編輯距離的定義

編輯距離（Edit Distance）最常用的定義就是Levenstein距離，是由俄國科學(xué)家Vladimir Levenshtein于1965年提出的，所以編輯距離一般又稱Levenshtein距離。它主要作用是測(cè)量兩個(gè)字符串的差異化程度，表示字符串a(chǎn)至少要經(jīng)過多少個(gè)操作才能轉(zhuǎn)換為字符串b，這里的操作包括三種：增加、刪除、替換。

舉個(gè)例子：
(1)增加：對(duì)于字符串a(chǎn)：abc 和 字符串b:abcde，顯然，只需要在字符串a(chǎn)的末尾增加字符'd'和'e'就能變成字符串b了，所以a和b的最短編輯距離為2。
(2)刪除：對(duì)于字符串a(chǎn):abcd 和字符串b:abc，顯然，只需要在字符串a(chǎn)的末尾刪除字符'd'就能變成字符串b了，所以a和b的最短編輯距離為1。
(3)替換：對(duì)于字符串a(chǎn):abcd 和 字符串b:abce，顯然，只需要把字符串a(chǎn)的'd'替換成'e'就可以了，此時(shí)二者的最短編輯距離是1。

一般字符串都是需要增加、刪除、替換三者結(jié)合起來一起使用，因?yàn)樽址產(chǎn)到b可能存在多種變化的方法，而我們往往最關(guān)心的是最短的編輯距離，這樣才能得出a和b的相似程度，最短編輯距離越小，表示a到b所需要的操作越少，a和b的相似度也就越高。因此，Levenstein距離的一個(gè)應(yīng)用場景就是判斷兩個(gè)字符串的相似度，可以用在字符串的模糊搜索上面。

Levenshtein 算法原理

先從一個(gè)問題談起：對(duì)于字符串"xyz"和"xcz"，它們的最短距離是多少？我們從兩個(gè)字符串的最后一個(gè)字符開始比較，它們都是'z'，是相同的，我們可以不用做任何操作，此時(shí)二者的距離實(shí)際上等于"xy"和"xc"的距離，即d(xyz,xcz) = d(xy,xc)。也即是說，如果在比較的過程中，遇到了相同的字符，那么二者的距離是除了這個(gè)相同字符之外剩下字符的距離。即d(i，j) = d(i - 1,j-1)。

接著，我們把問題拓展一下，最后一個(gè)字符不相同的情況：字符串A("xyzab")和字符串B("axyzc")，問至少經(jīng)過多少步操作可以把A變成B。

我們還是從兩個(gè)字符串的最后一個(gè)字符來考察即'b'和'c'。顯然二者不相同，那么我們有以下三種處理辦法：
(1)增加：在A末尾增加一個(gè)'c'，那么A變成了"xyzabc"，B仍然是"axyzc"，由于此時(shí)末尾字符相同了，那么就變成了比較"xyzab"和"axyz"的距離，即d(xyzab,axyzc) = d(xyzab,axyz) + 1。可以寫成d(i,j) = d(i,j - 1) + 1。表示下次比較的字符串B的長度減少了1，而加1表示當(dāng)前進(jìn)行了一次字符的操作。

(2)刪除：刪除A末尾的字符'b'，考察A剩下的部分與B的距離。即d(xyzab,axyzc) = d(xyza,axyzc) + 1?？梢詫懗蒬(i,j) = d(i - 1,j) + 1。表示下次比較的字符串A的長度減少了1。

(3)替換：把A末尾的字符替換成'c'，這樣就與B的末尾字符一樣了，那么接下來就要考察出了末尾'c'部分的字符，即d(xyzab,axyzc) = d(xyza,axyz) + 1。寫成d(i,j) = d(i -1,j-1) + 1表示字符串A和B的長度均減少了1。

由于我們要求的是最短的編輯距離，所以我們?nèi)∫陨先齻€(gè)步驟得出的距離的最小值為最短編輯距離。由上面的步驟可得，這是一個(gè)遞歸的過程，因?yàn)槌糇詈笠粋€(gè)字符之后，剩下的字符串的最后一位仍然是最后一個(gè)字符，我們?nèi)匀豢梢园凑丈厦娴娜N操作來進(jìn)行，經(jīng)過這樣的不斷遞歸，直到比較到第一個(gè)字符為止，遞歸結(jié)束。

