基于编辑距离和lcs的提示性拼写检查器？

Question

我如何实现一个简单的拼写检查器，接受拼写错误的单词和编辑距离阈值，然后生成建议的正确单词列表。 这是想通过使用一种算法来实现 1-use both editing edit distance and longest common subsequence 2 - 不要计算字典中每个单词的编辑距离???????

Answer 1

所以你有一个单词词典，你想用编辑距离来计算与给定单词最接近的匹配。

一些建议，以快捷方式的过程中检查所有可能的选项：

• 缓存最接近的匹配到的话，当你做了计算。如果有人输入“spelling”并且您的顶级比赛是“spelling”，“spewing”和“spilling”，请将这些匹配与他们计算的距离和阈值一起保存。下次您看到“拼写”时，您可以检索阈值为< =新阈值的任何结果。
• 使用levenshtein距离计算时，可以丢弃任何长度差大于阈值的词。你应该能够简化这个过程。当然，如果你想要共同的子序列，那么这个就会失败。
• 修改levenshtein距离计算器，一旦达到阈值就立即中断。你仍然会开始检查很多不匹配的单词，但你很快就会做更少的工作。

如果你仍然在levenshtein距离算法之后，看看这个例子。这很快。

http://dotnetperls.com/levenshtein

Answer 2

彼得·诺维格在Python这样做，有人移植了拼写检查器C＃

http://norvig.com/spell-correct.html

http://www.codegrunt.co.uk/?page=cSharp#norvigSpell