来源:http://wdhdmx.iteye.com/blog/1343856
1.百度百科介绍:
Levenshtein 距离,又称编辑距离,指的是两个字符串之间,由一个转换成另一个所需的最少编辑操作次数。
许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。
编辑距离的算法是首先由俄国科学家Levenshtein提出的,故又叫Levenshtein Distance。
2.用途
模糊查询
3.实现过程
a.首先是有两个字符串,这里写一个简单的 abc和abe
b.将字符串想象成下面的结构。
A处 是一个标记,为了方便讲解,不是这个表的内容。
abc | a | b | c | |
abe | 0 | 1 | 2 | 3 |
a | 1 | A处 | ||
b | 2 | |||
e | 3 |
c.来计算A处 出得值
它的值取决于:左边的1、上边的1、左上角的0.
按照Levenshtein distance的意思:
上面的值和左面的值都要求加1,这样得到1+1=2。
A处 由于是两个a相同,左上角的值加0.这样得到0+0=0。
这是后有三个值,左边的计算后为2,上边的计算后为2,左上角的计算为0,所以A处 取他们里面最小的0.
d.于是表成为下面的样子
abc | a | b | c | |
abe | 0 | 1 | 2 | 3 |
a | 1 | 0 | ||
b | 2 | B处 | ||
e | 3 |
在B处 会同样得到三个值,左边计算后为3,上边计算后为1,在B处 由于对应的字符为a、b,不相等,所以左上角应该在当前值的基础上加1,这样得到1+1=2,在(3,1,2)中选出最小的为B处的值。
e.于是表就更新了
abc | a | b | c | |
abe | 0 | 1 | 2 | 3 |
a | 1 | 0 | ||
b | 2 | 1 | ||
e | 3 | C处 |
C处 计算后:上面的值为2,左边的值为4,左上角的:a和e不相同,所以加1,即2+1,左上角的为3。
在(2,4,3)中取最小的为C处 的值。
f.于是依次推得到
a | b | c | ||
0 | 1 | 2 | 3 | |
a | 1 | A处 0 | D处 1 | G处 2 |
b | 2 | B处 1 | E处 0 | H处 1 |
e | 3 | C处 2 | F处 1 | I处 1 |
I处: 表示abc 和abe 有1个需要编辑的操作。这个是需要计算出来的。
同时,也获得一些额外的信息。
A处: 表示a 和a 需要有0个操作。字符串一样
B处: 表示ab 和a 需要有1个操作。
C处: 表示abe 和a 需要有2个操作。
D处: 表示a 和ab 需要有1个操作。
E处: 表示ab 和ab 需要有0个操作。字符串一样
F处: 表示abe 和ab 需要有1个操作。
G处: 表示a 和abc 需要有2个操作。
H处: 表示ab 和abc 需要有1个操作。
I处: 表示abe 和abc 需要有1个操作。
g.计算相似度
先取两个字符串长度的最大值maxLen,用1-(需要操作数除maxLen),得到相似度。
例如abc 和abe 一个操作,长度为3,所以相似度为1-1/3=0.666。
#include <iostream> #include <string> using namespace std; int minValue(int a,int b,int c) { if (a>b) { return b>c? c:b; } else { return a>c? c:a; } } //这个方法是编程之美的递归方法。 int calStringDis(string strA, int pABegin,int pAEnd,string strB, int pBBegin,int pBEnd) { if (pABegin > pAEnd) { if (pBBegin > pBEnd) return 0; else return pBEnd - pBBegin + 1; } if (pBBegin > pBEnd) { if(pABegin > pAEnd) return 0; else return pAEnd - pABegin + 1; } if (strA[pABegin] == strB[pBBegin]) { return calStringDis(strA,pABegin+1,pAEnd,strB,pBBegin+1,pBEnd); } else { int t1 = calStringDis(strA,pABegin,pAEnd,strB,pBBegin+1,pBEnd); int t2 = calStringDis(strA,pABegin+1,pAEnd,strB,pBBegin,pBEnd); int t3 = calStringDis(strA,pABegin+1,pAEnd,strB,pBBegin+1,pBEnd); return minValue(t1,t2,t3)+1; } } //Levenshtein算法实现求编辑距离 int calStringDistance(string &str1,string &str2) { int len1,len2; len1=str1.length(); len2=str2.length(); int i,j; if (len1==0) { return len2; } if (len2==0) { return len1; } int **c=new int *[len2+1]; for (i=0;i<=len2;i++) { c[i]=new int[len1+1]; } c[0][0]=0; for (i=1;i<=len2;i++) { c[i][0]=i; } for (j=1;j<=len1;j++) { c[0][j]=j; } for (i=1;i<=len2;i++) { for (j=1;j<=len1;j++) { if (str2[i-1]==str1[j-1]) { c[i][j]=minValue(c[i-1][j-1],c[i-1][j]+1,c[i][j-1]+1); } else { c[i][j]=minValue(c[i-1][j-1]+1,c[i-1][j]+1,c[i][j-1]+1); } } } return c[len2][len1]; } int main() { string str1="abcd"; string str2="bcdef"; cout<<calStringDis(str1,0,str1.length()-1,str2,0,str2.length()-1)<<endl; cout<<calStringDistance(str1,str2)<<endl; return 0; }
一个更加快速高效的Levenshtein算法http://www.cnblogs.com/ymind/archive/2012/03/27/fast-memory-efficient-Levenshtein-algorithm.html
说明
原来的算法是创建一个大小为StrLen1*StrLen2的矩阵。如果所有字符串加起来是1000个字符那么长的话,那么这个矩阵就会是1M;如果字符串是10000个字符,那么矩阵就是100M。如果元素都是整数(这里是指数字,Int32)的话,那么矩阵就会是4*100M == 400MB这么大,唉……
现在的算法版本只使用2*StrLen个元素,这使得后面给出的例子成为2*10,000*4 = 80 KB。其结果是,不但内存占用更少,而且速度也变快了!因为这使得内存分配只需要很少的时间来完成。当两个字符串的长度都是1k左右时,新算法的效率是旧算法的两倍!
示例
原来的版本将会创建一个矩阵[6+1, 5+1],而我的新算法将会创建两个向量[6+1](黄色元素)。在这两个算法版本中,字符串的顺序是无关紧要、无所谓的,也就是说,它也可以是矩阵[5+1, 6+1]和两个向量[5+1]。
新的算法
步骤
步骤 | 说明 |
---|---|
1 | 设置n为字符串s的长度。("GUMBO") 设置m为字符串t的长度。("GAMBOL") 如果n等于0,返回m并退出。 如果m等于0,返回n并退出。 构造两个向量v0[m+1] 和v1[m+1],串联0..m之间所有的元素。 |
2 | 初始化 v0 to 0..m。 |
3 | 检查 s (i from 1 to n) 中的每个字符。 |
4 | 检查 t (j from 1 to m) 中的每个字符 |
5 | 如果 s[i] 等于 t[j],则编辑代价为 0; 如果 s[i] 不等于 t[j],则编辑代价为1。 |
6 | 设置单元v1[j]为下面的最小值之一: a、紧邻该单元上方+1:v1[j-1] + 1 b、紧邻该单元左侧+1:v0[j] + 1 c、该单元对角线上方和左侧+cost:v0[j-1] + cost |
7 | 在完成迭代 (3, 4, 5, 6) 之后,v1[m]便是编辑距离的值。 |
本小节将演示如何计算"GUMBO"和"GAMBOL"两个字符串的Levenshtein距离。
步骤1、2
v0 | v1 | |||||
G | U | M | B | O | ||
0 | 1 | 2 | 3 | 4 | 5 | |
G | 1 | |||||
A | 2 | |||||
M | 3 | |||||
B | 4 | |||||
O | 5 | |||||
L | 6 |
步骤3-6,当 i = 1
v0 | v1 | |||||
G | U | M | B | O | ||
0 | 1 | 2 | 3 | 4 | 5 | |
G | 1 | 0 | ||||
A | 2 | 1 | ||||
M | 3 | 2 | ||||
B | 4 | 3 | ||||
O | 5 | 4 | ||||
L | 6 | 5 |
步骤3-6,当 i = 2
v0 | v1 | |||||
G | U | M | B | O | ||
0 | 1 | 2 | 3 | 4 | 5 | |
G | 1 | 0 | 1 | |||
A | 2 | 1 | 1 | |||
M | 3 | 2 | 2 | |||
B | 4 | 3 | 3 | |||
O | 5 | 4 | 4 | |||
L | 6 | 5 | 5 |
步骤3-6,当 i = 3
v0 | v1 | |||||
G | U | M | B | O | ||
0 | 1 | 2 | 3 | 4 | 5 | |
G | 1 | 0 | 1 | 2 | ||
A | 2 | 1 | 1 | 2 | ||
M | 3 | 2 | 2 | 1 | ||
B | 4 | 3 | 3 | 2 | ||
O | 5 | 4 | 4 | 3 | ||
L | 6 | 5 | 5 | 4 |
步骤3-6,当 i = 4
v0 | v1 | |||||
G | U | M | B | O | ||
0 | 1 | 2 | 3 | 4 | 5 | |
G | 1 | 0 | 1 | 2 | 3 | |
A | 2 | 1 | 1 | 2 | 3 | |
M | 3 | 2 | 2 | 1 | 2 | |
B | 4 | 3 | 3 | 2 | 1 | |
O | 5 | 4 | 4 | 3 | 2 | |
L | 6 | 5 | 5 | 4 | 3 |
步骤3-6,当 i = 5
v0 | v1 | |||||
G | U | M | B | O | ||
0 | 1 | 2 | 3 | 4 | 5 | |
G | 1 | 0 | 1 | 2 | 3 | 4 |
A | 2 | 1 | 1 | 2 | 3 | 4 |
M | 3 | 2 | 2 | 1 | 2 | 3 |
B | 4 | 3 | 3 | 2 | 1 | 2 |
O | 5 | 4 | 4 | 3 | 2 | 1 |
L | 6 | 5 | 5 | 4 | 3 | 2 |
步骤7
编辑距离就是矩阵右下角的值,v1[m] == 2。由"GUMBO"变换为"GAMBOL"的过程对于我来说是很只管的,即通过将"A"替换为"U",并在末尾追加"L"这样子(实际上替换的过程是由移除和插入两个操作组合而成的)。
改良
如果您确信你的字符串永远不会超过2^16(65536)个字符,那么你可以使用ushort来表示而不是int,如果字符串少于2^8个,还可以使用byte。我觉得这个算法用非托管代码实现的话可能会更快,但我没有试过。