按照以上思路，我們很容易寫出下面的方程：

最短編輯距離方程

注釋：該方程的第一個(gè)條件min(i,j) = 0，表示若某一字符串為空，轉(zhuǎn)換成另一個(gè)字符串所需的操作次數(shù)，顯然，就是另一個(gè)字符串的長度(添加length個(gè)字符就能轉(zhuǎn)換)。這個(gè)條件可以看成是遞歸的出口條件，此時(shí)i或j減到了0。

根據(jù)以上方程，我們能快速寫出遞歸代碼，但由于遞歸包含了大量的重復(fù)計(jì)算，并且如果初始字符串過長，會(huì)造成遞歸層次過深，容易造成棧溢出的問題，所以我們這里可以用動(dòng)態(tài)規(guī)劃來實(shí)現(xiàn)。如果說遞歸是自頂向下的運(yùn)算過程，那么動(dòng)態(tài)規(guī)劃就是自底向上的過程。它從i和j的最小值開始，不斷地增大i和j，同時(shí)對(duì)于一個(gè)i和j都會(huì)算出當(dāng)前地最短距離，因?yàn)橄乱粋€(gè)i和j的距離會(huì)與當(dāng)前的有關(guān)，所以通過一個(gè)數(shù)組來保存每一步的運(yùn)算結(jié)果來避免重復(fù)的計(jì)算過程，當(dāng)i和j增加到最大值length時(shí)，結(jié)果也就出來了，即d[length][length]為A、B的最短編輯距離。

動(dòng)態(tài)規(guī)劃中，i和j的增加需要兩層循環(huán)來完成，外層循環(huán)遍歷i，內(nèi)層循環(huán)遍歷j，也即是，對(duì)于每一行，會(huì)掃描行內(nèi)的每一列的元素進(jìn)行運(yùn)算。因此，時(shí)間復(fù)雜度為o(n2)，空間復(fù)雜度為o(n2)。

圖解動(dòng)態(tài)規(guī)劃求最短編輯距離過程

在寫代碼之前，為了讓讀者對(duì)動(dòng)態(tài)規(guī)劃有一個(gè)直觀的感受，筆者以表格的形式，列出動(dòng)態(tài)規(guī)劃是如何一步步地工作的。
下面以字符串"xyzab"和"axyzc"為例來講解。

圖解

由上面可以看出，動(dòng)態(tài)規(guī)劃就是逐行逐列地運(yùn)算，逐漸填滿整個(gè)數(shù)組，最后得到結(jié)果恰好保存在數(shù)組的最后一行和最后一列的元素上。

代碼實(shí)現(xiàn)

一、基本實(shí)現(xiàn)

public class LevenshteinDistance {

    private static int minimum(int a,int b,int c){
        return Math.min(Math.min(a,b),c);
    }

    public static int computeLevenshteinDistance(CharSequence src,CharSequence dst){
        int[][] distance = new int[src.length() + 1][dst.length() + 1];

        for (int i = 0;i <= src.length();i++)
            distance[i][0] = i;
        for (int j = 0;j <= dst.length();j++)
            distance[0][j] = j;

        for (int i = 1;i <= src.length();i++){
            for (int j = 1;j <= dst.length();j++){
                int flag = (src.charAt(i - 1) == dst.charAt(j - 1)) ? 0 : 1;
                distance[i][j] = minimum(
                        distance[i - 1][j] + 1,
                        distance[i][j - 1] + 1,
                        distance[i - 1][j - 1] + flag);
            }
        }
        return distance[src.length()][dst.length()];
    }

    //測(cè)試方法
    public static void main(String args[]){
        String s1 = "xyzab";
        String s2 = "axyzc";

        String s3 = "等啊高原";
        String s4 = "阿登高原";

        String s5 = "xyz阿登高原";
        String s6 = "1y3等啊高原x";

        System.out.println("字符串(\"" + s1 + "\")和字符串(\"" + s2 + "\")的最小編輯距離為："+ computeLevenshteinDistance(s1,s2));
        System.out.println("字符串(\"" + s3 + "\")和字符串(\"" + s4 + "\")的最小編輯距離為："+ computeLevenshteinDistance(s3,s4));
        System.out.println("字符串(\"" + s5 + "\")和字符串(\"" + s6 + "\")的最小編輯距離為："+ computeLevenshteinDistance(s5,s6));

    }
}

