編輯距離

维基百科，自由的百科全书

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

例如將kitten一字轉成sitting：

1. sitten （k→s）
2. sittin （e→i）
3. sitting （→g）

俄羅斯科學家Vladimir Levenshtein在1965年提出這個概念。

[编辑] 應用

• DNA分析
• 拼字檢查
• 語音辨識
• 抄襲偵測

[编辑] 演算法

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

整數 Levenshtein距離(字符 str1[1..lenStr1], 字符 str2[1..lenStr2])
   宣告 int d[0..lenStr1, 0..lenStr2]
   宣告 int i, j, cost
 
   對於 i 等於 由 0 至 lenStr1
       d[i, 0] := i
   對於 j 等於 由 0 至 lenStr2
       d[0, j] := j

   對於 i 等於 由 1 至 lenStr1
       對於 j 等於 由 1 至 lenStr2
           若 str1[i] = str2[j] 則 cost := 0
                                否則 cost := 1
           d[i, j] := 最小值(
                                d[i-1, j  ] + 1,     // 刪除
                                d[i  , j-1] + 1,     // 插入
                                d[i-1, j-1] + cost   // 替換
                            )
 
   返回 d[lenStr1, lenStr2]

wikisource上有不同的編程語言版本。

[编辑] 參見

• 漢明距離
• 延森-香農距離
• 序列比對
• Soundex