编辑距离java,编辑距离算法 的Java实现

编辑距离是指通过添加删除或更改字符这三种操作,由一个字符串转到另一个字符串所需的最少次数。

俄国科学家Liechtenstein在1956年首次提出了这个概念.

对于编辑距离的实现,可以通过下述方式进行计算:

假设有字符串a,b，计算由a至b的编辑距离ed(a,b)，此处设定La，Lb分别表示a,b字符串的长度

<1>La==0||Lb==0  –> ed(a,b)=La+Lb

<2>如果La,Lb都不等于0，那么 ed(a,b)=min{ed(a-1,b)+1, ed(a,b-1)+1,ed(a-1,b-1)+b(a,b)}     b(a,b)=1 if a的最后一个字符等于b的最后一个字符,否则b(a,b)=0

————————Code——————————-

package Levenshtein;

/**

* @author c0rpse * 编辑距离算法的实现 *

*/

public class Levenshtein {

public static void main(String[] args){

String a = "abc",b = "def";

System.out.println(levenshtein(a,b));

}

public static int levenshtein(String x,String y){

int xl = x.length(),yl=y.length();

if(xl==0||yl==0) return yl+xl;

String x_1=xl-1>0?x.substring(0, xl-1):"";

String y_1=yl-1>0?y.substring(0, yl-1):"";

int x__1=levenshtein(x_1,y)+1;

int y__1=levenshtein(y_1,x)+1;

int x_y=levenshtein(x_1,y_1)+(x.substring(xl-1).equals(y.substring(yl-1))?0:1);

return min(min(x__1,y__1),x_y);

}

public static int min(int x,int y)

{

return x<y?x:y;

}

}