編輯距離（Edit Distance），最先是由俄國科學家Vladimir Levenshtein在1965年發(fā)明，用他的名字命名，又稱Levenshtein距離。是指兩個字串之間，由一個轉成另一個所需的最少編輯操作次數(shù)。許可的編輯操作包括將一個替換成另一個字符，插入一個字符，刪除一個字符。

假設我們有兩個字符串"syk"和"syko"。

1.將兩個字符串分別寫到行和列中，第一行和第一列的值從0開始增長。

2.A出得值取決于：左邊的值(1)、上邊的值(1)、左上角的值(0)。上面的值和左面的值都要求加1，這樣得到1+1=2，1+1=2。A處由于是兩個s相同，左上角的值加0.這樣得到0+0=0。所以A處取他們里面最小的0.

3.同理，B出得值取決于：左邊的值(0)、上邊的值(2)、左上角的值(1)。上面的值和左面的值都要求加1，這樣得到2+1=3, 0+1=1。 B處由于是t和s不相同，左上角的值加1.這樣得到1+1=2。所以B處取他們里面最小的1.

4.依次生成矩陣

5.最后得到他們的距離=1，根據(jù)相似度計算公式：
(1-ld/(double)Math.max(syk.length(), syko.length()))
ld指的是最小編輯距離，就是矩陣最右下角最后求出的值。
所有最后的相似度值為1-1/4 = 0.75

局限性

由于需要利用矩陣，故空間復雜度為O(MN)。這個在兩個字符串都比較短小的情況下，能獲得不錯的性能。不過，如果字符串比較長的情況下，就需要極大的空間存放矩陣。例如：兩個字符串都是20000字符，則LD矩陣的大小為：20000 X 20000 X 2=800000000Byte=800MB。

java代碼

public static double levenshtein(String str1, String str2) {
        //計算兩個字符串的長度。
        int len1 = str1.length();
        int len2 = str2.length();
        //建立上面說的數(shù)組，比字符長度大一個空間
        int[][] dif = new int[len1 + 1][len2 + 1];
        //賦初值。
        for (int a = 0; a <= len1; a++) {
            dif[a][0] = a;
        }
        for (int a = 0; a <= len2; a++) {
            dif[0][a] = a;
        }
        //計算兩個字符是否一樣，計算左上的值
        int temp;
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    temp = 0;
                } else {
                    temp = 1;
                }
                //取三個值中最小的
                dif[i][j] = min(dif[i - 1][j - 1] + temp, dif[i][j - 1] + 1,
                        dif[i - 1][j] + 1);
            }
        }
        System.out.println("字符串\"" + str1 + "\"與\"" + str2 + "\"的比較");
        //取數(shù)組右下角的值，同樣不同位置代表不同字符串的比較
        System.out.println("差異步驟：" + dif[len1][len2]);
        //計算相似度
        float similarity = 1 - (float) dif[len1][len2] / Math.max(str1.length(), str2.length());
        System.out.println("相似度：" + similarity);
        return similarity;
    }

    //得到最小值
    private static int min(int... is) {
        int min = Integer.MAX_VALUE;
        for (int i : is) {
            if (min > i) {
                min = i;
            }
        }
        return min;
    }