使用Trie树还是SortedSet来构建字典？

Question

我对使用Tries/SortedSets进行字典操作有一些疑问。

1. 在查找方面，哪个更有效率？
2. 在虚拟内存方面，哪个更有效率？
3. 当将这两种结构用于字典时，是否存在其他优缺点？

不需要回答所有问题，只要提供一些好的回答和相关资料即可。谢谢。

- PandaBearSoup

---

也许这篇 Stack Overflow 文章《如何在哈希表和 Trie（前缀树）之间进行选择？》可以帮到你？ - keenthinker

Answer 1

1. Trie中的查找非常快，因为它们只需要O(键长)次比较，几乎是最快的。SortedSet通常使用平衡二叉搜索树实现，这将执行更多的比较，在最坏情况下需要O(树高)个字符串比较。因此，Trie在这里是明显的赢家。

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

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

- max

---

一个提示：在第一点上，“所以 Trie 在这里是明显的赢家。”根据我的发现，排序集合的查找效率为 O(log(n))。因此，对于像“恐龙”（8个字符）这样的搜索词，您的字典必须有超过1亿（10^8）个单词，才能使 Trie 更有效率。 - emilyk