string - 实现字典的最佳数据结构？

Question

存储字典中所有单词的最佳数据结构是什么？我能想到的最好的方法是使用 HashMap，它将映射到 HashTable。基本上，根据第一个字符，我们将获得关联的 HashTable，然后使用它，我们可以添加从该字符开始的单词。然后我们将根据字符串选择一个好的哈希函数。

有没有更好的方法？

Answer 1

取决于你想做什么，有很多好的数据结构。

如果您只想存储单词并询问“这个单词是否在这里？”，没有其他花哨机制的标准哈希表是一种合理的方法。如果该词是预先固定的列表，请考虑使用 perfect hash table以获得出色的性能和空间利用率。

如果您希望能够在支持快速查找的同时检查给定前缀是否存在，trie是一个不错的选择，尽管它的空间效率可能有点低。它还支持快速插入或删除。它还允许按字母顺序进行迭代，而散列法不提供。这基本上是您在答案中描述的结构，但根据用例，其他尝试表示可能会更好。

如果除上述之外，您知道单词列表是固定的，请考虑使用 DAWG (有向无环词图)，本质上是该语言的最小状态 DFA。它比 trie 结构更紧凑，但支持许多相同的操作。

如果你想要类似 trie 的行为但不想付出巨大的空间代价，ternary search tree是另一个可行的选择，radix tree 也是如此。 .这些是非常不同的结构，但在不同情况下可能比 trie 更好。

如果空间是一个问题，但你想要一个 trie，请查看 succinct trie表示，它的查找速度较慢，但​​在理论上几乎是最佳空间使用。该链接讨论了如何在 JavaScript 中使用它作为传输大量数据的简单方法。另一种紧凑表示是 double-array trie ，虽然我对此知之甚少。

如果您想使用词典进行拼写检查等需要查找与其他词相似的词的操作，BK-tree是一个值得考虑的优秀数据结构。