萊文斯坦距離

维基百科,自由的百科全书
(重定向自編輯距離
跳转至: 导航搜索

萊文斯坦距離,又稱Levenshtein距離,是編輯距離edit distance)的一種。指兩個字串之間,由一個轉成另一個所需的最少編輯操作次數。許可的編輯操作包括將一個字符替換成另一個字符,插入一個字符,刪除一個字符。

例如將kitten一字轉成sitting:

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

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

應用[编辑]

演算法[编辑]

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

int LevenshteinDistcance(string str1[1..lenStr1], string str2[1..lenStr2])
    int d[0..lenStr1, 0..lenStr2]
    int i, j, cost
 
    for i = 0 to lenStr1
       d[i, 0] := i
    for j = 0 to lenStr2
       d[0, j] := j
 
    for i = 1 to lenStr1
        for j = 1 to lenStr2
            if str1[i] = str2[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]

參見[编辑]