戴默爾-列文斯坦距離

在資訊理論和電腦科學中，Damerau–Levenshtein 距離（以 Frederick J. Damerau 和 Vladimir I. Levenshtein 的名字命名）是一種用於測量兩個序列之間編輯距離的字串度量。通俗地說，兩個單字之間的 Damerau–Levenshtein 距離是將一個單字轉換成另一個單字所需的最少操作次數（包括插入、刪除或替換單一字元，或換位兩個相鄰字元）。

Damerau–Levenshtein 距離與傳統的 Levenshtein 距離不同之處在於，除了三種傳統的單字元編輯操作（插入、刪除和替換）外，它還將換位納入允許的操作中。

在其開創性論文中，Damerau 指出，在一項針對資訊檢索系統的拼寫錯誤調查中，超過 80% 的錯誤是由這四種類型之一的單一錯誤造成的。Damerau 的論文只考慮了最多只需一次編輯操作即可糾正的拼寫錯誤。雖然最初的動機是為了測量人類拼寫錯誤之間的距離以改進拼寫檢查器等應用，但 Damerau–Levenshtein 距離也已應用於生物學，以測量蛋白質序列之間的變異。

定義

為了表示兩個字串 <math>a</math> 和 <math>b</math> 之間的 Damerau–Levenshtein 距離，定義了一個函數 <math>d_{a,b}(i,j)</math>，其值為字串 <math>a</math> 的一個 <math>i</math> 長度前綴（初始子字串）與字串 <math>b</math> 的一個 <math>j</math> 長度前綴之間的距離。

受限距離函數遞迴定義如下： <math display="block">

d_{a,b}(i,j) = \min \begin{cases}
 0 & \text{if } i = j = 0, \\
 d_{a,b}(i-1,j) + 1 & \text{if } i > 0, \\
 d_{a,b}(i,j-1) + 1 & \text{if } j > 0, \\
 d_{a,b}(i-1,j-1) + 1_{(a_i \neq b_j)} &  \text{if } i, j > 0, \\
 d_{a,b}(i-2,j-2) + 1_{(a_i \neq b_j)} & \text{if } i, j > 1 \text{ and } a_i = b_{j-1} \text{ and } a_{i-1} = b_j, \\
\end{cases}

</math> 其中 <math>1_{(a_i \neq b_j)}</math> 是指示函數，當 <math>a_i = b_j</math> 時等於 0，否則等於 1。

每個遞迴呼叫對應 Damerau–Levenshtein 距離所涵蓋的一種情況：

<math>d_{a,b}(i-1,j) + 1</math> 對應於刪除（從 a 到 b），
<math>d_{a,b}(i,j-1) + 1</math> 對應於插入（從 a 到 b），
<math>d_{a,b}(i-1,j-1) + 1_{(a_i \neq b_j)} </math> 對應於匹配或不匹配，取決於相應的符號是否相同，
<math>d_{a,b}(i-2,j-2) + 1_{(a_i \neq b_j)}</math> 對應於兩個連續符號之間的換位。

則 <math>a</math> 和 <math>b</math> 之間的 Damerau–Levenshtein 距離由完整字串的函數值給出：<math>d_{a,b}\big(|a|, |b|\big)</math>，其中 <math>i = |a|</math> 表示字串 <math>a</math> 的長度，<math>j = |b|</math> 是字串 <math>b</math> 的長度。

演算法

這裡介紹兩種演算法：第一種較簡單，計算的是所謂的最佳字串對齊距離或受限編輯距離；第二種計算的是帶有相鄰換位的 Damerau–Levenshtein 距離。增加換位操作會顯著增加複雜性。兩種演算法的區別在於，最佳字串對齊演算法計算的是在「沒有子字串被編輯超過一次」的條件下使字串相等所需的編輯操作次數，而第二種演算法則沒有此類限制。

以 CA 和 ABC 之間的編輯距離為例。Damerau–Levenshtein 距離 LD(CA, ABC) = 2，因為 CA → AC → ABC；但最佳字串對齊距離 OSA(CA, ABC) = 3，因為如果使用操作 CA → AC，就無法再使用 AC → ABC，因為這會導致子字串被編輯超過一次，而這在 OSA 中是不允許的，因此最短的操作序列是 CA → A → AB → ABC。請注意，對於最佳字串對齊距離，三角不等式不成立：OSA(CA, AC) + OSA(AC, ABC) < OSA(CA, ABC)，因此它不是一個真正的度量。

最佳字串對齊距離

最佳字串對齊距離可以使用計算 Levenshtein 距離的 Wagner–Fischer 動態規劃演算法的直接擴展來計算。其偽代碼如下：

演算法 OSA-distance 為
    輸入：字串 a[1..length(a)], b[1..length(b)]
    輸出：距離，整數
    
    令 d[0..length(a), 0..length(b)] 為一個維度為 (length(a)+1) x (length(b)+1) 的二維整數陣列
    // 注意 d 是零基索引，而 a 和 b 是一基索引。
    
    對於 i := 0 到 length(a) (包含) 執行
        d[i, 0] := i
    對於 j := 0 到 length(b) (包含) 執行
        d[0, j] := j
    
    對於 i := 1 到 length(a) (包含) 執行
        對於 j := 1 到 length(b) (包含) 執行
            如果 a[i] = b[j] 則
                cost := 0
            否則
                cost := 1
            d[i, j] := minimum(d[i-1, j] + 1,     // 刪除
                               d[i, j-1] + 1,     // 插入
                               d[i-1, j-1] + cost)  // 替換
            如果 i > 1 且 j > 1 且 a[i] = b[j-1] 且 a[i-1] = b[j] 則
                d[i, j] := minimum(d[i, j],
                                   d[i-2, j-2] + 1)  // 換位
    回傳 d[length(a), length(b)]

