具有公共前缀的字符串的空间有效集合 - Java实现

我需要在内存中的Set like结构中存储数百万个具有公共前缀的字符串（它们不对应于文件系统路径），并查询Collection以查看路径是否存在。例如

/path
/path/1
/path/2
/path/1/a
/path/1/b

我想尽可能有效地存储它们（它们将在内存中），因为对于所有涉及的字符串，将会有许多共同的前缀，Trie是否是合理的候选者？我正在寻找在Java中实现合适的数据结构的建议。

已邀请:

6 个回复

峨躬坎抬焚

Trie看起来像你需要的结构。类似的结构也是Radix Tries，与尝试不同，使用字符序列来标记边缘。在普通尝试中，边缘标有单个字符，我确信它们在字符串共享相当多的前缀的情况下表现得更好。也可以看看 ... http://code.google.com/p/trie/ http://code.google.com/p/radixtree/

炉挤仙挟

这看起来像是一个很好的候选实现：https：//github.com/rkapsi/patricia-trie

弓萍功

让我们在任何建议之前考虑权衡。你说你需要存储“数百万”的路径。我假设一百万，因为它使计算更容易（甚至在服务器上，我还没有看到超过一百万个目录）。这些路径有多长？你已经展示了一个非常短的路径的例子，所以我们可能会看到一百兆字节来存储这些百万路径。我没有最大路径长度的参考，但我心中有256个字符。因此，您的路径将占用最多512 Mb的内存。你有那么多记忆吗？路径名的均匀分布如何？换句话说，您是否遵循80:20规则，其中80％的路径在20％的目录中找到？我问的原因是因为trie结构需要在级别之间使用某种形式的索引。如果你有很多目录只有几条路径，那么维护一个trie会有很多开销。建议：如果我有足够的记忆，我会使用HashSet<String>并完成它。如果我没有很多内存，并且目录结构遵循80:20规则（或者更可能是95：5），我会想到一个HashMap<String,Set<String>>。此映射的关键是具有“合理”重复量的最长前导路径字符串，值将是剩余的字符串。您将使用逐渐缩短的前导组件探测此地图，直到找到匹配项，然后探测其余部分的集合。这留下了“合理”重复的问题。这是重复的数量，其中两个数据结构的开销通过减少重复来克服。例如，/usr/bin/可能有效（因为它包含数千个文件，每个文件保存9个字符或18个字节），但/usr/local/bin/可能不会（至少在我的系统上，它只保存一个文件）。

寇剩

您可以使用树结构，就像在磁盘上一样。但是，您需要记住，树结构可以在节省开销时使用尽可能多的内存。即它们并非真正用于节省内存。如果存在这些文件，也许您可以使用磁盘子系统的缓存。它可能会更快。我会检查你真的需要这样做，因为你可以非常舒服地在JVM中存储一百万个条目。 ;）如果要最小化内存消耗，可以压缩内存中的数据。这可能比任何其他选项小得多，但制作效率更高。

抵舵

我会用什么：一个类似于的多层地图目录结构。单一的平衡树字符作为键和更多树作为价值观。

死搭胯

我建议你按原样存储路径，如字符串。我相信试图节省内存的开销将导致相反的结果。当然，通过对上面提到的Tries数据结构进行基准测试来测试它是否足够简单。

要回复问题请先登录或注册

具有公共前缀的字符串的空间有效集合 - Java实现

6 个回复

发起人

trie

问题状态

具有公共前缀的字符串的空间有效集合 - Java实现

与内容相关的链接

6 个回复

发起人

trie

问题状态