編輯距離

編輯距離是針對二個字符串（例如英文字）的差異程度的量化量測，量測方式是看至少需要多少次的處理才能將一個字符串變成另一個字符串。編輯距離可以用在自然语言处理中，例如拼寫檢查可以根據一個拼錯的字和其他正確的字的編輯距離，判斷哪一個（或哪幾個）是比較可能的字。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

參考資料

[编辑]
  1. ^ 1.0 1.1 1.2 Navarro, Gonzalo. A guided tour to approximate string matching (PDF). ACM Computing Surveys. 1 March 2001, 33 (1): 31–88 [19 March 2015]. doi:10.1145/375360.375365. （原始内容 (PDF)存档于2021-04-19）.