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

Question

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

例如

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

我想尽可能有效地存储它们(它们将在内存中),因为对于所有涉及的字符串,将会有许多共同的前缀,Trie是否是合理的候选者？

我正在寻找在Java中实现合适的数据结构的建议.

Answer 1

Trie看起来就像您需要的结构。类似的结构还有Radix Tries，与 attempts 不同，它使用字符序列来标记边缘。在简单的尝试中，边缘用单个字符标记，我确信它们在字符串共享大量前缀的情况下表现得更好。

也可以看看 ...

http://code.google.com/p/trie/

http://code.google.com/p/radixtree/