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

允许的编辑操作包括：

将一个字符替换成另一个字符

插入一个字符

刪除一个字符

俄羅斯科學家弗拉基米尔·莱文斯坦在1965年提出這個概念。

定义
如果分别用 |a| 和 |b| 表示 a, b 两个字符串的长度，那么它们的列文斯坦距离为 \operatorname{lev}_{a,b}(|a|,|b|)，它符合：

:\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}

1_{(a_i \neq b_j)} 是一个指示函数（indicator function），当 a_i = b_j 时，其值为0，其他时候它等于 1 。

\operatorname{lev}_{a,b}(i,j)表示 a 的前 i 个字符与 b 的前 j 个字符之间的列文斯坦距离。（ i 和 j 都是从1开始的下标）

注意：min运算中的第一个公式代表（ 从 a 中）删除字符（以到达 b）；第二个公式代表插入字符；第三个代表替换（取决于当前字符是否相同）

例如
將“kitten”一字轉成“sitting”的萊文斯坦距离为3：

kitten → sitten （k→s）

sitten → sittin （e→i）

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算法

参考文献