與 Levenshtein 距離演算法的區別在於增加了一個遞迴關係式：

如果 i > 1 且 j > 1 且 a[i] = b[j-1] 且 a[i-1] = b[j] 則
    d[i, j] := minimum(d[i, j],
                       d[i-2, j-2] + 1)  // 換位

帶有相鄰換位的距離

以下演算法計算帶有相鄰換位的真實 Damerau–Levenshtein 距離；此演算法需要一個額外參數，即字母表 |Σ| 的大小，因此陣列的所有條目都在 [1..|Σ|] 的範圍內：

演算法 DL-distance 為
    輸入：字串 a[1..length(a)], b[1..length(b)]
    輸出：距離，整數
    
    da := 一個大小為 |Σ| 的新整數陣列
    對於 i := 1 到 |Σ| (包含) 執行
        da[i] := 0
    
    令 d[−1..length(a), −1..length(b)] 為一個維度為 (length(a)+2) x (length(b)+2) 的二維整數陣列
    // 注意 d 的索引從 -1 開始，而 a, b 和 da 是一基索引。
    
    maxdist := length(a) + length(b)
    d[−1, −1] := maxdist
    對於 i := 0 到 length(a) (包含) 執行
        d[i, −1] := maxdist
        d[i, 0] := i
    對於 j := 0 到 length(b) (包含) 執行
        d[−1, j] := maxdist
        d[0, j] := j
    
    對於 i := 1 到 length(a) (包含) 執行
        db := 0
        對於 j := 1 到 length(b) (包含) 執行
            k := da[b[j]]
            ℓ := db
            如果 a[i] = b[j] 則
                cost := 0
                db := j
            否則
                cost := 1
            d[i, j] := minimum(d[i−1, j−1] + cost,  //替換
                               d[i,   j−1] + 1,     //插入
                               d[i−1, j  ] + 1,     //刪除
                               d[k−1, ℓ−1] + (i−k−1) + 1 + (j-ℓ−1)) //換位
        da[a[i]] := i
    回傳 d[length(a), length(b)]

為了設計一個能計算無限制 Damerau–Levenshtein 距離的合適演算法，要注意的是，永遠存在一個最佳的編輯操作序列，其中經過一次換位的字母之後不再被修改。（只要換位的成本 <math>W_T</math> 至少是插入和刪除成本的平均值，即 <math>2W_T \ge W_I + W_D</math>，此條件即成立。）因此，我們只需要考慮兩種對稱的方式來多次修改一個子字串：(1) 換位字母並在它們之間插入任意數量的字元，或 (2) 刪除一個字元序列並換位因刪除而變得相鄰的字母。直接實現這個想法會得到一個立方複雜度的演算法：<math>O\big(M \cdot N \cdot \max(M, N)\big)</math>，其中 M 和 N 是字串長度。利用 Lowrance 和 Wagner 的思想，這個樸素的演算法可以在最壞情況下改進到 <math>O(M \cdot N)</math>，這正是上面偽代碼所做的。

有趣的是，bitap 演算法可以被修改以處理換位。關於此類改編的範例，可參見資訊檢索的相關章節。

應用

Damerau–Levenshtein 距離在自然語言處理中扮演著重要角色。在自然語言中，字串很短，錯誤（拼寫錯誤）的數量很少超過 2 個。在這種情況下，受限編輯距離和真實編輯距離的差異非常罕見。Oommen 和 Loke 甚至透過引入廣義換位來緩解受限編輯距離的局限性。儘管如此，我們必須記住，受限編輯距離通常不滿足三角不等式，因此不能與度量樹一起使用。

DNA

由於 DNA 經常發生插入、刪除、替換和換位，且這些操作都發生在大致相同的時間尺度上，因此 Damerau–Levenshtein 距離是衡量兩條 DNA 鏈之間變異的合適度量。在 DNA、蛋白質和其他生物資訊學相關的對齊任務中，更常見的是使用密切相關的演算法，如 Needleman–Wunsch 演算法或 Smith–Waterman 演算法。

詐騙偵測

該演算法可用於任何一組詞語，例如供應商名稱。由於輸入本質上是手動的，因此存在輸入錯誤供應商的風險。一個舞弊的員工可能會輸入一個真實的供應商，如「Rich Heir Estate Services」，而不是一個虛假的供應商「Rich Hier State Services」。然後，該舞弊者會創建一個虛假的銀行帳戶，讓公司將支票匯給真實供應商和虛假供應商。Damerau–Levenshtein 演算法將檢測到換位和遺漏的字母，並將這些項目提請舞弊稽核師注意。

出口管制

美國政府在其綜合篩查清單 API 中使用了 Damerau–Levenshtein 距離。

參見

Ispell – 根據 Damerau–Levenshtein 距離為 1 提出修正建議

參考資料

延伸閱讀

Category:字串度量 Category:資訊理論 Category:動態規劃