字元串編輯距離（最小編輯次數）算法-解法推導

最近在研究一些算法，因為之前自己的程式設計都沒有經過系統的學習，是以通過學一些算法和資料結構來提高程式設計水準。

關于字元串的編輯距離算法，網上的文章有很多，内容大同小異，都是用動态規劃來做，而且給出了實作的代碼。但是，對于算法中的狀态轉換方程 d[i, j] = min(d1,d2,d3) = min(d[i-1, j]+1,   d[i, j-1]+1,   d[i-1, j-1] + (A[i] == A[j] ? 0 : 1)) 的推導，說明都不太詳細或者基于直覺，少有較為完整的證明。像知乎上就有人問（https://www.zhihu.com/question/23139644）：

題主在了解狀态轉移方程的時候，一直過不去。

假設字元串A(長為n), B(長為m)，0 < i <= n, 0 < j <= m,D(i, j)代表A[1:i]變為B[1:j]的編輯距離，編輯距離指由A=>B的最短操作數，每個操作都隻針對一個字元。

那麼 D(i,j) = min(D(i - 1, j - 1) + (A[i] == B[j]) ? 0 : 1, D(i - 1, j) + 1, D(i, j - 1) + 1)

如何用數學、嚴謹、形式化的方式去證明上述遞推公式成立？而不是想當然、由題而知、顯然可得？

下文以我自己的了解，結合圖檔，來推導狀态轉換方程。

問題描述

字元串的編輯距離是指，字元串A修改為字元串B所需要的最少的編輯次數。插入、删除、修改都算作一次修改。

解法推導

現在研究在老字元串到新字元串的編輯過程中，老字元串的 原有字元 的 變化 情況。可能的變化有：

1. 被修改；
2. 被删除；
3. 位置移動（由插入新字元/删除字元導緻）。

舉個例子，例如從“abcdefg" -> “aebcdhf” 的一種編輯，原有字元的變化情況如下：

圖中，“e”被修改，“g”被删除，“b” “c” “d” “e(後改為h)” “f” 的位置發生了變化。

值得注意的是，由于插入、修改和删除不涉及字元順序的變化，是以原字元串中的字元的順序在新字元串中不會發生變化。例如，若将 "ab" 修改為 “ba”，則視為兩次修改： a 修改為 b，b 修改為 a，因為并沒有規定“交換字元順序”的編輯方式。

設源字元串為A，目标字元串為B；字元串 A 有 i 個字元；字元串 B 有 j 個字元。

現在考慮在某編輯中，對字元串 A 的 最後一個字元 A[i] 的處理情況。

情況有三種：

1. 最後一個字元 被删除。此時的情況比較簡單，隻需要将字元串A剩下的字元串 A[0...i-1] 修改為字元串B即可（設最少編輯 k1次）。此時的最少編輯次數為 k1 + 1。
2. 最後一個字元 未被删除，但是其在新字元串中 是最後一個字元。此時，需要将原字元串剩下的子串 A[1...i-1] 修改成為新字元串的子串 B[1...j-1]（如下圖所示）（設最少編輯 k2 次）。如果 A[i] == B[j], 則最後一個字元無需修改，最少編輯次數為 k2; 否則，需要修改最後一個字元，最少編輯次數為 k2 + 1。

   

3. 最後一個字元 未被删除，但是其在新字元串中 不是最後一個字元。因為在編輯過程中，字元串的字元順序不會變化，是以原字元串的前 i - 1 個字元在新字元串的位置必在 A[i] 的新位置之前（若未被删除）（如下圖所示）。這樣的編輯等價于将字元串 A 修改為字元串 B 的子串 B[1...j-1]（設最少編輯 k3 次），然後再在尾部添加字元串 B 的最後一個字元即可。此時的最少編輯次數 k3 + 1。

   

由于這3種情況 涵蓋了對最後一個字元的所有處理方式，是以，最少的編輯次數一定會從這三種情況中産生。設 d[i, j] 為字元串 A 的子串 A[1...i] 到 字元串B的子串 B[1...j] 的最短編輯距離，則：

• 情況1： d1 = d[i-1, j] + 1;
• 情況2： 當 A[i] = B[j] 時，d2 = d[i - 1, j - 1]; 否則，d2 = d[i - 1,  j - 1] + 1;
• 情況3： d3 = d[i, j - 1] + 1。

是以，d[i, j] = min(d1,d2,d3) = min(d[i-1, j]+1,   d[i, j-1]+1,   d[i-1, j-1]+t) ，其中 t = 0（A[i] = B[j]），t = 1(A[i] != B[j])。

知道了狀态轉換方程，由動态規劃來求解該問題的具體方法就不贅述了，需要注意的是初始條件的選取：

• d[0, 0] = 0;
• 當 i = 0 時，d[0, j] = j；（将空字元串修改為長度為 j 的字元串需要增添 j 次）
• 當 j = 0 時，d[i, 0] = i。（将長度為 i 的字元串修改為空需要删除 i 次）

相關參考

https://www.zhihu.com/question/23139644/answer/98769510