Damerau-Levenshtein：鍵盤上的同理心

演算法背後的故事：打字太快的代價

想像妳正在輸入 algorithm，但妳的手指動得太快了，以至於打成了 algorit hm（妳交換了 h 和 m 的位置）。

在標準的 Levenshtein 距離 看來，這是 2 次操作（刪除 h 再插入 h；或者兩次替換）。但在人類的認知裡，這只是 一個錯誤：一次 字元鄰接交換 (Transposition)。

1964 年，Frederick J. Damerau 發表了一篇論文。他觀察到，在人類所有的拼寫錯誤中，有 80% 是由以下四種情況組成的：一次插入、一次刪除、一次替換，以及 相鄰兩個字元的交換。

透過在 Levenshtein 的矩陣中加入「交換」規則，他創造了一個感覺更「人性化」的演算法。它理解我們不是隨機犯錯的機器人，而是生物，我們的手指有時會跑在思想的前面。

為什麼需要它？

Damerau-Levenshtein 是模糊匹配的「專業版」。

• 搜尋引擎： 它能為常見的打字失誤（如將 the 打成 teh）提供更準確的建議。
• OCR（光學字元識別）： 修正掃描儀在識別時可能產生的相鄰字元位置誤判。
• 生物資訊學： 在某些生物學語境中，相鄰的鹼基可能會發生交換，該演算法能捕捉到這種變異。

演算法是如何「思考」的

它與 Levenshtein 幾乎完全相同，但多了一份 「記憶」。

1. 標準的三個選項： 它依然會檢查插入、刪除和替換。
2. 交換 (Transposition)： 當編輯在矩陣中移動時，他會多往回看兩個步驟。他會問：

   「當前字元是否等於另一個單詞的前一個字元，且反之亦然？」 如果是，它就將 一次交換 視為一次操作，並計算其成本。

這讓演算法在邏輯上稍微複雜了一點，但對於處理人類產生的文本，它的準確性有了顯著提升。

工程決策：「完美」的代價

和 Levenshtein 一樣，它的複雜度也是 $O(N \cdot M)$。

• 選擇： 大多數開發者使用的是「受限」版本（Optimal String Alignment），它不允許在同一個子串上進行多次編輯。這對於拼寫檢查器來說已經足夠快且好用。
• 「人」的因素： 如果妳的應用是一個 CLI 工具或搜尋框，使用者經常需要快速輸入，那麼 Damerau-Levenshtein 值得妳多寫那幾行邏輯。如果妳是在比較機器生成的雜湊值，那麼 Levenshtein 或簡單的位元運算就足夠了。

實作參考 (Python - 受限版本)

def damerau_levenshtein(s1, s2):
    n, m = len(s1), len(s2)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(n + 1): dp[i][0] = i
    for j in range(m + 1): dp[0][j] = j

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            cost = 0 if s1[i-1] == s2[j-1] else 1
            
            # 標準的 Levenshtein 編輯操作
            dp[i][j] = min(
                dp[i-1][j] + 1,      # 刪除
                dp[i][j-1] + 1,      # 插入
                dp[i-1][j-1] + cost  # 替換
            )
            
            # 核心：Damerau 的相鄰交換邏輯
            if i > 1 and j > 1 and s1[i-1] == s2[j-2] and s1[i-2] == s2[j-1]:
                # 檢查是否可以透過一次交換來到達當前狀態
                dp[i][j] = min(dp[i][j], dp[i-2][j-2] + cost)

    return dp[n][m]

# 使用範例
# print(damerau_levenshtein("teh", "the")) # 輸出: 1
# print(damerau_levenshtein("ca", "abc")) # 輸出: 3

小結

Damerau-Levenshtein 教會我們：機器想要變得聰明，就必須理解人類是如何失敗的。透過識別兩個手指的簡單位置交換，我們彌合了冰冷的邏輯與人類生物學之間的鴻溝。它提醒我們，在代碼的世界裡，同理心往往只是動態規劃矩陣中的第四個選項。