Levenshtein算法：我如何滿足這種文本編輯要求？

我使用Levenshtein算法來滿足這些要求：Levenshtein算法：我如何滿足這種文本編輯要求？

當發現N個字符的字，詞在我的字典數據庫建議作爲修正爲：

的有1 N個字符的每一個字字典與所發現的詞語不同的性格。例如：創建詞：bearn，字典詞：熊

每個有N個字符的N + 1個字符的詞典單詞等於找到的單詞。例如：找到的單詞：bear，詞典單詞：熊

每個包含N-1個字符的N-1個字符的字典單詞都與找到的單詞相等。例子：發現一句話：熊，字典裏的單詞：熊

我使用這個實現在C++ Levenshtein算法來尋找當一個字有1萊文斯坦號（這是萊文斯坦數爲所有三種情況），但是我該如何選擇要建議的單詞呢？我閱讀了Boyer-Moore-Horspool和Knuth-Morris-Pratt，但我不確定他們中的哪一個能夠有所幫助。

#include <string> 
#include <vector> 
#include <algorithm> 

using namespace std; 

int levenshtein(const string &s1, const string &s2) 
{ 
    string::size_type N1 = s1.length(); 
    string::size_type N2 = s2.length(); 
    string::size_type i, j; 
    vector<int> T(N2+1); 

    for (i = 0; i <= N2; i++) 
     T[i] = i; 

    for (i = 0; i < N1; i++) { 
     T[0] = i+1; 
     int corner = i; 
     for (j = 0; j < N2; j++) { 
     int upper = T[j+1]; 
     if (s1[i] == s2[j]) 
      T[j+1] = corner; 
     else 
      T[j+1] = min(T[j], min(upper, corner)) + 1; 
     corner = upper; 
     } 
    } 
    return T[N2]; 
}

來源

2009-01-27 franvergara66