單詞建議程序

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"] 
>>>