logo标签列表

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

algorithmlanguage-agnosticspell-checkinglevenshtein-distance
123

在实现带有单词建议的拼写检查器时，通常使用什么算法？

一开始，我认为对于每个新输入的单词（如果未在字典中找到）进行检查，并将其与字典中的每个单词计算Levenshtein距离，然后返回前几个结果可能是有意义的。但是，这似乎非常低效，需要不断评估整个字典。

通常是如何实现的呢？

6个回答
217

有一篇Peter Norvig写的好文章介绍如何实现一个拼写纠正器。它基本上是一种暴力破解方法，尝试使用给定的编辑距离生成候选字符串。（这里有一些提示，可以通过使用Bloom过滤器和更快的候选哈希来提高拼写校正器的性能。）

拼写检查器的要求较弱。您只需找出字典中没有该单词即可。您可以使用Bloom过滤器构建拼写检查器，从而消耗更少的内存。Jon Bentley在Programming Pearls中描述了一个古老版本，仅使用64kb的英语字典。

BK-Tree是另一种替代方法。这里有一篇不错的文章链接。

Levenshstein距离并不是一个拼写检查器的完全正确的编辑距离。它只知道插入、删除和替换。转置缺失，对于1个字符的转置会产生2（它包含1个删除和1个插入）。Damerau-Levenshtein距离才是正确的编辑距离。

2
对于相对较不为人知的BK-Tree参考文献，我给予了+1的评价。这就是像谷歌这样处理实际数据量的公司所采用的方法。 - NoozNooz42
3
这里有一份更好的 BK 树解释链接。 - Ian Boyd
19
我成功使用过但从未在任何地方看到描述的生成建议的方法是通过使用“糟糕”的哈希函数预计算建议（在构建字典时）。

这个想法是看人们犯的拼写错误类型，并设计哈希函数，使得一个不正确的拼写与其正确的拼写分配到相同的桶中。

例如，常见的错误是使用错误的元音，比如definate 而不是 definite。所以你设计了一个哈希函数，将所有元音字母视为相同的字母。一个简单的方法是先 "规范化" 输入单词，然后将规范化的结果通过常规哈希函数。在这个例子中，规范化函数可能会删除所有元音字母，所以 definite 变成了 dfnt。这个 "规范化" 的单词然后通过一个典型的哈希函数进行哈希。

使用这种特殊哈希函数向辅助索引（哈希表）中插入所有字典单词。由于哈希函数是 "糟糕的"，所以这个表中的桶将有较长的冲突列表，但那些冲突列表实质上就是预先计算的建议。

现在，当你找到一个拼错的单词时，查找辅助索引中该错误映射到的桶的冲突列表。哎呀：你有了一个建议列表！你所要做的就是对其上的单词进行排名。

在实践中，你将需要一些带有其他哈希函数的辅助索引来处理其他类型的错误，例如颠倒字母、单/双字母，甚至是类似 Soundex 的简单音标拼写错误。实际上，我发现简单的发音方法可以起到很大的作用，并且本质上使一些旨在查找琐碎的错别字的方法过时了。

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

请记住，碰撞列表中仅包含字典中存在的单词。对于试图生成替代拼写的方法（如Peter Norvig文章中所述），您可能会得到（数十）万个候选项，您首先必须将它们与字典进行过滤。使用预先计算的方法，您可能会得到几百个候选项，并且您知道它们都是拼写正确的，因此可以直接跳过筛选步骤进行排名。

更新：我后来找到了一个与此类似的算法描述，即FAROO分布式搜索。这仍然是一个编辑距离有限的搜索，但是由于预计算步骤类似于我的“不良哈希函数”想法，因此非常快速。FAROO只使用了有限的不良哈希函数概念。

