字典和拼写检查器的数据结构？

可以使用哪种数据结构来有效地构建单词词典和拼写检查器?

答案取决于Spell Checker中所需的功能专家和内存的可用性。例如, 以下几种可能性。

散列 这是一个简单的选择。我们可以将所有单词放在哈希表中。参考这个该论文将散列与自平衡二叉搜索树和跳过列表进行了比较, 表明散列的性能更好。

哈希不支持前缀搜索之类的操作。前缀搜索是用户输入前缀的内容, 字典会显示所有以该前缀开头的单词。散列也不支持以字母顺序和最近邻居搜索有效地打印字典中的所有单词。

如果我们需要这两种操作, 请查找并添加前缀搜索, 特里很适合。使用Trie, 我们可以支持所有操作, 例如O(n)时间内的插入, 搜索, 删除, 其中n是要处理的单词的长度。 Trie的另一个优点是, 我们可以按字母顺序打印所有单词, 而散列是不可能的。

Trie的缺点是, 它需要大量空间。如果需要空间, 那么三元搜索树 可以是首选。在三元搜索树中, 搜索操作的时间复杂度为O(h), 其中h是树的高度。三元搜索树还支持Trie支持的其他操作, 例如前缀搜索, 字母顺序打印和最近邻居搜索。

如果我们要支持建议, 例如Google会显示”你的意思是…”, 那么我们需要在词典中找到最接近的单词。可以将最接近的单词定义为可以通过最少数量的字符转换(添加, 删除, 替换)获得的单词。一种幼稚的方法是拿走给定的单词, 并生成相距1距离(1个编辑或1个删除或1个替换)的所有单词, 并在字典中一一查看。如果未找到任何内容, 则查找所有距离为2的单词, 依此类推。为此有很多复杂的算法。按照维基页面, 迄今为止最成功的算法是Andrew Golding和Dan Roth的基于窗口的拼写校正算法。

看到这个一个简单的拼写检查器实现。

本文作者：皮尤什。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。