什麼是遍歷Trie檢查拼寫建議的好算法？

Question

假設建立了一般詞典的字典，檢查4種拼寫錯誤的最佳方法是什麼 - 遍歷期間的替換，刪除，轉置和插入？

一種方法是找出給定單詞的n個編輯距離內的所有單詞，然後在Trie中檢查它們。這不是一個壞的選擇，但是更好的直覺似乎是使用動態編程（或遞歸等價）方法來確定在遍歷期間修改單詞之後的最佳子嘗試。

任何想法都會受到歡迎！

PS，將不勝感激實際投入，而不僅僅是答案中的鏈接。

Answer 1

其實我寫了一些代碼來做到這一點的一天：

https://bitbucket.org/teoryn/spell-checker/src/tip/spell_checker.py

它是基於由彼得·諾維格（http://norvig.com/spell-correct.html）的代碼，但存儲詞典的索引樹對於給定的編輯中發現的話距離更快。

該算法通過消耗輸入單詞中的字母，遞歸地遞歸地在每個步驟中應用可能的編輯（或不編輯）。遞歸調用的參數說明可以進行多少次編輯。通過檢查哪些字母實際上可以從我們給定的前綴中獲得，這個搜索結果有助於縮小搜索範圍例如，插入字符時，不是添加字母表中的每個字母，而只添加可從當前節點到達的字母。不進行編輯相當於從輸入單詞中的當前字母開始，從當前節點中取出分支。如果該分支不在那裏，那麼我們可以回溯並避免搜索可能找不到真正單詞的可能較大的空間。

Answer 2

看看如何計算Levenshtein distance，它提供了一個動態規劃解決方案，用於查找兩個序列之間的距離。

Answer 3

我認爲你可以在樹上直接進行廣度優先搜索：選擇你正在尋找的錯誤數量的閾值，只需一次一個地匹配一個單詞的字母，生成一組迄今達成一致的前綴（前綴，subtrie中）對，而你是你的錯誤閾值之下，添加到您的設置下一個子目標：

1. 在這個角色的地方沒有錯誤：添加子目標
2. 在此位置插入，刪除或替換的字符：在此處找到適當的字符串並增加錯誤計數;
3. 不是一個額外的目標，但要注意的是，換位要麼是與之前的刪除或插入相匹配的插入或刪除：如果此測試成立，則不要增加錯誤計數。

這看起來很天真：有沒有這個問題導致你想到動態編程？

Answer 4

假設您單詞中的每個連續字符代表樹中的一個級別，那麼您有五種情況要檢查每個字符（匹配，刪除，插入，替換和換位）。我假設換位是兩個相鄰的字符。

您將需要一個接受樹節點和要檢查的字符的函數（CheckNode）。它需要返回一組代表匹配的（子/大孩）節點。

您將需要一個接受單詞的函數（CheckWord）。它依次檢查每個字符與一組節點。它將返回一組代表匹配單詞的（葉）節點。

這個想法是，樹中的每個級別（孩子，大孩子等）匹配單詞中字符的位置。如果您調用頂級樹節點，級別0，則您將擁有級別1，級別2等。

顯然，對於沒有錯誤的單詞，字符位置和級別之間存在一對一匹配那個樹。

對於刪除操作，您需要跳過樹中的級別。

對於插入，您需要跳過單詞中的字符。

對於替換，您需要跳過關卡和角色。

對於換位，您需要（暫時）交換單詞中的字符。