编辑距离（Edit Distance）

这个算法是我面试的时候遇到了，觉得很有趣，也很实用，故收纳到我的记录中。

原理

百度百科的解释：
编辑距离（Edit Distance），又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。一般来说，编辑距离越小，两个串的相似度越大。
例如将kitten一字转成sitting：
sitten （k→s）
sittin （e→i）
sitting （→g）

算法

还是百度百科的例子，比如要计算cafe和coffee的编辑距离。cafe→caffe→coffe→coffee
先创建一个6×8的表（cafe长度为4，coffee长度为6，各加2）

接着，在如下位置填入数字（表2）：

从3,3格开始，开始计算。取以下三个值的最小值：
如果最上方的字符等于最左方的字符，则为左上方的数字。否则为左上方的数字+1。（对于3,3来说为0）
左方数字+1（对于3,3格来说为2）
上方数字+1（对于3,3格来说为2）

按照这个原理，我们得出下表：

Java实现

原理很简单，我们看看在Java怎么实现。

public static int ld(String s, String t) {  
    int d[][];                                
    int sLen = s.length();  
    int tLen = t.length();  
    int si;   
    int ti;   
    char ch1;  
    char ch2;  
    int cost;  
    if(sLen == 0) {  
        return tLen;  
    }  
    if(tLen == 0) {  
        return sLen;  
    }  
    d = new int[sLen+1][tLen+1];  
    for(si=0; si<=sLen; si++) {  
        d[si][0] = si;  
    }  
    for(ti=0; ti<=tLen; ti++) {  
        d[0][ti] = ti;  
    }  
    for(si=1; si<=sLen; si++) {  
        ch1 = s.charAt(si-1);  
        for(ti=1; ti<=tLen; ti++) {  
            ch2 = t.charAt(ti-1);  
            if(ch1 == ch2) {  
                cost = 0;  
            } else {  
                cost = 1;  
            }  
            d[si][ti] = Math.min(Math.min(d[si-1][ti]+1, d[si][ti-1]+1),d[si-1][ti-1]+cost);  
        }  
    }  
    return d[sLen][tLen];  
}  

附加一个相似度函数：

public static double similarity(String src, String tar) {  
    int ld = ld(src, tar);  
    return 1 - (double) ld / Math.max(src.length(), tar.length());   
}