編輯距離 編輯距離是針對二個字符串例如英文字的差異程度的量化量測量測方式是看至少需要多少次的處理才能將一個字符串變成另一個字符串編輯距離可以用在自然语言处理中例如拼寫檢查可以根據一個拼錯的字和其他正確的字的編輯距離判斷哪一個或哪幾個是比較可能的字DNA也可以視為用ACG和T組成的字符串因此編輯距離也用在生物信息学中判斷二個DNA的類似程度Unix 下的 diff 及 patch 即是利用编辑距离来进行文本编辑对比的例子 編輯距離有幾種不同的定義差異在可以對字符串進行的處理 在萊文斯坦距離中可以刪除加入取代字符串中的任何一個字元也是較常用的編輯距離定義常常提到編輯距離時指的就是萊文斯坦距離 也存在其他編輯距離的定義方式例如 DamerauLevenshtein 距离是一种莱文斯坦距离的变种但允许以单一操作交换相邻的两个字符称为字符转置如 ABBA 的距离是 交换而非 先删除再插入或者两次替换 LCS最长公共子序列距離只允許刪除加入字元 Jaro 距离只允许字符转置 汉明距离只允許取代字元