一尘不染

实现字典的最佳数据结构?

algorithm

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

有没有更好的方法?


阅读 253

收藏
2020-07-28

共1个答案

一尘不染

根据您要执行的操作,有许多良好的数据结构。

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

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

如果除了上述内容之外,您还知道单词列表是固定的,请考虑使用DAWG(定向无环单词图),它实际上是该语言的最低状态DFA。它比trie更为紧凑,但支持许多相同的操作。

如果您想要类似trie的行为,但又不想付出巨大的空间代价,那么三元搜索树基数树也是另一个可行的选择。这些结构非常不同,但是在不同情况下可能会比传统结构好得多。

如果空间是一个问题,但您想要一个trie,请查看简洁的trie表示形式,该表示的查找速度较慢,但​​理论上几乎是最佳的空间使用情况。该链接讨论了如何在JavaScript中使用它作为传输大量数据的简便方法。另一种紧凑的表示形式是double-
array trie
,尽管我承认对此知之甚少。

如果要将字典用于拼写检查等操作,需要在其中查找与其他单词相似的单词,则BK树是一个值得考虑的出色数据结构。

希望这可以帮助!

2020-07-28