萊文斯坦距離

萊文斯坦距離（英語：Levenshtein distance）是編輯距離的一種。指兩個字串之間，由一個轉成另一個所需的最少編輯操作次數。

允許的編輯操作包括：

1. 將一個字符替換成另一個字符
2. 插入一個字符
3. 刪除一個字符

俄羅斯科學家弗拉基米爾·萊文斯坦在1965年提出這個概念^[1][2]。

定義

如果分別用 ${\displaystyle |a|}$ 和 ${\displaystyle |b|}$ 表示 ${\displaystyle a,b}$ 兩個字符串的長度，那麼它們的列文斯坦距離為 ${\displaystyle \operatorname {lev} _{a,b}(|a|,|b|)}$，它符合：

${\displaystyle \qquad \operatorname {lev} _{a,b}(i,j)={\begin{cases}\max(i,j)&{\text{ if }}\min(i,j)=0,\\\min {\begin{cases}\operatorname {lev} _{a,b}(i-1,j)+1\\\operatorname {lev} _{a,b}(i,j-1)+1\\\operatorname {lev} _{a,b}(i-1,j-1)+1_{(a_{i}\neq b_{j})}\end{cases}}&{\text{ otherwise.}}\end{cases}}}$

${\displaystyle 1_{(a_{i}\neq b_{j})}}$ 是一個指示函數（indicator function），當 ${\displaystyle a_{i}=b_{j}}$ 時，其值為0，其他時候它等於 1 。

${\displaystyle \operatorname {lev} _{a,b}(i,j)}$表示 ${\displaystyle a}$ 的前 ${\displaystyle i}$ 個字符與 ${\displaystyle b}$ 的前 ${\displaystyle j}$ 個字符之間的列文斯坦距離。（ ${\displaystyle i}$ 和 ${\displaystyle j}$ 都是從1開始的下標）

注意：min運算中的第一個公式代表（ 從 ${\displaystyle a}$ 中）刪除字符（以到達 ${\displaystyle b}$）；第二個公式代表插入字符；第三個代表替換（取決於當前字符是否相同）

例如

將「kitten」一字轉成「sitting」的萊文斯坦距離為3：

1. kitten → sitten （k→s）
2. sitten → sittin （e→i）
3. sittin → sitting （插入g）

應用

• DNA分析
• 拼寫檢查
• 語音辨識
• 抄襲偵測

演算法

動態規劃經常被用來作為這個問題的解決手段之一。

int LevenshteinDistcance(string str1[1..lenStr1], string str2[1..lenStr2])
    int d[0..lenStr1, 0..lenStr2]
    int i, j, cost
 
    for i = 0 to lenStr2
       d[i, 0] := i
    for j = 0 to lenStr1
       d[0, j] := j
 
    for i = 1 to lenStr2
        for j = 1 to lenStr1
            if str2[i] = str1[j] 
                cost := 0
            else 
                cost := 1
            d[i, j] := min(
                                d[i-1, j  ] + 1,     // 删除
                                d[i  , j-1] + 1,     // 插入
                                d[i-1, j-1] + cost   // 替換
                            )
 
   return d[lenStr1, lenStr2]

參見

• 漢明距離
• 延森-香農距離
• 序列比對
• Soundex
• 最長公共子序列
• Floyd-Warshall算法
• Viterbi算法