編輯距離

维基百科,自由的百科全书
跳转至: 导航搜索

編輯距離是針對二個字符串(例如英文字)的差異程度的量化量測,量測方式是看至少需要多少次的處理才能將一個字符串變成另一個字符串。編輯距離可以用在自然语言处理中,例如拼寫檢查可以根據一個拼錯的字和其他正確的字的編輯距離,判斷哪一個(或哪幾個)是比較可能的字。DNA也可以視為用A、C、G和T組成的字符串,因此編輯距離也用在生物信息学中,判斷二個DNA的類似程度。

編輯距離有幾種不同的定義,差異在可以對字符串進行的處理。在萊文斯坦距離中,可以對刪除、加入、取代字符串中的任何一個字元,也是較常用的編輯距離定義,常常提到編輯距離時,指的就是萊文斯坦距離[1]

也存在其他編輯距離的定義方式,包括只允許刪除、加入字符串中任何一個字元的LCS(最长公共子序列)距離[1]:37,若針對相同長度的字符串,也可以用只允許取代字符串中任何一個字元的汉明距离[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.