Python怎么計(jì)算編輯距離

這篇文章主要講解了“Python怎么計(jì)算編輯距離”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“Python怎么計(jì)算編輯距離”吧！

算法原理

在計(jì)算文本的相似性時(shí)，經(jīng)常會用到編輯距離。編輯距離，又稱Levenshtein距離，是指兩個(gè)字串之間，由一個(gè)轉(zhuǎn)成另一個(gè)所需的最少編輯操作次數(shù)。通常來說，編輯距離越小，兩個(gè)文本的相似性越大。這里的編輯操作主要包括三種：

• 插入：將一個(gè)字符插入某個(gè)字符串；

• 刪除：將字符串中的某個(gè)字符刪除；

• 替換：將字符串中的某個(gè)字符替換為另外一個(gè)字符。

下面通過示例來看一下。

將字符串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ì)算編輯距離呢？我們可以從較為簡單的情況進(jìn)行分析。

• 當(dāng)兩個(gè)字符串都為空串，那么編輯距離為0；

• 當(dāng)其中一個(gè)字符串為空串時(shí)，那么編輯距離為另一個(gè)非空字符串的長度；

• 當(dāng)兩個(gè)字符串均為非空時(shí)(長度分別為 i 和 j )，取以下三種情況最小值即可：

  1、長度分別為 i-1 和 j 的字符串的編輯距離已知，那么加1即可；

  2、長度分別為 i 和 j-1 的字符串的編輯距離已知，那么加1即可；

  3、長度分別為 i-1 和 j-1 的字符串的編輯距離已知，此時(shí)考慮兩種情況，若第i個(gè)字符和第j個(gè)字符不同，那么加1即可；如果不同，那么不需要加1。

很明顯，上述算法的思想即為動態(tài)規(guī)劃。

求長度為m和n的字符串的編輯距離，首先定義函數(shù)——edit(i, j)，它表示第一個(gè)長度為i的字符串與第二個(gè)長度為j的字符串之間的編輯距離。動態(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代碼也是極其簡潔的，這也是動態(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 range(1, len(str1) + 1):
        for j in range(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包可以用來計(jì)算編輯距離，安裝方法很簡單，直接安裝即可：

pip install python-Levenshtein

這樣我們就可以引入包直接計(jì)算編輯距離了：

import Levenshtein

str1 = 'batyu'
str2 = 'beauty'
print(Levenshtein.distance(str1, str2))

那么，Levenshtein包中還有沒有其它計(jì)算距離的方法呢？

這個(gè)包有很多計(jì)算距離的方法，包括如下：

• hamming(str1, str2)，計(jì)算長度相等的字符串str1和str2的漢明距離，即為兩個(gè)等長字串之間對應(yīng)位置上不同字符的個(gè)數(shù)。

• ratio(str1, str2)，計(jì)算萊文斯坦比。計(jì)算公式  r = (sum – ldist) / sum, 其中sum是指str1 和 str2 字串的長度總和，ldist是類編輯距離。注意這里是類編輯距離，在類編輯距離中刪除、插入依然+1，但是替換+2。

• jaro(str1, str2)，jaro_winkler(str1, str2)等等。

總結(jié)

• 可以用動態(tài)規(guī)劃算法求解字符串的編輯距離。

• PyPi包Levenshtein可以用來計(jì)算字符串的編輯距離，也可以計(jì)算其它類型的距離。

感謝各位的閱讀，以上就是“Python怎么計(jì)算編輯距離”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對Python怎么計(jì)算編輯距離這一問題有了更深刻的體會，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識點(diǎn)的文章，歡迎關(guān)注！