学步园

编程之美---计算字符串的相似度

      在比较字符串是否相同时，我们经常要考虑两个字符串的编辑距离，所谓编辑距离就是通过修改、删除、插入等三种操作使两个字符串相等所需要的步数。字符串的相似度定义为编辑距离加1 的倒数。具体分析过程在此不再赘述。

      在编程之美中提出了递归的解决方法，但是在递归过程中有子问题被重复计算，因此在参考[1]算法引论书中提到了动态规划的思想解决该问题，在字符串比较过程中存在解最优子问题的情况，因此动态规划适用于此处。为了避免重复计算，把子问题的解存储起来。

递归代码如下：

int minmal(int a,int b,int c)<br /> {<br /> int min;<br /> if(a < b) min = a;<br /> else min = b;<br /> if(min > c) min = c;<br /> return min;<br /> }<br /> int calStringDis(string strA, int pABegin,int pAEnd,string strB, int pBBegin,int pBEnd)<br /> {<br /> if (pABegin > pAEnd)<br /> {<br /> if (pBBegin > pBEnd)<br /> return 0;<br /> else<br /> return pBEnd - pBBegin + 1;<br /> }<br /> if (pBBegin > pBEnd)<br /> {<br /> if(pABegin > pAEnd)<br /> return 0;<br /> else<br /> return pAEnd - pABegin + 1;<br /> }<br /> if (strA[pABegin] == strB[pBBegin])<br /> {<br /> return calStringDis(strA,pABegin+1,pAEnd,strB,pBBegin+1,pBEnd);<br /> }<br /> else<br /> {<br /> int t1 = calStringDis(strA,pABegin+1,pAEnd,strB,pBBegin+2,pBEnd);<br /> int t2 = calStringDis(strA,pABegin+2,pAEnd,strB,pBBegin+1,pBEnd);<br /> int t3 = calStringDis(strA,pABegin+2,pAEnd,strB,pBBegin+2,pBEnd);</p> <p> return minmal(t1,t2,t3) +1;<br /> }<br /> }

//动态规划计算编辑距离<br /> int ASM(string p,string t,int m, int n)<br /> {<br /> int i,j;</p> <p> int ** D = new int * [m+1];<br /> for (i = 0;i <= m;i++)<br /> {<br /> D[i] = new int[n+1];<br /> }</p> <p> for (j = 1;j <= n;j++)<br /> D[0][j] = 0;<br /> for(i = 0;i <= m;i++)<br /> D[i][0] = i;</p> <p> for (j = 1;j <= n; j++)<br /> {<br /> for (i =1; i <= m;i++)<br /> {<br /> if(p[i] == t[j])<br /> D[i][j] = minmal(D[i-1][j-1],D[i-1][j]+1,D[i][j-1]+1);<br /> else<br /> D[i][j] = minmal(D[i-1][j-1]+1,D[i-1][j]+1,D[i][j-1]+1);<br /> }<br /> }</p> <p> return D[m][n];<br /> }

在上述两个算法的运行结果中，我遇到了一个问题，对于一些字符串的计算结果是不同的，比如"kitting"和"sittin"我想了很长时间也没想明白怎么回事，希望高手指点，谢谢！