`

【串和序列处理 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
0
分享到:
评论
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;
			}
		}

相关推荐

    计算两个字符串的编辑距离 -- 快速算法

    原始的Wagner-Fischer算法使用一个二维数组dp,其中dp[i][j]表示字符串S的前i个字符与字符串T的前j个字符的最小编辑距离。通过维护一个滚动窗口,我们可以只存储最后两行的数组状态,从而将空间复杂度从O(m * n)...

    计算两字符串的编辑距离

    编辑距离,又称Levenshtein距离,是一种衡量两个字符串相似度的指标,广泛应用于文本处理、数据校验、搜索引擎优化等多个领域。这个概念源于俄国科学家瓦迪姆·列文斯坦在1965年提出,它定义了将一个字符串转换成另...

    字符串相似度算法 levenshtein distance 编辑距离算法

    **字符串相似度算法——...总的来说,编辑距离算法提供了一种量化比较字符串相似度的有效手段,是理解和处理文本数据的重要工具。在阅读提供的“ld.htm”文件后,可以更深入地了解这个算法的实现细节和实际应用案例。

    Python-Levenshtein快速计算编辑距离以及字符串的相似度

    在Python编程环境中,Levenshtein库是一个非常实用的工具,用于计算两个字符串之间的编辑距离。编辑距离,也称为Levenshtein距离,是衡量两个字符串差异的一种度量,定义为由一个字符串转换成另一个字符串最少的单...

    java-string-similarity, 各种字符串相似性和距离算法.zip

    java-string-similarity, 各种字符串相似性和距离算法 java-string-similarity 实现不同字符串相似度和距离度量的库。 目前已经实现了许多算法( 包括Levenshtein编辑距离和 sibblings,jaro winkler,最长公共子序列...

    字符串相似度比较算法

    Levenshtein 距离(也称为编辑距离)是衡量两个字符串之间最少单字符编辑操作(插入、删除、替换)次数的方法。例如,将 "kitten" 变为 "sitting" 需要3次操作:将 "k" 替换为 "s",将 "e" 替换为 "i",并在末尾...

    算法-动态规划- 线性 DP- 字符串编辑距离(包含源程序).rar

    在字符串编辑距离问题中,我们可以使用线性动态规划来构建一个二维数组dp,其中dp[i][j]表示字符串1的前i个字符和字符串2的前j个字符的最小编辑距离。数组的每一行和每一列分别对应两个字符串的一个字符,而数组的每...

    VC实现字符串编辑距离计算

    在实际应用中,字符串编辑距离广泛应用于拼写检查、DNA序列比对、文本相似度分析等领域。通过理解并实现这个算法,开发者可以有效地处理字符串相关的相似度问题。 在提供的压缩包文件"字符串编辑距离"中,可能包含...

    编辑距离JS算法

    通过以上分析,我们可以看出,编辑距离算法是衡量字符串相似度的一种有效方法。在实际应用中,根据具体需求选择合适的实现方式和优化方案尤为重要。例如,在大规模数据处理中,可以考虑使用更高效的算法变体或其他...

    编辑距离问题算法分析

    编辑距离问题是一个经典的计算机科学问题,它涉及到字符串的相似度计算和序列的比较。这个问题的主要目标是找到将一个字符串转换成另一个...通过理解和实现编辑距离算法,我们可以更好地理解和处理字符串相似度的问题。

    字符串相似度算法

    在IT领域,字符串相似度算法是一种非常重要的工具,特别是在数据挖掘、信息检索、文本分类以及自然语言处理等应用中。这个小例子旨在介绍如何通过计算字符串间的相似度来进行模糊匹配。我们将探讨几种常见的字符串...

    字符串算法

    5. **动态规划**:在字符串问题中,动态规划常用于解决最短编辑距离(Levenshtein Distance)、最长公共子序列(Longest Common Subsequence)等。这些问题可以通过构建二维状态转移表来解决,从而找出最优解。 6. ...

    编辑距离原代码 根据编的

    编辑距离算法的基本思想是通过插入、删除和替换操作来转换一个字符串成另一个字符串,计算这些操作的最小次数。这个算法的核心在于动态规划,它解决了如何在两个字符串之间找到最短的编辑路径的问题。《算法导论》是...

    公共子序列-查找两个字符序列的所有公共子序列

    在计算机科学领域,"公共子序列"(Common Subsequence)是一个重要的概念,特别是在字符串处理、序列比对和生物信息学中。本主题聚焦于查找两个字符序列的所有公共子序列,这意味着我们要找出那些既存在于字符串A中...

    最长公共子序列与最小编辑距离-你有更快的算法么?,排序算法数据结构

    最小编辑距离(Minimum Edit Distance, MED)是指将一个字符串转换成另一个字符串所需要的最少编辑操作次数,这些编辑操作包括插入、删除和替换字符。 ##### 2.2 动态规划算法 最小编辑距离也可以通过动态规划方法...

    编辑距离算法例子

    总的来说,编辑距离算法是理解和实现的重要工具,它能够帮助我们处理字符串的相似度问题,提高用户体验,特别是在搜索、纠错和自动建议等功能中。在分析`test`文件中的具体实现时,我们可以更深入地了解这个算法如何...

    ACM-字符串处理专练

    9. **编辑距离**(Edit Distance):衡量两个字符串之间的相似度,常用于拼写检查、DNA序列比对等场景。 10. **字符串分解**:如找到字符串的所有子串、所有子序列,或者按特定规则分割字符串,如通过分隔符进行...

    2007年图书:字符串的算法

    《字符串的算法》是2007年出版的一本专业图书,主要探讨了字符串处理中的各种算法和技术。这本书原版为英文,具有高清晰度的PDF格式,为读者提供了优质的阅读体验。在IT领域,字符串处理是计算机科学的一个重要组成...

    Delphi计算字符串的相似度

    1. **Levenshtein距离**:也称为编辑距离,它计算的是从一个字符串转换为另一个字符串所需的最少单字符编辑(插入、删除或替换)次数。在Delphi中,你可以实现一个动态规划的算法来计算Levenshtein距离。 2. **...

    fasta算法,Smith-waterman算法,编辑距离算法,最长公共子串算法

    `fasta`算法、`Smith-Waterman`(SW)算法、编辑距离算法以及最长公共子串算法都是这一领域中常用的序列比对方法。下面将详细介绍这些算法。 1. **fasta算法** `fasta`算法是一种快速的全局序列比对方法,由Pearson...

Global site tag (gtag.js) - Google Analytics