【串和序列处理 2】字符串编辑距离算法

我们来看一个实际应用。现代搜索技术的发展很多以提供优质、高效的服务作为目标。比如说：baidu、google、sousou等知名全文搜索系统。当我们输入一个错误的query="Jave" 的时候，返回中有大量包含正确的拼写 "Java"的网页。当然这里面用到的技术绝对不会是我们今天讲的怎么简单。但我想说的是：字符串的相似度计算也是做到这一点的方法之一。

 

 

字符串编辑距离： 是一种字符串之间相似度计算的方法。给定两个字符串S、T，将S转换成T所需要的删除，插入，替换操作的数量就叫做S到T的编辑路径。而最短的编辑路径就叫做字符串S和T的编辑距离。

 

举个例子：S=“eeba”   T="abac"   我们可以按照这样的步骤转变：(1) 将S中的第一个e变成a;(2) 删除S中的第二个e;(3)在S中最后添加一个c; 那么S到T的编辑路径就等于3。当然，这种变换并不是唯一的，但如果3是所有变换中最小值的话。那么我们就可以说S和T的编辑距离等于3了。

 

动态规划解决编辑距离

动态规划(dynamic programming)是一种解决复杂问题最优解的策略。它的基本思路就是：将一个复杂的最优解问题分解成一系列较为简单的最优解问题，再将较为简单的的最优解问题进一步分解，直到可以一眼看出最优解为止。

 

动态规划算法是解决复杂问题最优解的重要算法。其算法的难度并不在于算法本身的递归难以实现，而主要是编程者对问题本身的认识是否符合动态规划的思想。现在我们就来看看动态规划是如何解决编辑距离的。

 

还是这个例子：S=“eeba”   T="abac" 。我们发现当S只有一个字符e、T只有一个字符a的时候，我们马上就能得到S和T的编辑距离edit(0,0)=1(将e替换成a)。那么如果S中有1个字符e、T中有两个字符ab的时候，我们是不是可以这样分解：edit(0,1)=edit(0,0)+1(将e替换成a后，在添加一个b)。如果S中有两个字符ee，T中有两个字符ab的时候，我们是不是可以分解成：edit(1,1)=min(edit(0,1)+1, edit(1,0)+1, edit(0,0)+f(1,1)). 这样我们可以得到这样一些动态规划公式：      

        如果i=0且j=0        edit(0, 0)=1

        如果i=0且j>0        edit(0, j )=edit(0, j-1)+1

        如果i>0且j=0        edit( i, 0 )=edit(i-1, 0)+1

        如果i>0且j>0        edit(i, j)=min(edit(i-1, j)+1, edit(i,j-1)+1, edit(i-1,j-1)+f(i , j) )

 

小注：edit(i,j)表示S中[0.... i]的子串 si 到T中[0....j]的子串t1的编辑距离。f(i,j)表示S中第i个字符s(i)转换到T中第j个字符s(j)所需要的操作次数，如果s(i)==s(j)，则不需要任何操作f(i, j)=0； 否则，需要替换操作，f(i, j)=1 。

 

这就是将长字符串间的编辑距离问题一步一步转换成短字符串间的编辑距离问题，直至只有1个字符的串间编辑距离为1。

 

编辑距离的实际应用

       在信息检索领域的应用我们在文章开始的时候就提到了。另外，编辑距离在自然语言文本处理领域(NLP)中是计算字符串相似度的重要方法。一般而言，对于中文语句的相似度处理，我们很多时候都是将词作为一个基本操作单位，而不是字(字符)。

 

 

字符串编辑距离源代码

package net.hr.algorithm.stroper;
/**
 * 字符串编辑距离
 * 
 * 这是一种字符串之间相似度计算的方法。
 * 给定字符串S、T，将S转换T所需要的插入、删除、替代操作的数量叫做S到T的编辑路径。
 * 其中最短的路径叫做编辑距离。
 * 
 * 这里使用了一种动态规划的思想求编辑距离。
 * 
 * @author heartraid
 *
 */
public class StrEditDistance {

	/**字符串X*/
	private String strX="";
	/**字符串Y*/
	private String strY="";
	/**字符串X的字符数组*/
	private char[] charArrayX=null;
	/**字符串Y的字符数组*/
	private char[] charArrayY=null;
	