上面的代碼是利用了動(dòng)態(tài)規(guī)劃的思想來實(shí)現(xiàn)的最短編輯距離算法，它的實(shí)現(xiàn)與原理方程基本上是一致的，都是先對(duì)第一行和第一列的數(shù)據(jù)進(jìn)行初始化，然后開始逐行逐列進(jìn)行計(jì)算，填充滿整個(gè)數(shù)組，即自底向上的思想，通過這樣減少了大量的遞歸重復(fù)計(jì)算，實(shí)現(xiàn)了運(yùn)算速度的提升。上面提到，這種實(shí)現(xiàn)的時(shí)間復(fù)雜度和空間復(fù)雜度都是n2級(jí)別的（實(shí)際上是m×n，兩個(gè)字符串長度的乘積）。實(shí)際上，我們可以對(duì)代碼進(jìn)行優(yōu)化，降低空間復(fù)雜度。

二、利用滾動(dòng)數(shù)組進(jìn)行空間復(fù)雜度的優(yōu)化
滾動(dòng)數(shù)組是動(dòng)態(tài)規(guī)劃中一種常見的優(yōu)化思想。為了理解滾動(dòng)數(shù)組的思想，我們先來看看如何進(jìn)行空間復(fù)雜度的優(yōu)化?；氐皆矸匠蹋覀兛梢杂^察到d(i,j)只與上一行的元素d(i-1,j)、d(i,j-1)和d(i-1,j-1)有關(guān)，而上一行之前的元素沒有關(guān)系，也就是說，對(duì)于某一行的d(i,j)，我們只需要知道上一行的數(shù)據(jù)就行，別的數(shù)據(jù)都是無效數(shù)據(jù)。實(shí)際上，我們只需要兩行的數(shù)組就可以了。

舉個(gè)例子：還是上面的"xyzab"和"axyzc"，當(dāng)我們計(jì)算完第一行和第二行的數(shù)據(jù)后，到達(dá)第三行時(shí)，我們以第二行為上一行結(jié)果來計(jì)算，并把計(jì)算結(jié)果放到第一行內(nèi)；到達(dá)第四行時(shí)，由于第三行的數(shù)據(jù)實(shí)際上保存在第一行，所以我們根據(jù)第一行來計(jì)算，把結(jié)果保存在第二行……以此類推，直到計(jì)算到最后一行，即不斷交替使用兩行數(shù)組的空間，“滾動(dòng)數(shù)組”也因此得名。通過使用滾動(dòng)數(shù)組的形式，我們不需要n×m的空間，只需要2×min(n,m)的空間，這樣便能把空間復(fù)雜度降到線性范圍內(nèi)，節(jié)省了大量的空間。

利用滾動(dòng)數(shù)組后的空間復(fù)雜度為o(2×n)或者o(2×m)，這取決于代碼的實(shí)現(xiàn)，即取字符串A還是B的長度為數(shù)組的列數(shù)。(因?yàn)闊o論把哪一個(gè)字符串作為src或dst，都是等價(jià)的，結(jié)果都是一樣的。)其實(shí)我們可以通過判斷A、B的長度，來選取一個(gè)最小值作為列數(shù)，此時(shí)空間復(fù)雜度變?yōu)閛(2×min(n,m))。下面給出基于滾動(dòng)數(shù)組的最小編輯距離的優(yōu)化版本，由Java實(shí)現(xiàn)。

