萊文斯坦距離

萊文斯坦距離，閣稱Levenshtein 距離，是編輯距離的一種。指兩个字串之間，由一个轉做另外一个所需的上少編輯操作次數。

允准的編輯操作包括：

一 . 共一字符替換做另外一字符二 . 插一字符仔三 . 刪除一字符俄羅斯科學家陽拉基米爾 ・ 萊文斯坦在一九六五年提出這个概念。

定義

若是分別用 $ | a | $ 和 $ | b | $ 表示 $ a , b $ 兩字符串的長度，按呢𪜶的列文斯坦距離做 $ \ operatorname { lev } _ { a , b } ( | a | , | b | ) $，伊符合著：

$ \ qquad \ operatorname { lev } _ { a , b } ( i , j )={ \ begin { cases } \ max ( i , j ) & { \ text { if } } \ min ( i , j )=零 , \ \ \ min { \ begin { cases } \ operatorname { lev } _ { a , b } ( i 影一 , j ) + 一 \ \ \ operatorname { lev } _ { a , b } ( i , j 影一 ) + 一 \ \ \ operatorname { lev } _ { a , b } ( i 影一 , j 影一 ) + 一 _ { ( a _ { i } \ neq b _ { j } ) } \ end { cases } } & { \ text { otherwise . } } \ end { cases } } $

$ 一 _ { ( a _ { i } \ neq b _ { j } ) } $ 是一个指示函數（'indicator'function）， 當 $ a _ { i }=b _ { j } $ 時，其值為零，其他的時陣伊等於一。

$ \ operatorname { lev } _ { a , b } ( i , j ) $ 表示 $ a $ 的前 $ i $ 字符佮 $ b $ 的前 $ j $ 個字符之間的列文斯坦距離。（$ i $ 和 $ j $ 攏是對一開始的下標）

注意：min 運算中的頭一个公式代表（對 $ a $ 中）刪除字符（以到位 $ b $）； 第二个公式代表插入字符；第三个代表替換（決定做前字符是毋是有仝款）

比如講

將「kitten」一字轉做「sitting」的萊文斯坦距離做三：

一 .kitten →sitten（k→s） 二 . sitten → sittin（e→i） 三 . sittin → sitting（插入去 g）

應用

• DNA 分析
• 拼寫檢查
• 語音辨識
• 操人偵測

演算法

動態規劃不時予人用來做這个問題的解決手段之一。

` ` ` intLevenshteinDistcance (stringstr 一 [一 . . lenStr 一] ,stringstr 二 [一 . . lenStr 二] ) intd [零 . . lenStr 一 , 零 . . lenStr 二] inti , j , cost

fori=零 to lenStr 二 d [i , 零]   :=i forj=零 to lenStr 一 d [零 , j]   :=j

fori=一 to lenStr 二 forj=一 to lenStr 一 ifstr 二 [i]=str 一 [j] cost  :=零 else cost  :=一 d [i , j]   :=min ( d [i 影一 , j] + 一 , _ / / 鋪排 _ d [i , j 影一] + 一 , _ / / 插入去 _ d [i 影一 , j 影一] + cost _ / / 替換 _ )

returnd [lenStr 一 , lenStr 二] ` ` `

參見

• 漢明距離
• 延森-香農離
• 序列比對
• Soundex
• 上長公共子序列
• Floyd-Warshall 算法
• Viterbi 算法