編輯距離

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

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

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

例子

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