Last Updated on 2021-07-05 by Clay
前言
在我們進行自然語言處理 (NLP) 任務的時候，有時候，我們會需要進行『兩個句子』的比對，好用來確認他們兩者之間相似不相似 —— 當然，如果想要比較文本，也是可以這麼做，不過稍微有點少見。
在想要比對兩個句子是否相似的時候，除了現在相當熱門的使用詞向量、句向量、TF-IDF 來比較之外，使用所謂的『最短編輯距離』(Minimum Edit Distance) 也是一個相當常見的方法，而且好處是計算速度相當地快。
本篇文章便紀錄了最短編輯距離的公式，以及該如何使用 Python 來實作這樣的計算方法。
最短編輯距離 (Minimum Edit Distance)
首先來看下 WIKI 的解釋：
編輯距離是針對二個字符串（例如英文字）的差異程度的量化量測，量測方式是看至少需要多少次的處理才能將一個字符串變成另一個字符串。
—— From Wiki
編輯距離是針對二個字符串（例如英文字）的差異程度的量化量測，量測方式是看至少需要多少次的處理才能將一個字符串變成另一個字符串。編輯距離可以用在自然语言处理中，例如拼寫檢查可以根據一個拼錯的字和其他正確的字的編輯距離，判斷哪一個（或哪幾個）是比較可能的字。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的最小處理方式如下：
kitten → sitten（將k改為s）
sitten → sittin（將e改為i）
sittin → sitting（最後加入g）
若是考慮LCS距離（只考慮加入及刪除），LCS距離是5：
刪除位在第1個字的k
在第1個字之前加入s
刪除位在第4個字的e
在第4個字之前加入i
在第6個字之前加入g
簡單來講，所謂的『最短編輯距離』，指的便是如何透過使用『修改』、『增加』、『刪除』等動作，將一個句子完全替換成另外一個句子的最少『步驟』—— 這就是兩個句子之間的最短編輯距離。
程式碼
首先，我們來看下虛擬碼：
其實我覺得挺麻煩的......哈哈哈，本來寫了個版本，雖然可以跑，可是似乎沒有線上解題網站上標準答案的正解高效，故最後又揉合了重寫。
def MED(sent_01, sent_02): n = len(sent_01) m = len(sent_02) matrix = [[i+j for j in range(m+1)] for i in range(n+1)] for i in range(1, n+1): for j in range(1, m+1): if sent_01[i-1] == sent_02[j-1]: d = 0 else: d = 1 matrix[i][j] = min(matrix[i-1][j]+1, matrix[i][j-1]+1, matrix[i-1][j-1]+d) distance_score = matrix[n][m] return distance_score
Reference
- https://www.slideshare.net/shkulathilake/nlpkashkminimum-edit-distance
- https://web.stanford.edu/class/cs124/lec/med.pdf
- https://www.geeksforgeeks.org/edit-distance-dp-5/