Jat*_*tin 63 string algorithm dictionary data-structures
存储字典所有单词的最佳数据结构是什么？我能想到的最好的就是使用a HashMap,它将映射到a HashTable.基本上,根据第一个字符,我们将得到关联HashTable,然后使用它,我们可以添加从该字符开始的单词.然后我们将根据字符串选择一个好的哈希函数.
有更好的方法吗？
tem*_*def 138
根据您的想法,有许多良好的数据结构.
如果您只想存储单词并询问"这里是否有这个词？",那么没有其他花哨机器的标准哈希表是一种合理的方法.如果该单词是预先修复的列表,请考虑使用完美的哈希表来获得出色的性能和空间使用.
如果您希望能够在支持快速查找的同时检查给定前缀是否存在,则trie是一个不错的选择,尽管它可能有点空间效率低.它还支持快速插入或删除.它还允许按字母顺序迭代,而散列不提供.这基本上是您在答案中描述的结构,但根据用例,其他尝试表示可能会更好.
如果除了上述内容之外,您知道单词列表是固定的,请考虑使用DAWG(有向非循环字图),它本质上是该语言的最小状态DFA.它比trie更紧凑,但支持许多相同的操作.
如果你想要类似于trie的行为但又不想付出巨大的空间损失,那么三元搜索树是另一个可行的选择,就像基数树一样.这些是非常不同的结构,但在不同情况下可以比trie好得多.
如果空间是一个问题,但你想要一个特里,请查看简洁的trie表示,它具有较慢的查找但只是理论上最佳的空间使用.该链接讨论了如何在JavaScript中使用它作为传输大量数据的简便方法.另一种紧凑的表示形式是双阵列特里,但不可否认,我对此知之甚少.
如果你想使用字典进行拼写检查等操作,你需要找到与其他单词类似的单词,那么BK树是一个很好的数据结构.
希望这可以帮助!