萊文斯坦距離

萊文斯坦距離(英語:Levenshtein distance)是編輯距離的一種。指兩個字串之間,由一個轉成另一個所需的最少編輯操作次數。

允許的編輯操作包括:

  1. 將一個字符替換成另一個字符
  2. 插入一個字符
  3. 刪除一個字符

俄羅斯科學家弗拉基米爾·萊文斯坦在1965年提出這個概念[1][2]

定義

編輯

如果分別用    表示   兩個字符串的長度,那麼它們的列文斯坦距離為  ,它符合:

 

  是一個指示函數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]

參見

編輯

參考文獻

編輯
  1. ^ 王淼; 蔡忠閩; 沈超; 華濤. 行为截获技术对鼠标动力学身份认证的影响. 微電子學與計算機. 2013-04-01, 30 (4): 14–21 [2023-12-20]. ISSN 1000-7180. (原始內容存檔於2023-12-20) (中文). 
  2. ^ В. И. Левенштейн. Двоичные коды с исправлением выпадений, вставок и замещений символов [能夠糾正刪除、插入和反轉的二進制代碼]. Доклады Академии Наук СССР. 1965, 163 (4): 845–848 (俄語).