我需要将数百万个带有公共前缀的字符串（它们不对应于文件系统路径）存储在内存中的类似结构的集合中，并查询集合以查看路径是否存在。
例如
/path
/path/1
/path/2
/path/1/a
/path/1/b
我想尽可能有效地存储这些（它们将在内存中），考虑到所有涉及的字符串都会有许多公共前缀，Trie 是否是一个合理的候选者？
我正在寻找有关在 Java 中实现合适数据结构的建议。
问问题
1772 次
6 回答
4
Trie看起来像您需要的结构。类似的结构还有Radix Tries，与尝试不同的是，它使用字符序列来标记边缘。在简单的尝试中，边缘用单个字符标记，我相信在字符串共享很多前缀的情况下它们会表现得更好。
也可以看看 ...
于 2011-04-08T13:35:51.927 回答
3
这看起来像是一个很好的候选实现：https ://github.com/rkapsi/patricia-trie
于 2011-04-08T13:36:28.987 回答
1
让我们在任何建议之前考虑权衡。
您说您需要存储“数百万”条路径。我假设有一百万，因为它使计算更容易（即使在服务器上，我也没有看到超过一百万的目录）。
这些路径有多长？您已经展示了一个路径非常短的示例，因此我们正在查看可能有一百兆字节来存储这百万条路径。我没有关于最大路径长度的参考资料，但 256 个字符在我脑海中挥之不去。因此，您的路径最多将占用 512 Mb 的内存。你有那么大的记忆力吗？
路径名的分布有多均匀？换句话说，您是否遵循 80:20 规则，即在 20% 的目录中找到 80% 的路径？我问的原因是因为 trie 结构需要某种形式的级别之间的索引。如果您有很多目录，而它们下面只有几条路径，那么您将有很多开销来维护 trie。
建议：如果我有足够的内存，我会使用 aHashSet<String>并完成它。
如果我没有很多内存，并且目录结构遵循 80:20 规则（或者，更有可能是 95:5），我会想到一个HashMap<String,Set<String>>. 此映射的键将是具有“合理”重复量的最长前导路径字符串，而值将是剩余的字符串。您将使用逐渐变短的前导组件来探测此地图，直到找到匹配项，然后探测其余部分的集合。
这就留下了“合理”重复的问题。这是重复的数量，其中两部分数据结构的开销被重复的减少所克服。例如，/usr/bin/可能是有效的（因为它包含数千个文件，并且每个文件保存 9 个字符或 18 个字节），但/usr/local/bin/可能不是（至少在我的系统上，它只包含一个文件）。
于 2011-04-08T14:31:39.210 回答
0
您可以使用 Tree 结构，就像在磁盘上一样。但是，您需要记住，树结构可以在开销中使用尽可能多或更多的内存，因为它们节省了。即它们并不是真正为节省内存而设计的。
如果这些文件存在，也许您可以使用磁盘子系统的缓存。它可能会更快。
我会检查您是否真的需要这样做，因为您可以非常轻松地在 JVM 中存储一百万个条目。;)
如果你想最小化内存消耗，你可以压缩内存中的数据。这可能比任何其他选项都小得多，但要提高效率则更复杂。
于 2011-04-08T13:36:38.177 回答
0
我建议您将路径按原样存储为字符串。我相信试图节省内存的开销会导致相反的结果。
当然，通过对上面提到的 Tries 数据结构进行基准测试来测试它是否是很简单的。
于 2011-04-08T13:46:21.597 回答
0
我会用什么：
- 类似于目录结构的多级映射。
- 一棵平衡树，以单个字符作为键，进一步的树作为值。
于 2011-04-08T13:38:07.467 回答