/**
     *  利用滾動(dòng)數(shù)組優(yōu)化過的最小編輯距離算法。空間復(fù)雜度為O(2×min(lenSrc,lenDst))
     * @param src 動(dòng)態(tài)規(guī)劃數(shù)組的行元素
     * @param dst 動(dòng)態(tài)規(guī)劃數(shù)組的列元素
     * @return
     */
    public static int computeLevenshteinDistance_Optimized(CharSequence src,CharSequence dst){
        int lenSrc = src.length() + 1;
        int lenDst = dst.length() + 1;

        CharSequence newSrc = src;
        CharSequence newDst = dst;
        //如果src長度比dst的短，表示數(shù)組的列數(shù)更多，此時(shí)我們
        //交換二者的位置，使得數(shù)組的列數(shù)變?yōu)檩^小的值。
        if (lenSrc < lenDst){
            newSrc = dst;
            newDst = src;
            int temp = lenDst;
            lenDst = lenSrc;
            lenSrc = temp;
        }

        //創(chuàng)建滾動(dòng)數(shù)組，此時(shí)列數(shù)為lenDst，是最小的
        int[] cost = new int[lenDst];   //當(dāng)前行依賴的上一行數(shù)據(jù)
        int[] newCost = new int[lenDst];//當(dāng)前行正在修改的數(shù)據(jù)

        //對(duì)第一行進(jìn)行初始化
        for(int i = 0;i < lenDst;i++)
            cost[i] = i;

        for(int i = 1;i < lenSrc;i++){
            //對(duì)第一列進(jìn)行初始化
            newCost[0] = i;

            for(int j = 1;j < lenDst;j++){
                int flag = (newDst.charAt(j - 1) == newSrc.charAt(i - 1)) ? 0 : 1;

                int cost_insert = cost[j] + 1;        //表示“上面”的數(shù)據(jù)，即對(duì)應(yīng)d(i - 1,j)
                int cost_replace = cost[j - 1] + flag;//表示“左上方的數(shù)據(jù)”，即對(duì)應(yīng)d(i - 1,j - 1)
                int cost_delete = newCost[j - 1] + 1; //表示“左邊的數(shù)據(jù)”，對(duì)應(yīng)d(i,j - 1)

                newCost[j] = minimum(cost_insert,cost_replace,cost_delete); //對(duì)應(yīng)d(i,j)
            }

            //把當(dāng)前行的數(shù)據(jù)交換到上一行內(nèi)
            int[] temp = cost;
            cost = newCost;
            newCost = temp;
        }

        return cost[lenDst - 1];
    }

把main()方法的方法調(diào)用改為上述方法，比較前后兩個(gè)方法的輸出結(jié)果，結(jié)果一致，符合預(yù)期。

輸出結(jié)果

三、對(duì)空間復(fù)雜度的進(jìn)一步優(yōu)化
實(shí)際上，我們還能對(duì)這個(gè)進(jìn)行進(jìn)一步的優(yōu)化，把空間復(fù)雜度減少為o(min(n,m))，即我們只需要一行的數(shù)組d加一個(gè)額外的臨時(shí)變量就可以實(shí)現(xiàn)。比如說我們要修改d[i]的值時(shí)，只需知道它的左邊、上邊和左上方的元素的值，而左邊的值就是d[i-1]，上邊的值是修改之前的d[i]，左上方的值是d[i-1]修改之前的值。每一次需要修改d[i-1]的時(shí)候，都用臨時(shí)變量把他保存起來，這樣i位置就能直接獲取這三個(gè)值進(jìn)行比較，得到結(jié)果之后，先用這個(gè)臨時(shí)變量把d[i]保存起來，然后再寫入d[i]內(nèi)，……以此類推，直到遍歷完一行。

其核心思想是：把求得的數(shù)據(jù)，再次寫回這一行數(shù)據(jù)對(duì)應(yīng)下標(biāo)元素的位置，而臨時(shí)變量temp則保存當(dāng)前位置左上方元素的值，以提供給下一個(gè)位置的計(jì)算。總的來說，數(shù)據(jù)的操作只集中在一行之內(nèi)，所以空間復(fù)雜度就是o(n)。

下面以圖解的形式表達(dá)這一過程，方便讀者理解。

單行數(shù)組

代碼實(shí)現(xiàn)也不復(fù)雜，有興趣的同學(xué)可以根據(jù)上圖或者思路來實(shí)現(xiàn)，這里就不再實(shí)現(xiàn)了。

好了，這篇文章寫到這里就結(jié)束了，希望能對(duì)各位同學(xué)有所裨益，謝謝你們的耐心閱讀~