单词建议程序

Question

向我建议一个程序或方式来处理单词更正/建议系统。 - 假设输入为'Suggset'，则应该显示'Suggest'。

Thanx提前。我正在使用python和AJAX。请不要向我推荐任何jquery模块，因为我需要算法部分。

Answer 1

算法。鉴于某些语言的单词列表和打字错误/不完整的单词，您需要建立一个最接近它的给定字典中的单词列表。例如，“建议”和“suggset”之间的距离等于2 - 您需要一次删除和一次插入。作为优化，您可以为每个操作指定不同的权重 - 例如，您可以说替换比删除更便宜，并且键盘上靠近键盘的两个字母（例如'v'和'b'）之间的替换比较便宜，相距很远（例如'q'和'l'）。

1964年出现了用于拼写和修正的算法的第一个描述。1974年，基于动态规划的高效算法出现在Robert A.Wagner和Michael J.Fischer的论文“String-to-string correction problem”中。任何算法书都有或多或少的详细处理。

对于蟒蛇有库，做到这一点：Levenshtein distance library 还要检查这个earlier discussion on Stack Overflow

Answer 2

要自己制作其中的一个需要很多工作。有一个非常好的拼写检查器库，用python编写，名为​​，我发现它非常好。下面是从他们的网站的例子：该解决您的问题称为“编辑距离”

>>> import enchant 
>>> d = enchant.Dict("en_US") 
>>> d.check("Hello") 
True 
>>> d.check("Helo") 
False 
>>> d.suggest("Helo") 
['He lo', 'He-lo', 'Hello', 'Helot', 'Help', 'Halo', 'Hell', 'Held', 'Helm', 'Hero', "He'll"] 
>>>