【算法】Levenshtein算法理解
算法介绍：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=strB，那么cost=0，否则cost=1，判断Arr+1,Arr+1,Arr+cost的最小值，将最小值赋值给Arr。
5：循环结束后，矩阵的最后一个元素就是最小编辑距离。
根据以上算法流程的C++代码：#include <string>
#include <iostream>
using namespace std;
int levenshtein(string str1,string str2);
void main()
{
string str1,str2;
cout<<"please input a string str1:"<<endl;
cin>>str1;
cout<<"please input a string str2:"<<endl;
cin>>str2;
cout<<"change from str1 to str2 needs: "<<levenshtein(str1,str2)<<endl;
}
int levenshtein(string str1,string str2)
{
int n = str1.size();
int m = str2.size();
if ( n == 0)
return m;
if ( m == 0)
return n;
int **Arr = (int**)malloc( (m+1)*sizeof(int*) );
for (int i=0;i<=m;i++)
Arr = (int*)malloc( (n+1)*sizeof(int) );
int cost = 0;
for(int i=0;i<=n;i++)
Arr = i;
for(int j=0;j<=m;j++)
Arr = j;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
if (str1 == str2)
cost = 0;
else
cost = 1;
Arr = Arr+1<Arr+1?Arr+1:Arr +1 ;
Arr = Arr<Arr+cost?Arr:Arr+cost;
}
int nEdit = Arr;
for(int i=0;i<=m;i++)
free(Arr);
free(Arr);
return nEdit;
}算法原理：
1：为什么要把矩阵首行以及首列初始化为0-n，0-m
我们先说说列初始化0-m表示的原因，它意思是strA从0个元素转变成strB的前i个元素的操作步骤数，这当然就很容易理解了，从一个空白的字符串转换为包含一个字符的前i个的字符的子字符串，当然需要添加i个字符了。同理，可以解释第一行初始化为0-n的原因。
2：为什么选择Arr+1,Arr+1,Arr+cost的最小值赋给Arr
通过1，我们应该理解这里的Arr表示的意思，它的意思就是strA的前i个字符转变成strB的前j个字符的最小编辑距离。
Arr表示的是strA的前i个字符转变成strB的前j-1个字符的操作步骤，那么把strA的前i个字符转变成strB的前j个字符，只需要在strA的前i个字符后面加上t，所以最终操作数是Arr+1;
Arr表示的是strA的前i-1个字符转变成strB的前j个字符的操作步骤，那么把strA的前i个字符转变成strB的前j个字符，只需要在strA的第i个字符删除即可，所以最终操作数是Arr+1;
Arr表示的strA的前i-1个字符转变成strB的前j-1个字符的操作步骤，那么把strA的前i个字符变成strB的前j个字符，只需要看strA的第i个字符和strB的第j个字符是否相等，相等则最终操作数是Arr，不相等则最终操作数是Arr+1；
以上三种根据前者转换的方法得到的结果都可能是最少的编辑距离，所以我们选择三者的最小值作为Arr的值。
算法实例：
strA = "acdf",strB = "abc"
a cdf
01 234
a 1
b 2
c 3
当i=0时，strA的前0个字符串str = null，
j = 0，str->null ，k =0,即Arr =0;
j =1，str->a，k =1，即Arr =1;
j =2，str->ab，k=2，即Arr=2;
j =3，str->abc，k=3，即Arr =3;
当 i =1时，strA的前1个字符串str = a，
j =1，str->a:strA--> strB =1(null-->a), strA-->strB=1(a->null), strA-->strB=0(null-->null),从而证明了Arr =0;
j =2，str->ab，....(同理)
j =3，str->abc，...(同理)
i=2,3,4(同理)
算法改进：
从算法的计算中我们可以看到，虽然建立了一个(m+1)×(n+1)的矩阵，但是我们每次只用到了矩阵中的两列或者两行，所以从这点来改进算法，提高算法的空间利用率。int Levenshtein(string str1,string str2)
{
int n = str1.size();
int m = str2.size();
if ( n == 0)
return m;
if ( m == 0)
return n;
vector<int> vec1(m+1);
vector<int> vec2(m+1);
for(int i=0;i<=m;i++)
vec1 = i;
int cost = 0;
for(int i=1;i<=n;i++)
{
vec2 = i;
for(int j=1;j<=m;j++)
{
if( str1 == str2 )
cost = 0;
else
cost = 1;
vec2 = vec2+1 < vec1+1 ? vec2+1 : vec1+1;
vec2 = vec2 < vec1+cost ? vec2 : vec1+cost;
}
vec1 = vec2;
}
return vec2.back();
}
页:
[1]