萊文斯坦距離

维基百科,自由的百科全书
跳到导航 跳到搜索

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

允许的编辑操作包括:

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

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

定义[编辑]

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

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

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


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

例如[编辑]

將“kitten”一字轉成“sitting”的列文斯坦距离为3:

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

應用[编辑]

演算法[编辑]

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

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]

參見[编辑]