编辑距离，如何计算大量字符串间的编辑距离

本文目录一览

1，如何计算大量字符串间的编辑距离
2，字符串编辑距离问题
3，编辑距离算法

1，如何计算大量字符串间的编辑距离

模拟构造一个（m + 1)行，（n+1）列的表格每一次都是在前一次的计算结果下，得到当前的值首先是三个特殊情况用srcStr表示源字符串，dstStr 表示目标字符串1) 两个空字符串的编辑距离D(srcStr, dstStr) = 02) 如果srcStr为空，dstStr不为空，则D(srcStr, dstStr) = dstStr.length(), 即在原空字符串上添加字符，形成dstStr3) 如果dstStr为空，srcStr不为空，则D(srcStr, dstStr) = srcStr.length(), 及在源字符串上删除其所有字符，直至为空

如何计算大量字符串间的编辑距离

2，字符串编辑距离问题

定义字符串的基本操作为：删除一个字符＼插入一个字符和将一个字符修改成另外一个字符这三种操作。将字符串A变成字符串B的最少操作步数，称为字符串A到字符串B的编辑距离。字符串“ABCDEFG”到字符串“BADECG”的编辑距离为_____。正确答案： 3

你的第二步就错了。原来的字母B去哪了？ABCDEFG-原来BCDEFG-去掉ABDEFG-去掉CBADEFG-插入ABADECG-替换F为C我这种做法的编辑距离是4。也不是电脑编程问题，还是训练思维。

编辑距离为3abcdefg 删除a 得出 bcdefg (a→) bcdefg 将c替换成a 得出 badefg (c→a) badefg 将f替换成c 得出badecg (f→c)

字符串编辑距离问题

3，编辑距离算法

编辑距离是3，楼主看一下这篇博文：http://www.cnblogs.com/biyeymyhjob/archive/2012/09/28/2707343.html也附有代码，可以试运行一下，动态规划求解

#include<stdio.h>#include<stdlib.h>#include<string.h>int_min(inta,intb,intc)intmin=a;if(b<min)min=b;if(c<min)min=c;returnmin;}intcomputedistance(chars[],chart[])intn=strlen(s);intm=strlen(t);//intd[][]=newint[n+1,m+1];//matrixint**d=(int**)malloc((n+1)*sizeof(int*));for(inti=0;i<=n;++i)d[i]=(int*)malloc((m+1)*sizeof(int));}//step1if(n==0)returnm;}if(m==0)returnn;}//step2for(inti=0;i<=n;i++)d[i][0]=i;}for(intj=0;j<=m;d[0][j]=j++)d[0][j]=j;}//step3for(inti=1;i<=n;i++)//step4for(intj=1;j<=m;j++)//step5intcost=(t[j-1]==s[i-1])?0:1;//step6d[i][j]=_min(d[i-1][j]+1,d[i][j-1]+1,d[i-1][j-1]+cost);}}//step7returnd[n][m];}intmain(intargc,char*argv[])chara[9999];charb[9999];printf("请输入字符串1\n");scanf("%s",&a);printf("请输入字符串2\n");scanf("%s",&b);intresult=computedistance(a,b);printf("%d\n",result);system("pause");return0;}////////////////////refrence:dynamicprogrammingalgorithm(dpa)foredit-distance编辑距离关于两个字符串s1,s2的差别，可以通过计算他们的最小编辑距离来决定。所谓的编辑距离:让s1和s2变成相同字符串需要下面操作的最小次数。1.把某个字符ch1变成ch22.删除某个字符3.插入某个字符例如s1=“12433”和s2=”1233”;则可以通过在s2中间插入4得到12433与s1一致。即d(s1,s2)=1(进行了一次插入操作)编辑距离的性质计算两个字符串s1+ch1,s2+ch2的编辑距离有这样的性质:1.d(s1,””)=d(“”,s1)=|s1|d(“ch1”,”ch2”)=ch1==ch2?0:1;2.d(s1+ch1,s2+ch2)=min(d(s1,s2)+ch1==ch2?0:1,d(s1+ch1,s2),d(s1,s2+ch2));第一个性质是显然的。第二个性质:由于我们定义的三个操作来作为编辑距离的一种衡量方法。于是对ch1,ch2可能的操作只有1.把ch1变成ch22.s1+ch1后删除ch1d=(1+d(s1,s2+ch2))3.s1+ch1后插入ch2d=(1+d(s1+ch1,s2))对于2和3的操作可以等价于:_2.s2+ch2后添加ch1d=(1+d(s1,s2+ch2))_3.s2+ch2后删除ch2d=(1+d(s1+ch1,s2))因此可以得到计算编辑距离的性质2。复杂度分析从上面性质2可以看出计算过程呈现这样的一种结构(假设各个层用当前计算的串长度标记，并假设两个串长度都为n)可以看到，该问题的复杂度为指数级别3的n次方，对于较长的串，时间上是无法让人忍受的。分析:在上面的结构中，我们发现多次出现了(n-1,n-1),(n-1,n-2)……。换句话说该结构具有重叠子问题。再加上前面性质2所具有的最优子结构。符合动态规划算法基本要素。因此可以使用动态规划算法把复杂度降低到多项式级别。动态规划求解首先为了避免重复计算子问题，添加两个辅助数组。一.保存子问题结果。m[|s1|,|s2|],其中m[i,j]表示子串s1(0->i)与s2(0->j)的编辑距离二.保存字符之间的编辑距离.e[|s1|,|s2|],其中e[i,j]=s[i]=s[j]?0:1三.新的计算表达式根据性质1得到m[0,0]=0;m[s1i,0]=|s1i|;m[0,s2j]=|s2j|;根据性质2得到m[i,j]=min(m[i-1,j-1]+e[i,j],m[i,j-1],m[i-1,j]);复杂度从新的计算式看出，计算过程为i=1->|s1|j=1->|s2|m[i][j]=……因此复杂度为o(|s1|*|s2|)，如果假设他们的长度都为n，则复杂度为o(n^2)

编辑距离算法