編輯距離：誤差測量者

演算法背後的故事：拼寫錯誤

想像妳是一位老師，正在批改拼寫測試。

• 學生寫了：“KITTEN”
• 正確單詞是：“SITTING”

妳應該扣多少分？

1. 把 ‘K’ 替換為 ‘S’ -> SITTEN
2. 在 ‘S’ 後面插入 ‘I’ -> SIITTEN (等等，這不對…)
3. 讓我們再試一次：
   • K -> S (替換)
   • I -> I (匹配)
   • T -> T (匹配)
   • T -> T (匹配)
   • E -> I (替換)
   • N -> N (匹配)
   • 結尾 -> 添加 G (插入)

總操作數：3。 這個數字 3 就是 Levenshtein 距離 (編輯距離)。它是將一個字串轉換為另一個字串所需的 插入、刪除 或 替換 的最小次數。

為什麼需要它？

• 拼寫檢查器： 「您是不是要找…？」如果妳輸入 “Gogle”，它到 “Google” 的距離是 1，到 “Apple” 的距離是 4。電腦建議 “Google”。
• DNA 對齊： 比較兩個基因序列，看兩個物種的親緣關係有多近。
• 查重檢測： 測量兩篇文章的相似度，即使學生修改了幾個詞。

演算法是如何「思考」的

該演算法使用 動態規劃 (Dynamic Programming)。它構建一個網格（矩陣），其中 cell[i][j] 表示 Word A 的前 i 個字元和 Word B 的前 j 個字元之間的距離。

網格規則：

• 如果字元匹配：沒有成本。cell[i][j] = cell[i-1][j-1]
• 如果不匹配：取三個選項中的最小值 + 1 成本：
  1. 插入： 看左邊 (cell[i][j-1])
  2. 刪除： 看上面 (cell[i-1][j])
  3. 替換： 看對角線 (cell[i-1][j-1])

工程決策：複雜度

• 時間： $O(N imes M)$，其中 N 和 M 是字串長度。
• 空間： $O(N imes M)$ 用於完整矩陣。
• 優化： 妳只需要上一行就能計算當前行。所以空間可以降低到 $O(min(N, M))$。

實作參考 (Python)

def levenshtein_distance(s1, s2):
    m, n = len(s1), len(s2)
    
    # 創建大小為 (m+1) x (n+1) 的矩陣
    # dp[i][j] = s1[:i] 和 s2[:j] 之間的距離
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # 初始化第一行和第一列
    for i in range(m + 1):
        dp[i][0] = i # 將 s1[:i] 變為空字串需要 i 次刪除
    for j in range(n + 1):
        dp[0][j] = j # 將空字串變為 s2[:j] 需要 j 次插入

    # 填充矩陣
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i - 1] == s2[j - 1]:
                # 字元匹配，無成本
                dp[i][j] = dp[i - 1][j - 1]
            else:
                # 不匹配，取 插入、刪除、替換 的最小值
                dp[i][j] = 1 + min(
                    dp[i][j - 1],    # 插入
                    dp[i - 1][j],    # 刪除
                    dp[i - 1][j - 1] # 替換
                )
    
    return dp[m][n]

# 使用範例
print(f"距離: {levenshtein_distance('kitten', 'sitting')}") # 輸出: 3

小結

編輯距離教會我們：差異是可以量化的。透過將「相似性」這樣模糊的概念分解為具體的原子動作（插入、刪除、替換），我們可以教電腦理解人類的錯誤。它提醒我們，在一個充滿噪音的世界裡，測量預期與現實之間差距的能力，是彌合差距的第一步。