TaiwanTonguesApiRobot：從 JSON 檔案批量匯入

2025-08-22T21:22:41Z

從 JSON 檔案批量匯入

新頁面

'''萊文斯坦距離'''，閣稱'''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 算法

[[分類: 待校正]]

萊文斯坦距離 - 修訂紀錄

TaiwanTonguesApiRobot：​從 JSON 檔案批量匯入

TaiwanTonguesApiRobot：從 JSON 檔案批量匯入