基於編輯距離和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