	public StrEditDistance(String sa,String sb){
		this.strX=sa;
		this.strY=sb;
	}
	/**
	 * 得到编辑距离
	 * @return 编辑距离
	 */
	public int getDistance(){
		charArrayX=strX.toCharArray();
		charArrayY=strY.toCharArray();
		return editDistance(charArrayX.length-1,charArrayY.length-1);
}
	/**
	 * 动态规划解决编辑距离
	 * 
	 * editDistance(i,j)表示字符串X中[0.... i]的子串 Xi 到字符串Y中[0....j]的子串Y1的编辑距离。
	 * 
	 * @param i 字符串X第i个字符
	 * @param j 字符串Y第j个字符
	 * @return 字符串X(0...i)与字符串Y(0...j)的编辑距离
	 */
	private int editDistance(int i,int j){
		if(i==0&&j==0){
			//System.out.println("edit["+i+","+j+"]="+isModify(i,j));
			return isModify(i,j);
		}
		else if(i==0||j==0){
			if(j>0){
				//System.out.println("edit["+i+","+j+"]=edit["+i+","+(j-1)+"]+1");
				if(isModify(i,j) == 0) return j;
                                return editDistance(i, j-1) + 1;
			}
			else{
				//System.out.println("edit["+i+","+j+"]=edit["+(i-1)+","+j+"]+1");
				if(isModify(i,j) == 0) return i;
                                return editDistance(i-1,j)+1;
			}
		}
		else {
			//System.out.println("edit["+i+","+j+"]=min( edit["+(i-1)+","+j+"]+1,edit["+i+","+(j-1)+"]+1,edit["+(i-1)+","+(j-1)+"]+isModify("+i+","+j+")");
			int ccc=minDistance(editDistance(i-1,j)+1,editDistance(i,j-1)+1,editDistance(i-1,j-1)+isModify(i,j));
			return ccc;
		}
	
	}
	/**
	 * 求最小值
	 * @param disa 编辑距离a
	 * @param disb 编辑距离b
	 * @param disc 编辑距离c
	 */
	private int minDistance(int disa,int disb,int disc){
		int dismin=Integer.MAX_VALUE;
		if(dismin>disa) dismin=disa;
		if(dismin>disb) dismin=disb;
		if(dismin>disc) dismin=disc;
		return dismin;
	}
	/**
	 * 单字符间是否替换
	 * 
	 * isModify(i,j)表示X中第i个字符x(i)转换到Y中第j个字符y(j)所需要的操作次数。
	 * 如果x(i)==y(j)，则不需要任何操作isModify(i, j)=0； 否则，需要替换操作，isModify(i, j)=1。
	 * @param i 字符串X第i个字符
	 * @param j 字符串Y第j个字符
	 * @return 需要替换，返回1；否则，返回0
	 */
	private int isModify(int i,int j){
		if(charArrayX[i]==charArrayY[j])
			return 0;
		else return 1;
	}
	
	/**
	 * 测试
	 * @param args
	 */
	public static void main(String[] args) {	
		System.out.println("编辑距离是："+new StrEditDistance("eeba","abac").getDistance());
	}

}

评论

6 楼 yytsjzhao 2012-10-31  

if (a == null || b == null)
return 0;

// 减少内存开销
if (a.length() < b.length()) {
String c = a;
a = b;
b = c;
}

int n = a.length();
int m = b.length();

int[][] s = new int[2][m + 1];

for (int i = 0; i <= m; i++) {
s[0][i] = i;
}

for (int i = 1; i <= n; i++) {

s[1][0] = i;

for (int j = 1; j <= m; j++) {

s[1][j] = s[0][j - 1]
+ (a.charAt(i - 1) == b.charAt(j - 1) ? 0 : 1);
s[1][j] = Math.min(s[1][j], s[0][j] + 1);
s[1][j] = Math.min(s[1][j], s[1][j - 1] + 1);
}

int[] t = s[0];
s[0] = s[1];
s[1] = t;
}

return s[0][b.length()];

5 楼 yytsjzhao 2012-10-31  

能不能再改进些,现在这个效率不理想

4 楼 yytsjzhao 2012-10-31  

1L 这样改不是跟原来一样么  

3 楼 shenlan211314 2011-03-26  

除了动态规划之外，还有其他求解最优编辑距离的方法没？

2 楼 Heart.X.Raid 2010-06-25  

1L说的对，我的算法确实有问题，谢谢你指出。

1 楼 seraphim871211 2010-06-19  

算法代码似乎有点问题：

public static void main(String[] args) {	
		System.out.println("编辑距离是："+new StrEditDistance("d","abd").getDistance());
	}

输出为：   编辑距离是：3

应该将上述editDistance方法中某段代码改为：

else if(i==0||j==0){
			if(j>0){
				//System.out.println("edit["+i+","+j+"]=edit["+i+","+(j-1)+"]+1");
				int aaa;
				if(isModify(i,j) == 0)
						aaa = j;
				else
						aaa = editDistance(i, j-1) + 1;
				return aaa;
			}
			else{
				//System.out.println("edit["+i+","+j+"]=edit["+(i-1)+","+j+"]+1");
				int bbb;
				if(isModify(i,j) == 0)
					bbb = i;
				else
					bbb = editDistance(i-1,j) + 1;
				return bbb;
			}
		}