我对字典的 Tries/SortedSets 用法有一些疑问。
- 哪个查找效率更高？
- 哪个对虚拟内存更有效？
- 当用于字典时，这两种结构还有其他优点/缺点吗？
无需回答所有三个问题，只需寻找一些好的回复和原始资料(如果有的话)。谢谢。
最佳答案
Trie 中的查找非常快，因为它们只需要
O(length of key)比较，而且速度几乎达到了可能的速度。 SortedSet 通常使用平衡的二叉搜索树来实现，这将执行更多的比较，在最坏的情况下是O(height of tree)字符串比较。因此 Trie 树显然是这里的赢家。虚拟内存效率可以看作是数据结构加载到内存中的速度。 SortedSet 占用的空间与元素的数量成正比。它是使用指针实现的，这可能不利于加载效率。这可以通过序列化并将其存储在数组中来改进，但这会增加所需的空间。最简单形式的 Trie 树占用很多内存。它也是使用指针实现的，这对加载效率同样不利。即使序列化，也占用大量内存。但是这里有一些有趣的替代方案，它们可以压缩 trie 并提供相同的性能。 Radix Tries 占用的内存量要少得多。更好的是，DAWG(有向无环词图)重叠常见的后缀和前缀，并大量压缩字典。压缩后，DAWG 占用的空间可能比字典本身要少。它是使用数组实现的，因此加载速度也很快。最后，如果你有一个静态字典，DAWG 将是最好的方式，否则就看情况了。
trie 将键视为序列。它是一个前缀树。您可以非常快速地获取从前缀开始的所有单词。使用 trie，您可以有效地执行自动完成和自动更正。某些键(如 float )可能会导致 trie 中出现长链，这很糟糕。 SortedSet 将键视为可比较的项目。因此很容易对元素进行分区。 SortedSet 和 Trie 都可以按字母顺序提供键，但我猜 SortedSet 会快得多。
关于memory - 字典使用 Trie 还是 SortedSet？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17797306/