萊文斯坦距離

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

允许的编辑操作包括：

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

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

 定义 

如果分别用  和  表示  两个字符串的长度，那么它们的列文斯坦距离为 ，它符合：

 是一个指示函数（indicator function），当  时，其值为0，其他时候它等于 1 。

表示  的前  个字符与  的前  个字符之间的列文斯坦距离。（  和  都是从1开始的下标）

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

 例如 
將“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算法

 参考文献 

Category:字符串相似性度量
Category:编码理论
Category:算法
Category:计算生物学
Category:动态规划
Category:带有伪代码示例的条目