首页 > 算法 数据结构 > 字符串相似度(编辑距离)

字符串相似度(编辑距离)

2012年6月13日 发表评论 阅读评论
文章作者:Yx.Ac   文章来源:勇幸|Thinking (http://www.ahathinking.com)   转载请注明,谢谢合作。

---

个人认为,大部分情况下,DP寻找子问题还是“从后向前”比较直观一些,像这道题目,个人觉得《编程之美》对它的分析就有些别扭,它“从前向后”寻求的子问题使得状态转移矩阵的初始化变得不太方便,不过“从后向前”分析和从前向后效果和原理都是一样的,本节通过三种实现方式来加深理解。

定义字符串的相似度有很多种度量,像前面说的最长公共子序列就是其中的一种,本节所说的“编辑距离”也算是一种,简单来说,编辑距离就是将两个字符串变成相同字符串所需要的最小操作次数。所需的操作可能有:

  1. 修改一个字符(如把“a”替换为“b”)
  2. 增加一个字符(如把“abdd”变为“aebdd”)
  3. 删除一个字符(如把“travelling”变为“traveling”)

例如,对于“abcdefg”和“abcdef”两个字符串来讲,可以通过增加/减少一个“g”的方式来达到目的。上面的两种方案,都仅需要一次操作。把这个操作所需要的次数定义为两个字符串的“编辑距离”。如何计算两个字符串的“编辑距离”?

鉴于DP自底向上求解子问题的性质,我们还是对字符串从后向前分析,这样寻找编辑距离的子问题比较直观,而且分解的子问题使得递归做备忘录变得容易理解,也使得自底向上实现时对状态转移矩阵的初始化更为简便易懂。

寻找子问题时,我们完全可以像分析最长公共子序列那样分析这个问题,我觉得它们是灰常相似的,都是“从后向前”看,假设有两个串X=abcdaex,Y=fdfax,它们的最后一个字符是相同的,只要计算X[1,…,6]=abcdae和Y[1,…,4]=fdfa的距离就可以了;但是如果两个串的最后一个字符不相同,那么就可以进行如下的操作来达到目的(xlen和ylen是X串和Y串的长度):

  1. 一步操作之后,再计算X[1,…,xlen-1]和Y[1,…ylen]的距离。这个操作可以是删除X的最后一个字符,也可以是增加X串的最后一个字符到Y串的最后字符之后
  2. 一步操作之后,再计算X[1,…,xlen]和Y[1,…ylen-1]的距离。这个操作与情况1类似,反过来而已
  3. 一步操作之后,再计算X[1,…,xlen-1]和Y[1,…ylen-1]的距离。这个操作可以是修改X串的最后有一个字符为Y串的最后一个字符,后者修改Y的变为X的最后一个字符,使得二者相同。

注意:我们计算编辑距离,并不需要关心两个字符串相等之后是怎样的,也不需要具体采取了什么操作,只是需要知道操作次数就可以,所以经过上面的分析,我们就可以尝试写状态方程了,这个的初始状态就是当两个串的长度都为0,那么编辑距离就是0,所以与最长公共子序列一样,dp[i][j]中的i和j表示串X和Y的长度,其中,如果某一个串的长度为0,则编辑距离就是另一个串的长度,这很容易理解。状态转移方程为

  1. dp[i][j] = 0  如果i=0 & j=0
  2. dp[i][j] = xlen | ylen  如果j=0 | i=0
  3. dp[i][j] = dp[i-1][j-1]  如果X[i-1] = Y[i-1]
  4. dp[i][j] = 1 + min{ dp[i-1][j], dp[i][j-1], dp[i-1][j-1] }  如果X[i-1] != Y[i-1]

好,到这里问题就解决了一半,代码如下,本节给出了三种实现方式,第一种是根据分析给出的递归搜索方法;由于具有重叠子问题,所以第二种方法便是使用了备忘录的递归方法(注:分治与动态规划的重要区别就是分治递归不断产生新的子问题,没有重叠子问题;而DP则是在递归不断产生子问题的同时很多子问题是重复计算的,即重叠子问题);第三种便是根据状态转移方程给出了自底向上的实现,这也是最符合DP性质的实现方式。

方法一:简单递归搜索:

/* 递归搜索 */
int calDistance1(char *ptrX, int xbeg, int xend, char *ptrY, int ybeg, int yend)
{
	if(xbeg > xend)
	{
		if(ybeg > yend)
			return 0;
		else
			return yend - ybeg + 1;
	}
	if(ybeg > yend)
	{
		if(xbeg > xend)
			return 0;
		else
			return xend - xbeg + 1;
	}
	if(ptrX[xend] == ptrY[yend])
	{
		return calDistance1(ptrX,xbeg,xend-1,ptrY,ybeg,yend-1);
	}else
	{
		int t1 = calDistance1(ptrX,xbeg,xend-1,ptrY,ybeg,yend);
		int t2 = calDistance1(ptrX,xbeg,xend,ptrY,ybeg,yend-1);
		int t3 = calDistance1(ptrX,xbeg,xend-1,ptrY,ybeg,yend-1);
		t1 = t1 < t2 ? t1 : t2;
		return (t1 < t3 ? t1 : t3) + 1;
	}
}

方法二:递归+备忘录:

/* 编辑距离
 * 设每个字符串长度不超过 30
*/

/* 存储子问题的解 i,j表示X,Y长度
 * dp[i][j]表示X[0-i)与Y[0-j)的编辑距离
*/
int dp[31][31];
/* 自顶向下 & 备忘录 */
int calDistance2(char *ptrX, int xbeg, int xend, char *ptrY, int ybeg, int yend)
{
	if(xend == 0)
	{
		if(yend == 0)
			return 0;
		else
			return yend - ybeg + 1;
	}
	if(yend == 0)
	{
		if(xend == 0)
			return 0;
		else
			return xend - xbeg + 1;
	}
	if(ptrX[xend-1] == ptrY[yend-1])
	{
		if(dp[xend-1][yend-1] == 0)
		{
			dp[xend-1][yend-1] = calDistance2(ptrX,xbeg,xend-1,ptrY,ybeg,yend-1);
		}
		return dp[xend-1][yend-1];
	}else
	{
		int t1, t2, t3;
		if(dp[xend-1][yend] == 0)
		{
			dp[xend-1][yend] = calDistance2(ptrX,xbeg,xend-1,ptrY,ybeg,yend);
		}
		t1 = dp[xend-1][yend];
		if(dp[xend][yend-1] == 0)
		{
			dp[xend][yend-1] = calDistance2(ptrX,xbeg,xend,ptrY,ybeg,yend-1);
		}
		t2 = dp[xend][yend-1];
		if(dp[xend-1][yend-1] == 0)
		{
			dp[xend-1][yend-1] = calDistance2(ptrX,xbeg,xend-1,ptrY,ybeg,yend-1);
		}
		t3 = dp[xend-1][yend-1];
		t1 = t1 < t2 ? t1 : t2;
		return (t1 < t3 ? t1 : t3) + 1;
	}
}

方法三:自底向上DP:

/* 编辑距离
 * 设每个字符串长度不超过 30
*/

/* 存储子问题的解 i,j表示X,Y长度
 * dp[i][j]表示X[0-i)与Y[0-j)的编辑距离
*/
int dp[31][31];
char X[31];
char Y[31];
/* 自底向上 DP */
int calDistance3(char *ptrX, int xlen, char *ptrY, int ylen)
{
	int i, j;
	for(i = 1; i <= xlen; ++i)
	{
		dp[i][0] = i;
	}
	for(j = 1; j <= ylen; ++j)
	{
		dp[0][j] = j;
	}
	for(i = 1; i <= xlen; ++i)
	{
		for(j = 1; j <= ylen; ++j)
		{
			if(ptrX[i-1] == ptrY[j-1])
			{
				dp[i][j] = dp[i-1][j-1];
			}else
			{
				int t1 = dp[i-1][j];
				t1 = t1 < dp[i][j-1] ? t1 :dp[i][j-1];
				t1 = t1 < dp[i-1][j-1] ? t1 : dp[i-1][j-1];
				dp[i][j] = t1 + 1;
			}
		}
	}
	return dp[xlen][ylen];
}

给出测试用例:

#include <iostream>
using namespace std;
void main()
{
	cin.getline(X,30);
	cin.getline(Y,30);

	int xlen = strlen(X);
	int ylen = strlen(Y);

	printf("%d\n",calDistance1(X,0,xlen-1,Y,0,ylen-1));
	//printf("%d\n",calDistance2(X,0,xlen,Y,0,ylen));
	printf("%d\n",calDistance3(X,xlen,Y,ylen));
}

本文相关代码可以到这里下载。

(全文完)

参考资料:《编程之美》 3.3

  • http://www.ahathinking.com/archives/116.html Austindglx

    楼主的思想非常的清晰,学到了不少~赞一个
    但是感觉楼主的函数和代码设计的不是特别的简洁,贴上自己的一段来,欢迎拍砖~~
    楼主的思想是从后往前计算编辑距离,本人代码是从前往后进行计算~不要误会~

    //直接递归会有很多重叠子问题,采用备忘录
    int dp[101][101]; //最多处理长度为100的字符串
    void InitDP(){ //初始化备忘录,在每次调用编辑距离函数前应该调用一次
    	for(int i =0 ; i<100; i++){
    		for(int j = 0; j<100; j++)
    			dp[i][j] = 0;
    	}
    	for(int i = 0; i<100; i++){
    		dp[0][i] = i;
    		dp[i][0] = i;
    	}
    }
    
    int EditDistance(char *s1, char* s2){
    	if(s1==NULL || s2==NULL ) return 0;
    
    	int len1 = strlen(s1), len2 = strlen(s2);
    	if(len1 == 0 || len2==0) return dp[len1][len2];
    
    	if(dp[len1][len2] == 0){
    		if(*s1 == *s2){
    			dp[len1][len2] = EditDistance(s1+1,s2+1);
    		}
    		else{
    			dp[len1][len2] = min(1+EditDistance(s1,s2+1),min(1+EditDistance(s1+1,s2),1+EditDistance(s1+1,s2+1)));
    		}
    	}
    	return dp[len1][len2];
    }
    
    • Yx.Ac

      nice~ :-)

  • Yx.Ac

    恩恩,好滴@NeverAskWho

  • NeverAskWho

    nice,不论是从后向前,还是从前向后,都是不错的思路。我亦好从后向前分析.
    我记得算法导论上有一个DP例子是优化矩阵乘法(结合律)。那个例子中的总复杂度为Catalan数,并且那道例子中,分析既非从强而后,亦非从后而前,而是从中间走的,有时间可以去瞧瞧那个例子.