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

Question

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

起初我认为检查每个输入的新词(如果没有在字典中找到)与它的 Levenshtein distance 可能是有意义的从字典中的每个其他单词并返回顶部结果。然而，这似乎是非常低效的，必须重复评估整个字典。

这通常是如何完成的？

Answer 1

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

拼写检查器的要求较弱。你只需要找出一个词不在字典里就可以了。您可以使用 Bloom Filter构建一个消耗更少内存的拼写检查器。 Programming Pearls 中描述了一个古代版本作者 Jon Bentley 使用 64kb 的英文词典。

A BK-Tree是一种替代方法。一篇不错的文章是here .

Levenshstein 距离并不是拼写检查器的正确编辑距离。它只知道插入、删除和替换。缺少换位并为 1 个字符的换位生成 2(它是 1 个删除和 1 个插入)。 Damerau–Levenshtein distance是正确的编辑距离。