檢視萊文斯坦距離的原始碼

'''萊文斯坦距離'''，閣稱'''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」的萊文斯坦距離做三：

一 .'''k'''itten →'''s'''itten（k→s）
二 . sitt'''e'''n → sitt'''i'''n（e→i）
三 . sittin → sittin'''g'''（插入去 g）

==應用==

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

==演算法==

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

` ` `
'''int'''LevenshteinDistcance ('''string'''str 一 [一 . . lenStr 一] ,'''string'''str 二 [一 . . lenStr 二] )
'''int'''d [零 . . lenStr 一 , 零 . . lenStr 二]
'''int'''i , j , cost

'''for'''i=零 to lenStr 二
d [i , 零]   :=i
'''for'''j=零 to lenStr 一
d [零 , j]   :=j

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

'''return'''d [lenStr 一 , lenStr 二]
` ` `

==參見==

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

[[分類: 待校正]]