莱文斯坦距离

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

允许的编辑操作包括：

将一个字符替换成另一个字符
插入一个字符
删除一个字符

俄罗斯科学家弗拉基米尔·莱文斯坦（英语：Vladimir Levenshtein）在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]

参见