最短編輯距離問題

一、問題描述

給定兩個字元串A和B，要求用少的編輯操作将A轉換成B，其中允許的操作有三種：

1、替換

2、插入

3、删除

注意，A[i]=B[i]表示A和B的對應位置字元已經相同，是以在這種情況下，是不需要經過任何的編輯操作的。

例如，給定字元串A和B如下：

String strA = "sight";
        String strB = "cite";      

由A->B最少需要進行4步編輯操作，分别是：

1、替換，将A中的‘s’替換為‘c’；

2、删除，将A中的‘g’删除；

3、删除，将A中的‘h’删除；

4、插入，将‘t’插入到A的末尾

至此，盡力4步編輯操作，可以将A完全抓化為B。而且這也是成本最小的（編輯次數最少）編輯方案。

二、分析

其實有了前面的DNA序列對齊問題的求解後，在求解這個編輯距離問題就很清晰。

在DNA序列對齊問題中，打分規則b和c的兩種細分情況剛好對應了編輯距離問題的替換、插入、删除三種編輯操作，打分規則a則對應了不需要編輯操作（可以想象為複制操作）的情況。

最高得分的序列對齊方案也就是用需要盡量多的複制操作和盡量少的替換、插入、删除操作完成對齊任務（當然這裡有一個内在的限制條件）。

用C(i,j)表示序列A[0]...A[i]和序列B[0]...B[j]的最少編輯操作次數，其求解遞推表達式為：

三、算法實作

package agdp;
public class SED {
    public static int getSED(String strA,String strB){
        int m = strA.length(),n = strB.length();
        int[][] aux = new int[m+1][n+1];//aux的第0行和第0列做哨兵，邊界計算
        //邊界值的初始化
        for (int i = 0; i < m+1; i++) {
            aux[i][0] = i;
        }
        for (int i = 0; i < n+1; i++) {
            aux[0][i] = i;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (strA.charAt(i-1) == strB.charAt(j-1)) {
                    aux[i][j] = aux[i-1][j-1];//無需編輯操作
                }else {
                    //對應替換，删除、插入中的一種，需要一次編輯擦周
                    aux[i][j] = Math.min(Math.min(aux[i-1][j], aux[i][j-1]), aux[i-1][j-1])+1;
                }
            }
        }
        return aux[m][n];
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        String strA = "sight";
        String strB = "cite";
//        String strA = "steal";
//        String strB = "steel";
        int count = getSED(strA, strB);
        System.out.print(count);
    }
}      

其子問題的求解如下：

 參考資料：

算法導論.第十五章