存储字典中所有单词的最佳数据结构是什么？我能想到的最好的方法是使用 a HashMap，它将映射到 a HashTable。基本上，根据第一个字符，我们将获得关联HashTable，然后使用它，我们可以添加从该字符开始的单词。然后，我们将根据字符串选择一个好的散列函数。
有更好的方法吗？
问问题
73992 次
1 回答
148
根据您想要做什么，有许多好的数据结构。
如果您只想存储单词并询问“这个单词是否在这里？”，没有其他花哨机器的标准哈希表是一种合理的方法。如果该词是预先固定的列表，请考虑使用完美的哈希表以获得出色的性能和空间使用率。
如果您希望能够在支持快速查找的同时检查给定前缀是否存在，则trie是一个不错的选择，尽管它可能会有点空间效率低下。它还支持快速插入或删除。它还允许按字母顺序进行迭代，这是散列不提供的。这本质上是您在答案中描述的结构，但根据用例的不同，尝试的其他表示可能会更好。
如果除了上述之外，您还知道单词列表是固定的，请考虑使用DAWG（有向无环单词图），它本质上是该语言的最小状态 DFA。它比 trie 更紧凑，但支持许多相同的操作。
如果您想要类似 trie 的行为但又不想付出巨大的空间损失，那么三元搜索树是另一个可行的选择，基数树也是如此。这些是非常不同的结构，但在不同情况下可能比 trie 好得多。
如果空间是一个问题，但你想要一个 trie，请查看简洁的 trie表示，它的查找速度较慢，但理论上是最佳的空间使用。该链接讨论了它如何在 JavaScript 中用作传输大量数据的简单方法。另一种紧凑的表示是双数组 trie，尽管我承认我对此知之甚少。
如果您想将字典用于拼写检查等需要查找与其他单词相似的单词的操作，那么BK-tree是一个值得考虑的优秀数据结构。
希望这可以帮助！
于 2012-04-04T19:21:16.570 回答