我正在研究C++中的拼寫檢查器，並且我被困在實現中的某個步驟中。在拼寫檢查器中使用Levenshtein距離
比方說，我們有一個拼寫正確的單詞和輸入的字符串的文本文件，我們想檢查拼寫錯誤。如果該字符串是一個拼寫錯誤的單詞，我可以通過檢查文本文件中的所有單詞並選擇與最少字母不同的單詞來輕鬆找到它的正確格式。對於這種類型的輸入，我已經實現了一個函數來計算2個字符串之間的Levenshtein編輯距離。到現在爲止還挺好。
現在，困難的部分：如果輸入的字符串是拼寫錯誤的單詞的組合？例如，「iloevcokies」。考慮到「我」，「愛」和「餅乾」是可以在文本文件中找到的單詞，我如何使用已實現的Levenshtein函數來確定文件中的哪些單詞適合於更正？另外，如何將空白插入正確的位置？
歡迎任何想法:)
短語的拼寫更正可以通過幾種方法完成。一種方法需要具有單詞二元組和三元組的索引。這當然可能是巨大的。另一種選擇是嘗試使用插入空格的單詞排列，然後對結果短語中的每個單詞進行查找。看一下谷歌的Peter Norvig的拼寫檢查器的簡單實現。無論哪種方式，考慮使用n-gram索引以獲得更好的性能，C++中有可用的庫供參考。
谷歌和其他搜索引擎能夠對詞組進行拼寫校正，因爲它們有很大的查詢索引和相關的結果集，這使得他們可以計算出一個統計上很好的猜測。總的來說，拼寫糾正問題可能會隨着上下文敏感糾正和語音糾正等方法變得非常複雜。鑑於使用可能的子項的排列可能會變得昂貴，您可以使用某些類型的啓發式，但這可能會很快超出範圍。
您也可以考慮使用和現有的拼寫庫，如aspell。
一個想法的起點：「iloevcokies」的L距離的頂級命中之一應該是「餅乾」。如果你可以改變你的L距離函數來跟蹤和返回一個最小索引和最大索引（即，這個匹配最好從字符5開始併到字符10），那麼你可以刪除那個子串並重新檢查L距離d爲之前的字符串，之後，再串連那些建議....
只是一個想法，好運氣....
我會假設你有一個現有的指數，上你運行你的levenshtein距離（例如，Trie，但任何排序的索引通常工作得很好）。
您可以考慮將白色空格添加爲常規編輯操作，只是存在一個轉折點：您需要（隨後）返回索引的下一個詞的根目錄。
這樣你就可以得到相同的索引，幾乎相同的路徑，大約相同的遍歷，它甚至不會影響你的運行時間。
不幸的是，你可能偶然發現一個完全不相關的單詞（即，這裏的編輯距離大概是6，這很大）。 – 2011-03-23 07:12:06
當然，在編輯距離上幾乎沒有任何字詞會被關閉，所以cookie仍然可能顯示爲頂級命中。儘管離完整的解決方案還很遠！ – usul 2011-03-30 01:24:27