memory - 对字典使用 Trie 或 SortedSet？

Question

我对字典中使用 Tries/SortedSets 有一些疑问。

1. 哪个查找效率更高？
2. 哪个对虚拟内存更有效？
3. 用于字典时，这两种结构还有其他优点/缺点吗？

无需全部回答这三个问题，如果有的话，只需寻找一些好的回应和源材料。谢谢。

Answer 1

1. Trie 中的查找速度非常快，因为它们只需要O(length of key)比较，并且几乎是尽可能快的。SortedSet 通常使用平衡二叉搜索树来实现，在最坏的情况下，它会执行更多的比较，O(height of tree)字符串比较。所以特里是这里的明显赢家。

2. 虚拟内存效率可以看作是数据结构加载到内存中的速度。SortedSet 占用的空间与元素的数量成正比。它是使用指针实现的，这可能对加载效率不利。这可以通过将其序列化并将其存储在数组中来改进，但这会增加所需的空间。最简单形式的 Trie 占用大量内存。它也是使用指针实现的，这同样不利于加载效率。即使序列化，也需要大量的内存。但是这里有一些有趣的替代方案，它们可以压缩特里树并提供相同的性能。Radix Tries占用的内存显着减少。更好的是，DAWG（有向无环词图）重叠常见的后缀和前缀，并大量压缩字典。压缩后，DAWG 占用的空间可能比您的字典本身要少。它是使用数组实现的，因此加载速度也很快。最后，如果你有一个静态字典，DAWG 将是最好的选择，否则取决于。

3. trie 将键视为序列。它是一个前缀树。您可以非常快速地获取从前缀开始的所有单词。使用 trie，您可以有效地执行自动完成和自动更正。浮点数等一些键可能会导致 trie 中的长链，这是不好的。SortedSet 将键视为可比较的项目。因此很容易对元素进行分区。SortedSet 和 Trie 都可以按字母顺序提供键，但我猜 SortedSet 会快得多。