编辑距离算法 的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&gt;0?x.substring(0, xl-1):"";

 String y_1=yl-1&gt;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&lt;y?x:y;

}

}