什么算法在拼写检查器中提供建议？

Question

在实现伴随单词建议的拼写检查器时,通常使用什么算法？

起初我认为检查每个键入的新单词(如果没有在字典中找到)与字典中的每个其他单词的Levenshtein距离并返回最高结果可能是有意义的.然而,这似乎非常低效,不得不反复评估整个字典.

这通常是怎么做的？

Answer 1

Peter Norvig有一篇很好的文章如何实现拼写纠正器.它基本上是一种蛮力方法,尝试使用给定编辑距离的候选字符串.(以下是一些提示如何使用布隆过滤器和更快的候选散列来提高拼写校正器性能的方法.)

拼写检查器的要求较弱.你只需要发现一个单词不在字典中.您可以使用Bloom Filter构建一个消耗较少内存的拼写检查程序.Jon Bentley使用64kb作为英语词典,在编程珍珠中描述了一个古老的版本.

甲BK-树是一种替代方法.这里有一篇好文章.

Levenshstein距离不是拼写检查器的正确编辑距离.它只知道插入,删除和替换.缺少转置,并为1个字符的转置产生2(它是1个删除和1个插入).Damerau-Levenshtein距离是正确的编辑距离.

Answer 2

用于生成我已成功使用但从未在任何地方看到的建议的方法是使用"坏"散列函数预先计算建议(在构建字典时).

我们的想法是查看人们所做的拼写错误的类型,并设计散列函数,这些散列函数会将错误的拼写分配给与正确拼写相同的存储桶.

例如,一个常见的错误是使用了错误的元音,如definate而不是明确的.因此,您设计了一个哈希函数,将所有元音视为相同的字母.一种简单的方法是首先"标准化"输入字,然后通过常规散列函数将标准化结果放入.在此示例中,规范化功能可能会丢弃所有元音,因此definite变为dfnt.然后使用典型的散列函数对"标准化"字进行散列.

使用此特殊散列函数将所有字典单词插入辅助索引(散列表).此表中的存储区将具有较长的冲突列表,因为哈希函数是"坏"的,但这些冲突列表基本上是预先计算的建议.

现在,当您找到拼写错误的单词时,您将查找拼写错误映射到辅助索引中的存储桶的冲突列表.塔达:你有一个建议清单!你所要做的就是对它上面的字进行排名.

实际上,你需要一些带有其他散列函数的辅助索引来处理其他类型的错误,比如转置字母,单/双字母,甚至是一个简单的类似Soundex的错误来捕捉拼音拼写错误.在实践中,我发现简单的发音有很长的路要走,并且基本上废弃了一些旨在发现琐碎错别字的发音.

所以现在你在每个辅助索引中查找拼写错误并在排名之前连接碰撞列表.

请记住,碰撞列表仅包含字典中的单词.通过尝试生成替代拼写的方法(如Peter Norvig文章中所述),您可以获得(数十)数千个候选人,首先必须对字典进行过滤.使用预先计算的方法,您可能会得到几百名候选人,并且您知道他们都拼写正确,因此您可以直接跳到排名.

更新:我发现了一个与此类似的算法描述,即FAROO分布式搜索.这仍然是一个编辑距离限制搜索,但它非常快,因为预计算步骤就像我的"坏哈希函数"的想法.FAROO只使用了有限的哈希函数概念.

Answer 3

算法

1. 将错误拼写的单词作为输入.
2. 将英语单词列表及其频率存储在文本文件中.
3. 在三元搜索树中插入所有可用的英语单词(存储在文本文件中)及其频率(衡量单词在英语中的使用频率).
4. 现在遍历三元搜索树 -
   • 对于三元搜索树中遇到的每个单词,从错误拼写的单词计算其Levensthein距离.
   • 如果Levensthein Distance <= 3,则将该单词存储在Priority Queue中.
   • 如果两个单词具有相同的编辑距离,则频率较高的单词更为重要.打印优先级队列中的前10项.

优化

5. 如果当前字的输入字的子字符串的编辑距离大于3,则可以在当前节点的子树中删除字. 您可以在github项目中找到更详细的说明和源代码.