在实现带有单词建议的拼写检查器时通常使用什么算法？
起初，我认为检查输入的每个新单词（如果在字典中找不到）与字典中每个其他单词的Levenshtein 距离并返回最佳结果可能是有意义的。但是，这似乎效率很低，必须反复评估整个字典。
这通常是如何完成的？
问问题
59090 次
5 回答
212
Peter Norvig有一篇很好的文章，如何实现拼写校正器。这基本上是一种蛮力方法，尝试具有给定编辑距离的候选字符串。（这里有一些提示如何使用布隆过滤器和更快的候选散列来提高拼写校正器的性能。）
拼写检查器的要求较弱。你只需要找出字典中没有的单词。您可以使用布隆过滤器来构建消耗更少内存的拼写检查器。Jon Bentley 在Programming Pearls中描述了一个古老的版本，使用 64kb 作为英文词典。
Levenshstein 距离并不是拼写检查器的正确编辑距离。它只知道插入、删除和替换。转置丢失并为 1 个字符的转置生成 2（它是 1 个删除和 1 个插入）。Damerau-Levenshtein 距离是正确的编辑距离。
于 2010-02-19T08:34:43.227 回答
19
一种生成我已成功使用但从未在任何地方描述过的建议的方法是使用“坏”哈希函数预先计算建议（在构建字典时）。
这个想法是查看人们犯的拼写错误的类型，并设计散列函数，将不正确的拼写分配到与其正确拼写相同的桶中。
例如，一个常见的错误是使用了错误的元音，例如definate而不是限定。因此，您设计了一个哈希函数，将所有元音视为同一个字母。一种简单的方法是首先“规范化”输入单词，然后将规范化的结果放入常规哈希函数中。在此示例中，规范化函数可能会删除所有元音，因此definite变为dfnt。然后用典型的散列函数对“标准化”字进行散列。
使用这个特殊的散列函数将所有字典单词插入到辅助索引（散列表）中。此表中的存储桶将具有较长的冲突列表，因为散列函数是“坏的”，但这些冲突列表本质上是预先计算的建议。
现在，当您找到拼写错误的单词时，您可以在辅助索引中查找拼写错误映射到的存储桶的冲突列表。Ta da：你有一个建议清单！您所要做的就是对上面的单词进行排名。
在实践中，您需要一些带有其他哈希函数的辅助索引来处理其他类型的错误，例如转置字母、单/双字母，甚至是一个简单的类似 Soundex 的索引来捕获语音拼写错误。在实践中，我发现简单的发音有很长的路要走，并且基本上已经过时了一些旨在查找琐碎拼写错误的发音。
因此，现在您在每个辅助索引中查找拼写错误，并在排名前连接冲突列表。
请记住，冲突列表仅包含字典中的单词。使用尝试生成替代拼写的方法（如 Peter Norvig 文章中所述），您可以获得（数万）个您首先必须根据字典过滤的候选者。使用预先计算的方法，你可能会得到几百个候选人，而且你知道他们都拼写正确，所以你可以直接跳到排名。
更新：从那以后，我发现了一种与此类似的算法描述，即FAROO 分布式搜索。这仍然是一个编辑距离有限的搜索，但它非常快，因为预计算步骤就像我的“坏哈希函数”想法一样。FAROO 只是使用了一个有限的散列函数概念。
于 2013-12-18T18:52:24.313 回答
7
算法
- 将拼写错误的单词作为输入。
- 将英语单词列表及其频率存储在文本文件中。
- 在三元搜索树中插入所有可用的英语单词（存储在文本文件中）及其频率（衡量一个单词在英语中的使用频率）。
- 现在沿着三元搜索树遍历 -
- 对于在三元搜索树中遇到的每个单词，计算其与拼写错误的单词的 Levensthein 距离。
- 如果 Levensthein 距离 <= 3，则将单词存储在优先队列中。
- 如果两个词的编辑距离相同，则频率越高的词越重。打印优先队列中的前 10 个项目。
优化
- 如果输入单词的子串与当前单词的编辑距离大于 3，则可以剔除当前节点子树中的单词。
你可以在github 项目 上找到更详细的解释和源代码。
于 2017-02-11T08:17:24.197 回答
3
您不需要知道字典中每个单词的确切编辑距离。您可以在达到限制值后停止算法并排除该单词。这将为您节省大量的计算时间。
于 2010-02-19T08:44:52.307 回答