感谢引用Faroos的SymSpell算法。虽然两种算法都是预先计算可能的拼写错误并使用哈希表进行快速查找，但主要区别在于SymSpell保证检测到所有可能的拼写错误，直到某个编辑距离（在这方面SymSpell等同于Peter Norvig的算法，只是快了3..6个数量级），而您的算法则使用启发式方法，仅检测所有理论上可能的拼写错误的有限子集（因此您的预计算成本可能会更低）。 - Wolf Garbe
SymSpell算法明确地预先计算并存储可能的拼写错误，而我的“坏哈希”方案则没有。对于英语来说，只需添加一个简单的语音哈希即可涵盖大量内容（例如，“terradacktle” -> “pterodactyl”，其编辑距离为6）。当然，如果您需要多语言查找，则可能会更加困难。 - Adrian McCarthy
通过利用关于可能的拼写错误的经验知识（并限制在这些错误上），您可以节省预计算时间和空间。但是，为了涵盖所有可能的拼写错误，SymSpell只需要预先计算其中的一小部分。一个五个字母的单词在最大编辑距离为3的情况下有大约300万种可能的拼写错误，但是使用SymSpell，您只需要预先计算和存储25个删除操作。这对于模糊/相似性搜索超出拼写纠正范围的情况非常重要，因为没有经验知识存在。 - Wolf Garbe
7

算法

  1. 输入一个错误拼写的单词。
  2. 将英语单词及其频率列表存储在文本文件中。
  3. 将所有可用的英语单词（存储在文本文件中）以及它们的频率（衡量单词在英语语言中使用频率的指标）插入到三叉搜索树中。
  4. 现在遍历三叉搜索树 -
    • 对于在三叉搜索树中遇到的每个单词，计算它与错误拼写单词之间的Levensthein距离。
    • 如果莱文斯坦距离<= 3，则将该单词存储在优先队列中。
    • 如果两个单词具有相同的编辑距离，则具有更高频率的单词优先。 从优先队列打印前10项。

优化

  1. 如果当前节点的子串与输入单词的编辑距离大于3，则可以消除当前节点子树中的单词。
    您可以在GitHub项目中找到更详细的解释和源代码。
嗯，在这种情况下，“grater”到“greater”的Levenshtein距离是不够的，因为“grater”也是一个词典单词。;-) - Tony Brasunas
1
@TonyBrasunas，是的，你说得对。但是程序将实际返回一个包含10个单词的列表，如果输入为'grater'，它将建议编辑距离为0的'grater'以及编辑距离为1的'greater'。这可能会有所帮助。 ;) - amarjeetAnand
如果一个候选项的距离为2，但非常频繁，而另一个候选项的距离为1，但非常罕见，你如何对这两个进行排名？在上述方法中，罕见的项总是获胜，这是正确的结果吗？ - speedplane
@speedplane 是的，罕见的词会获胜。而且我认为这是正确的结果。因为我们期望的是最接近输入单词拼写的单词。如果你还有疑问，可以这样想---假设有一个用户正确拼写的罕见单词。现在它的距离为0，但频率非常低。在建议中，我们应该将这个罕见的单词（距离为0）排在最上面（因为最小编辑距离获胜），其他距离为1-2-3的单词排在下面。 - amarjeetAnand
3

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

2
拼写检查器非常容易实现，例如Unix拼写程序。源代码可在公共领域中获得。纠正可以通过编辑来实现，再次检查新单词是否在字典中。这些新的编辑可以分组并显示给用户。
Unix系统使用Mc IllRoy编写的程序。另一种方法是使用Trie，对于大型文件来说可能会很有用。 Unix方法需要非常少的空间来存储巨大的字典，因为它使用散列散列算法。
0

Levenshtein距离递归算法因为重复比较而变得非常缓慢。然后使用wagner-Fisher算法。（它有太多的变体）它使用矩阵来比较字母。

enter image description here

使用3个操作

Insert a character
Delete a character
Replace a character.

每个单元格都保留将字符串片段转换所需的最小操作数。例如，要将“AB”转换为“NFB”，我们查看第2行和第3列，即“2”。
1- 我们用“N”替换“A”，因此得到“NB”。
2- 我们在“NB”之间插入“F”，以达到“NFB”。
我认为这与Leetcode-72有关。 在该算法中，我们实际上一次使用两行。 这就是为什么它被称为“基于两个矩阵行的算法”。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接