萊文斯坦距離

莱文斯坦距离，又称Levenshtein距离，是编辑距离的一种。指两个字串之間，由一个转成另一个所需的最少编辑操作次数。

允许的编辑操作包括：

1. 将一个字符替换成另一个字符
2. 插入一个字符
3. 刪除一个字符

俄羅斯科學家弗拉基米尔·莱文斯坦（英语：Vladimir Levenshtein）在1965年提出這個概念。

定义

如果分别用 ${\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算法