【算法】Levenshtein算法理解

0x55AA

算法介绍：
Levenshtein算法是计算两个字符串之间的最小编辑距离的算法，所谓的最小编辑距离就是把字符串A通过添加，删除，替换字符的方式转变成B所需要的最少步骤。俄罗斯科学家Vladimir Levenshtein在1965年提出这个概念，所以叫做Levenshtein算法。
算法的流程：
1：计算strA的长度n，strB的长度m
2：如果n=0,则最小编辑距离是m，m=0，则最小编辑距离是n
3：构造一个 (m+1)*(n+1)的矩阵Arr，并初始化矩阵的第一行和第一列分别为0-n，0-m
4：两重循环，遍历strA，在此基础上遍历strB，如果strA[i ]=strB[j]，那么cost=0，否则cost=1，判断Arr[j-1][i ]+1,Arr[j][i-1]+1,Arr[j-1][i-1]+cost的最小值，将最小值赋值给Arr[j][i ]。
5：循环结束后，矩阵的最后一个元素就是最小编辑距离。
根据以上算法流程的C++代码：

1. #include <string>
   
2. #include <iostream>
   
3. using namespace std;
   
4. 
   
5. int levenshtein(string str1,string str2);
   
6. 
   
7. void main()
   
8. {
   
9.         string str1,str2;
   
10.         cout<<"please input a string str1:"<<endl;
    
11.         cin>>str1;
    
12.         cout<<"please input a string str2:"<<endl;
    
13.         cin>>str2;
    
14.         cout<<"change from str1 to str2 needs: "<<levenshtein(str1,str2)<<endl;
    
15. }
    
16. 
    
17. int levenshtein(string str1,string str2)
    
18. {
    
19.         int n = str1.size();
    
20.         int m = str2.size();
    
21.         if ( n == 0)
    
22.                 return m;
    
23.         if ( m == 0)
    
24.                 return n;
    
25.         int **Arr = (int**)malloc( (m+1)*sizeof(int*) );
    
26.         for (int i=0;i<=m;i++)
    
27.                 Arr[i ] = (int*)malloc( (n+1)*sizeof(int) );
    
28.         int cost = 0;
    
29.         for(int i=0;i<=n;i++)
    
30.                 Arr[0][i ] = i;
    
31.         for(int j=0;j<=m;j++)
    
32.                 Arr[j][0] = j;
    
33.         for(int i=1;i<=n;i++)
    
34.                 for(int j=1;j<=m;j++)
    
35.                 {
    
36.                         if (str1[i-1] == str2[j-1])
    
37.                                 cost = 0;
    
38.                         else
    
39.                                 cost = 1;
    
40.                         Arr[j][i ] = Arr[j-1][i ]+1<Arr[j][i-1]+1?Arr[j-1][i ]+1:Arr[j][i-1] +1 ;
    
41.                         Arr[j][i ] = Arr[j][i ]<Arr[j-1][i-1]+cost?Arr[j][i ]:Arr[j-1][i-1]+cost;
    
42.                 }
    
43.         int nEdit = Arr[m][n];
    
44. 
    
45.         for(int i=0;i<=m;i++)
    
46.                 free(Arr[i ]);
    
47.         free(Arr);
    
48.        
    
49.         return nEdit;
    
50. }

复制代码

算法原理：
1：为什么要把矩阵首行以及首列初始化为0-n，0-m
我们先说说列初始化0-m表示的原因，它意思是strA从0个元素转变成strB的前i个元素的操作步骤数，这当然就很容易理解了，从一个空白的字符串转换为包含一个字符的前i个的字符的子字符串，当然需要添加i个字符了。同理，可以解释第一行初始化为0-n的原因。
2：为什么选择Arr[j-1][i ]+1,Arr[j][i-1]+1,Arr[j-1][i-1]+cost的最小值赋给Arr[j][i ]
通过1，我们应该理解这里的Arr[j][i ]表示的意思，它的意思就是strA的前i个字符转变成strB的前j个字符的最小编辑距离。
Arr[j-1][i ]表示的是strA的前i个字符转变成strB的前j-1个字符的操作步骤，那么把strA的前i个字符转变成strB的前j个字符，只需要在strA的前i个字符后面加上t[j]，所以最终操作数是Arr[j-1][i ]+1;
Arr[j][i-1]表示的是strA的前i-1个字符转变成strB的前j个字符的操作步骤，那么把strA的前i个字符转变成strB的前j个字符，只需要在strA的第i个字符删除即可，所以最终操作数是Arr[j][i-1]+1;
Arr[j-1][i-1]表示的strA的前i-1个字符转变成strB的前j-1个字符的操作步骤，那么把strA的前i个字符变成strB的前j个字符，只需要看strA的第i个字符和strB的第j个字符是否相等，相等则最终操作数是Arr[j-1][i-1]，不相等则最终操作数是Arr[j-1][i-1]+1；
以上三种根据前者转换的方法得到的结果都可能是最少的编辑距离，所以我们选择三者的最小值作为Arr[j][i ]的值。
算法实例：
strA = "acdf",strB = "abc"
     a c  d  f
  0  1 2  3  4
a 1
b 2
c 3
当i=0时，strA的前0个字符串str = null，
j = 0，str->null ，k =0,即Arr[0][0] =0;
j =1，str->a，k =1，即Arr[0][1] =1;
j =2，str->ab，k=2，即Arr[0][2]=2;
j =3，str->abc，k=3，即Arr[0][3] =3;
当 i =1时，strA的前1个字符串str = a，
j =1，str->a:strA[0,i-1]--> strB[0,j] =1(null-->a), strA[0,i]-->strB[0,j-1]=1(a->null), strA[0,i-1]-->strB[0,j-1]=0(null-->null),  从而证明了Arr[1][1] =0;
j =2，str->ab，....(同理)
j =3，str->abc，...(同理)
i=2,3,4(同理)


算法改进：
从算法的计算中我们可以看到，虽然建立了一个(m+1)×(n+1)的矩阵，但是我们每次只用到了矩阵中的两列或者两行，所以从这点来改进算法，提高算法的空间利用率。

1. int Levenshtein(string str1,string str2)
   
2. {
   
3.         int n = str1.size();
   
4.         int m = str2.size();
   
5.         if ( n == 0)
   
6.                 return m;
   
7.         if ( m == 0)
   
8.                 return n;
   
9.         vector<int> vec1(m+1);
   
10.         vector<int> vec2(m+1);
    
11.         for(int i=0;i<=m;i++)
    
12.                 vec1[i ] = i;
    
13.         int cost = 0;
    
14. 
    
15.         for(int i=1;i<=n;i++)
    
16.         {
    
17.                 vec2[0] = i;
    
18.                 for(int j=1;j<=m;j++)
    
19.                 {
    
20.                         if( str1[i-1] == str2[j-1] )
    
21.                                 cost = 0;
    
22.                         else
    
23.                                 cost = 1;
    
24.                         vec2[j] = vec2[j-1]+1 < vec1[j]+1 ? vec2[j-1]+1 : vec1[j]+1;
    
25.                         vec2[j] = vec2[j] < vec1[j-1]+cost ? vec2[j] : vec1[j-1]+cost;
    
26.                 }
    
27.                 vec1 = vec2;
    
28.         }
    
29.         return vec2.back();
    
30. }

复制代码