我正在做一個非常酷的家庭作業，其中通過使用帶有文本T的字典D，即時消息應該掃描文本T以及T中的每個單詞不在D中，生成通過執行以下常見拼寫錯誤中的至少一個可能的正確拼寫列表：交換兩個相鄰字符，插入額外字符，刪除單個字符並將字符替換爲另一個字符。從錯誤拼寫的單詞創建可能的正確拼寫列表
林不知道該如何去最後一部分，但這裏是我到目前爲止有：
1）使用的Java方法的任何一個到每個字分成一個字符串數組一入口 2.）使用帶有索引k的for循環轉到I中的每個條目，並使用get（k）來查看我們的字典中是否存在該單詞。如果不是，則將該單詞添加到另一個字符串數組MisspelledWords []中。
3.）我怎麼能有效地做這些常見的拼寫檢查之一？現在，我只能想到那些效率非常低的事情，比如隨意更改最後一封信或什麼的。
謝謝！
我能想到的有效做到這一點的答案是使用排序。基本上這是找出anagrams的方法。
你把你的字典，排序每一個單詞，並在散列。例如。狗，上帝 - >排序後 - > DGO。所以在DGO中你會有狗和神（喜歡鏈式哈希）。
現在您對拼寫錯誤的單詞進行排序，找到匹配的地方。你將字符與字符進行比較，將所有其他字詞放在同一個桶中。
警告：
如果有信丟失，這不能檢測。也許在比較拼寫錯誤的單詞時，我們可以考慮具有所有字母的任何存儲桶。 （例如）如果你在尋找好的，而你有神（讓希望沒有神的話）。你會排序並有dgo。你可以查看任何有一半以上字母的桶。在這個例子中是2個字母。
一旦你創建了散列（一次性成本），你的效率就會很好。請讓我知道是否可以對此進行任何改進。
好幾個指針讓你開始。如果您想要有效地存儲和檢索具有通用前綴的單詞，請嘗試使用prefix tree。對於拼寫檢查部分，請閱讀edit distance。
此外，對於一個簡單但實用且很好解釋（和簡短！）的實現，請參閱Norvig的this article。
基本上你想計算你的'壞'字和詞典中每個單詞之間的Levenshtein距離。這在計算上不是一個「便宜」的過程，但它可以讓您輕鬆檢測簡單換位/單一字符差異。
總之，L.D.是通過在每個步驟中添加/刪除/更改僅一個字符來將一個字符串轉換爲另一個字符串所需的「步驟」數量。
color/colour = LD of 1
mad/min = LD of 2 (mad -> man -> min
這裏的問題是mad/min的LD是2（並且這不符合作業規則下潛在的拼寫錯誤）並且mad/mda的LD也是2（但是這符合潛力拼錯）。因此，在爲每個單詞計算LD的所有麻煩之後，OP仍然需要應用額外的邏輯。 – gcooney 2011-04-20 22:24:15
我有一個學校項目是very similar to this one。
基本理論是，您要計算單詞T和字典D中所有單詞之間的Levenshtein Distance。然後您將呈現最高的X個結果，其中距離越低越好。
我同意這個項目是我的最愛之一。我發現的一個有趣功能是在結果表中存在特定的對稱性，這使得該算法易於多線程化。
祝你好運！
編寫一個比較兩個單詞的算法，並使用老師給你的規則來確定一個單詞是否可能是另一個單詞的拼寫錯誤。如果您遇到阻礙，請參閱Damerau-Levenshtein distance，這是一個修改的Levenshtein距離，它將轉置字符考慮在內。
然後，您需要使用該算法將每個拼寫錯誤的單詞與字典中的每個單詞進行比較。提示算法更有效率：可以在不計算距離函數的情況下消除大量詞作爲候選詞（考慮從n + 2個字符詞開始的n個字符詞的最小距離）。
這隻適用於字符交換的情況。它不適用於刪除的字符，添加的字符或替換的字符 – gcooney 2011-04-21 01:47:01
我已經提到過這種情況作爲警告，我們可以按照我在那裏提到的方式處理它。 – sethu 2011-04-21 06:08:51