4.1 編輯距離與最長共同子序列#

概念說明#

編輯距離（edit distance）又稱 Levenshtein 距離，定義為把字串 s 改成 t 所需的最少操作數，允許三種操作：插入一個字元、刪除一個字元、取代一個字元。例如 kitten → sitting：「k→s、e→i 兩次取代，末尾插入 g」，距離為 3。

編輯距離滿足度規（metric）的三個性質：非負且 d(s,t)=0 ⟺ s=t、對稱 d(s,t)=d(t,s)、三角不等式 d(s,u) ≤ d(s,t)+d(t,u)，因此可視為字串空間上的「距離」，這是模糊搜尋「找距離小於 k 的字」這類問題的理論基礎。

計算方法的核心觀察：考慮 s 與 t 的最後一個字元。若相同，則 d(s,t)=d(s去掉末字元, t去掉末字元)；若不同，則三種操作分別對應三個子問題取最小再加一。這種「由最後一步反推」的遞迴結構有大量重疊子問題，正是動態規劃（見《演算法》書的動態規劃法一章）的標準場景。

最長共同子序列（Longest Common Subsequence, LCS）是緊密相關的問題：找出兩字串的最長子序列（可不連續、但保持順序）。sea 與 ate 的 LCS 是 "ea"，長度 2。編輯距離與 LCS 是一體兩面：若只允許插入與刪除（取代視為一刪一插），則編輯距離 = len(s)+len(t) − 2×LCS(s,t)。LCS 的 DP 表還能回溯出共同的子序列本身——這正是 diff 工具（git diff、版本比對）的原理：兩檔案的共同行構成 LCS，其餘即為刪除或新增。

生物資訊中，DNA 序列比對（Needleman-Wunsch 全域比對、Smith-Waterman 局部比對）就是把編輯操作加上不同的得分權重，本質都是這張 DP 表。

演算法步驟#

定義 dp[i][j] = s 前 i 個字元與 t 前 j 個字元的編輯距離。
邊界：dp[i][0] = i（全部刪除）、dp[0][j] = j（全部插入）。
轉移：若 s[i−1] == t[j−1]：dp[i][j] = dp[i−1][j−1]；否則 dp[i][j] = 1 + min(dp[i−1][j−1]（取代）、dp[i−1][j]（刪 s）、dp[i][j−1]（插 s））。
答案為 dp[m][n]。
LCS 版本：相同時 +1，不同時取左右兩方向最大；回溯時從右下角走：相同字元即為 LCS 一部分，否則往較大方向退。
空間優化：dp[i][*] 只依賴上一列，可用兩個一維陣列（甚至一個加暫存變數）。

Python 程式碼範例#

def edit_distance(s, t):
    m, n = len(s), len(t)
    prev = list(range(n + 1))          # 空間優化：兩列滾動
    for i in range(1, m + 1):
        cur = [i] + [0] * n
        for j in range(1, n + 1):
            if s[i - 1] == t[j - 1]:
                cur[j] = prev[j - 1]
            else:
                cur[j] = 1 + min(prev[j - 1],   # 取代
                                 prev[j],       # 刪除 s[i-1]
                                 cur[j - 1])    # 插入
        prev = cur
    return prev[n]

def lcs(s, t):
    m, n = len(s), len(t)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    # 回溯求出 LCS 字串
    i, j, out = m, n, []
    while i and j:
        if s[i - 1] == t[j - 1]:
            out.append(s[i - 1]); i -= 1; j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    return dp[m][n], "".join(reversed(out))

print(edit_distance("kitten", "sitting"))          # 3
print(edit_distance("演算法", "演算法法"))          # 1
print(lcs("ABCBDAB", "BDCABA"))                    # (4, 'BCBA')

複雜度分析#

時間：O(m×n)，兩者相同；這是全比對的下界之一（在強化的序列比對假設下，比這更快需特殊條件，如四俄人演算法 O(nd) 只在距離小時快）。
空間：完整表 O(m×n)；滾動陣列 O(n)。但 LCS 若要回溯字串，需保留全表或用 Hirschberg 分治法在 O(n) 空間內完成。
實務：m、n 各 10 萬時 O(mn)=10¹⁰ 不可行，需改用後綴結構（第3章）或帶索引的近似比對（4.3 節）。

練習#

修改 edit_distance，讓它同時回傳操作序列（如 取代 k→s、取代 e→i、插入 g）：保留完整 DP 表並從右下角回溯，依 dp 值判斷每步用了哪種操作。
實作只許插入與刪除的編輯距離，驗證它等於 len(s)+len(t)−2×LCS(s,t)，並解釋為何取代算「兩步」時此式成立。
用 difflib.SequenceMatcher 比較兩段多行文字（模擬 git diff），觀察其輸出與你實作的 LCS 行比對有何異同；再查閱 Myers diff 演算法（O(ND)），說明它為何比樸素 O(mn) 更適合行數多的檔案。