編輯距離

編輯距離是針對二個字元串（例如英文字）的差異程度的量化量測，量測方式是看至少需要多少次的處理才能將一個字元串變成另一個字元串。編輯距離可以用在自然語言處理中，例如拼寫檢查可以根據一個拼錯的字和其他正確的字的編輯距離，判斷哪一個（或哪幾個）是比較可能的字。DNA也可以視為用A、C、G和T組成的字元串，因此編輯距離也用在生物信息學中，判斷二個DNA的類似程度。Unix 下的 diff 及 patch 即是利用編輯距離來進行文本編輯對比的例子。

基本介紹

• 中文名：編輯距離
• 外文名：Edit Distance
• 提出者：Vladimir Levenshtein
• 提出時間：1965年

簡介

編輯距離是針對二個字元串（例如英文字）的差異程度的量化量測，量測方式是看至少需要多少次的處理才能將一個字元串變成另一個字元串。編輯距離可以用在自然語言處理中，例如拼寫檢查可以根據一個拼錯的字和其他正確的字的編輯距離，判斷哪一個（或哪幾個）是比較可能的字。DNA也可以視為用A、C、G和T組成的字元串，因此編輯距離也用在生物信息學中，判斷二個DNA的類似程度。Unix下的diff及patch即是利用編輯距離來進行文本編輯對比的例子。

編輯距離有幾種不同的定義，差異在可以對字元串進行的處理。

• 在萊文斯坦距離中，可以刪除、加入、取代字元串中的任何一個字元，也是較常用的編輯距離定義，常常提到編輯距離時，指的就是萊文斯坦距離。
  
• 也存在其他編輯距離的定義方式，例如 Damerau-Levenshtein 距離是一種萊文斯坦距離的變種，但允許以單一操作交換相鄰的兩個字元（稱為字元轉置），如 AB→BA 的距離是 1（交換）而非 2（先刪除再插入、或者兩次替換）。
  
• LCS（最長公共子序列）距離只允許刪除、加入字元。
  
• Jaro 距離只允許字元轉置。
  
• 漢明距離只允許取代字元。
  

萊文斯坦距離

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

例如將kitten一字轉成sitting：

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

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

例子

kitten和sitting的萊文斯坦距離是3。將kitten變為sitting的最小處理方式如下：

1. kitten →sitten（將k改為s）
   
2. sitten → sittin（將e改為i）
   
3. sittin → sitting（最後加入g）
   

若是考慮LCS距離（只考慮加入及刪除），LCS距離是5：

1. 刪除位在第1個字的k
   
2. 在第1個字之前加入s
   
3. 刪除位在第4個字的e
   
4. 在第4個字之前加入i
   
5. 在第6個字之後加入g