Python如何計(jì)算編輯距離？
算法原理
大家好，歡迎來(lái)到 Crossin的編程教室 ！
在計(jì)算文本的相似性時(shí)，經(jīng)常會(huì)用到編輯距離。編輯距離，又稱Levenshtein距離，是指兩個(gè)字串之間，由一個(gè)轉(zhuǎn)成另一個(gè)所需的最少編輯操作次數(shù)。通常來(lái)說，編輯距離越小，兩個(gè)文本的相似性越大。這里的編輯操作主要包括三種：
插入：將一個(gè)字符插入某個(gè)字符串；
刪除：將字符串中的某個(gè)字符刪除；
替換：將字符串中的某個(gè)字符替換為另外一個(gè)字符。
下面通過示例來(lái)看一下。
將字符串batyu變?yōu)閎eauty，編輯距離是多少呢？這需要經(jīng)過如下步驟：
1、batyu變?yōu)閎eatyu（插入字符e）
2、beatyu變?yōu)閎eaty（刪除字符u）
3、beaty變?yōu)閎eauty（插入字符u）
所以編輯距離為3。
那么，如何用Python計(jì)算編輯距離呢？我們可以從較為簡(jiǎn)單的情況進(jìn)行分析。
當(dāng)兩個(gè)字符串都為空串，那么編輯距離為0；
當(dāng)其中一個(gè)字符串為空串時(shí)，那么編輯距離為另一個(gè)非空字符串的長(zhǎng)度；
當(dāng)兩個(gè)字符串均為非空時(shí)(長(zhǎng)度分別為 i 和 j )，取以下三種情況最小值即可：
1、長(zhǎng)度分別為 i-1 和 j 的字符串的編輯距離已知，那么加1即可；
2、長(zhǎng)度分別為 i 和 j-1 的字符串的編輯距離已知，那么加1即可；
3、長(zhǎng)度分別為 i-1 和 j-1 的字符串的編輯距離已知，此時(shí)考慮兩種情況，若第i個(gè)字符和第j個(gè)字符不同，那么加1即可；如果不同，那么不需要加1。
很明顯，上述算法的思想即為動(dòng)態(tài)規(guī)劃。
求長(zhǎng)度為m和n的字符串的編輯距離，首先定義函數(shù)——edit(i, j)，它表示第一個(gè)長(zhǎng)度為i的字符串與第二個(gè)長(zhǎng)度為j的字符串之間的編輯距離。動(dòng)態(tài)規(guī)劃表達(dá)式可以寫為：
if i == 0 且 j == 0，edit(i, j) = 0
if （i == 0 且 j > 0?）或者 （i > 0 且j == 0），edit(i, j) = i + j
if i ≥ 1 ?且 j ≥ 1 ，edit(i, j) == min{ edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1, j-1) + d(i, j) }，當(dāng)?shù)谝粋€(gè)字符串的第i個(gè)字符不等于第二個(gè)字符串的第j個(gè)字符時(shí)，d(i, j) = 1；否則，d(i, j) = 0。
最終的編輯距離即為edit(m,n)。上述示例的edit矩陣可以表示如下：
Python代碼實(shí)現(xiàn)
Talk is cheap. Show me the code. Python代碼也是極其簡(jiǎn)潔的，這也是動(dòng)態(tài)規(guī)劃的魅力：
def editdistance(str1, str2):
? ?'''
? ?計(jì)算字符串str1和str2的編輯距離
? ?:param str1:
? ?:param str2:
? ?:return:
? ?'''
? ?edit = [[i + j for j in range(len(str2) + 1)] for i in range(len(str1) + 1)]
? ?for i in xrange(1, len(str1) + 1):
? ? ? ?for j in xrange(1, len(str2) + 1):
? ? ? ? ? ?if str1[i - 1] == str2[j - 1]:
? ? ? ? ? ? ? ?d = 0
? ? ? ? ? ?else:
? ? ? ? ? ? ? ?d = 1
? ? ? ? ? ?edit[i][j] = min(edit[i - 1][j] + 1, edit[i][j - 1] + 1, edit[i - 1][j - 1] + d)
? ?return edit[len(str1)][len(str2)]擴(kuò)展
那么，Python功能這么強(qiáng)大，有沒有計(jì)算編輯距離的包呢？
答案是肯定的，Python中的Levenshtein包可以用來(lái)計(jì)算編輯距離，安裝方法很簡(jiǎn)單，直接安裝即可：
pip install python-Levenshtein這樣我們就可以引入包直接計(jì)算編輯距離了：
import Levenshtein
str1 = 'batyu'
str2 = 'beauty'
print Levenshtein.distance(str1, str2)有同學(xué)可能想計(jì)算漢字之間的編輯距離，如下：
import Levenshtein
str1 = 'Python那些事'
str2 = 'Python那些事！'
print Levenshtein.distance(str1, str2)得到的結(jié)果是3而不是1。這是因?yàn)樵谧址幋a為utf-8時(shí)，一個(gè)漢字占用3個(gè)字節(jié)。改為unicode編碼即可得到1，即：
import Levenshtein
str1 = u'Python那些事'
str2 = u'Python那些事！'
print Levenshtein.distance(str1, str2)那么，Levenshtein包中還有沒有其它計(jì)算距離的方法呢？
這個(gè)包有很多計(jì)算距離的方法，包括如下：
hamming(str1, str2)，計(jì)算長(zhǎng)度相等的字符串str1和str2的漢明距離，即為兩個(gè)等長(zhǎng)字串之間對(duì)應(yīng)位置上不同字符的個(gè)數(shù)。
ratio(str1, str2)，計(jì)算萊文斯坦比。計(jì)算公式? r = (sum – ldist) / sum, 其中sum是指str1 和 str2 字串的長(zhǎng)度總和，ldist是類編輯距離。注意這里是類編輯距離，在類編輯距離中刪除、插入依然+1，但是替換+2。
jaro(str1, str2)，jaro_winkler(str1, str2)等等。
總結(jié)
可以用動(dòng)態(tài)規(guī)劃算法求解字符串的編輯距離。
PyPi包Levenshtein可以用來(lái)計(jì)算字符串的編輯距離，也可以計(jì)算其它類型的距離。
_往期文章推薦_