What algorithm gives suggestions in a spell checker?

有 good essay by Peter Norvig如何实现拼写校正器。它基本上是一种蛮力方法，用给定的编辑距离来尝试候选字符串。(给你是一些如何使用 Bloom Filter 布鲁姆过滤器和 faster candidate hashing提高拼写校正器性能的技巧。)

对拼写检查的要求较弱。你只要发现字典里没有这个词就行了。您可以使用 Bloom Filter 布鲁姆过滤器来构建一个拼写检查器，它消耗更少的内存。一个古老的版本是由 Jon Bentley 在 编程珍珠中使用64kb 作为英语词典来描述的。

BK-Tree是一种可供选择的方法，给你是一篇不错的文章。

Levenshstein 距离不完全是拼写检查的正确编辑距离。它只知道插入、删除和替换。对于1个字符的转换(1个删除和1个插入) ，转换丢失并生成2。达默罗莱文斯坦距离是正确的编辑距离。

您不需要知道字典中每个单词的确切编辑距离。可以在达到一个限制值后停止算法并排除该单词。这将为您节省大量计算时间。

Spell checker is very easy to implement as in Unix spell program. The source code is available in public. The correction can be involved, one technique is to do edits and again check if this new word is in the dictionary. Such new edits can be grouped and shown to the user.

Unix 系统使用了一个由 Mc IlRoy 编写的程序。另一种方法是使用 Trie，它在处理大文件时非常有用。

• 我的 Trie 实验
• Unix 喜欢实验

Unix 方法使用散列哈希算法，因此对于一个巨大的字典所需的空间非常小。

生成建议的一种方法是使用“坏的”散列函数预先计算建议(在构建字典时) ，这种方法我已经成功地使用过，但从未在任何地方见过描述。

其思想是查看人们犯的拼写错误类型，并设计散列函数，将不正确的拼写分配给与正确拼写相同的桶。

例如，一个常见的错误是使用错误的元音，如 定义而不是 绝对的。所以你设计了一个散列函数，它把所有的元音都当作同一个字母。一个简单的方法是首先“规范化”输入单词，然后将规范化的结果放入一个常规散列函数中。在本例中，规范化函数可能删除所有元音，因此 definite变成 dfnt。然后，使用典型的散列函数对“规范化”单词进行散列。

使用这个特殊的散列函数将所有字典单词插入辅助索引(散列表)中。由于散列函数是“坏的”，这个表中的存储桶将拥有较长的冲突列表，但是这些冲突列表本质上是预先计算好的建议。

现在，当您发现拼写错误的单词时，您可以在辅助索引中查找拼写错误映射到的 bucket 的冲突列表。当当: 你有一个建议列表！你要做的就是在上面排序。

在实践中，您将需要一些带有其他散列函数的辅助索引来处理其他类型的错误，比如换位字母、单/双字母，甚至还需要一个简单的 Soundex (类似 Soundex)来捕捉语音拼写错误。在实践中，我发现过于简单化的发音有很大的帮助，并且基本上淘汰了一些用于发现琐碎拼写错误的发音。

现在查找每个辅助索引中的拼写错误，并在排序之前连接冲突列表。

请记住冲突列表只包含字典中的单词。通过尝试生成替代拼写的方法(如 Peter Norvig 的文章) ，您可以获得(数以万计)首先必须根据字典进行筛选的候选拼写。使用预先计算的方法，您可能会得到几百个候选人，并且您知道他们都拼写正确，因此您可以直接跳到排名。

更新 : 我发现了一个类似的算法描述，FAROO Distributed Search。这仍然是一个编辑距离有限的搜索，但是它非常快，因为预计算步骤的工作方式类似于我的“坏散列函数”的想法。FAROO 只是使用了一个有限的坏散列函数概念。

算法

1. 将拼写错误的单词作为输入。
2. 将英语单词列表及其频率存储在一个文本文件中。
3. 将所有可用的英语单词(存储在文本文件中)以及它们的频率(衡量一个单词在英语中的使用频率)插入到一个三元搜索树中。
4. 现在沿着三元搜索树走
   • 对于在三元搜索树中遇到的每个单词，从拼写错误的单词计算它的 Levensthein 距离。
   • 如果 Levensthein 距离 < = 3，则将单词存储在优先级队列中。
   • 如果两个单词有相同的编辑距离，频率较高的单词是格栅。 打印优先队列中的前10项。

优化

5. 如果输入单词的子串与当前单词的编辑距离大于3，则可以对当前节点子树中的单词进行元素化。

   ---

   您可以在 Github 项目上找到更详细的解释和源代码。