Python怎么計算編輯距離

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

算法原理

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

• 插入：將一個字符插入某個字符串；

• 刪除：將字符串中的某個字符刪除；

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

下面通過示例來看一下。

將字符串batyu變為beauty，編輯距離是多少呢？這需要經過如下步驟：

1、batyu變為beatyu（插入字符e）

2、beatyu變為beaty（刪除字符u）

3、beaty變為beauty（插入字符u）

所以編輯距離為3。

那么，如何用Python計算編輯距離呢？我們可以從較為簡單的情況進行分析。

• 當兩個字符串都為空串，那么編輯距離為0；

• 當其中一個字符串為空串時，那么編輯距離為另一個非空字符串的長度；

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

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

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

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

很明顯，上述算法的思想即為動態規劃。

求長度為m和n的字符串的編輯距離，首先定義函數——edit(i, j)，它表示第一個長度為i的字符串與第二個長度為j的字符串之間的編輯距離。動態規劃表達式可以寫為：

• 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) }，當第一個字符串的第i個字符不等于第二個字符串的第j個字符時，d(i, j) = 1；否則，d(i, j) = 0。

最終的編輯距離即為edit(m,n)。上述示例的edit矩陣可以表示如下：

Python代碼實現

Talk is cheap. Show me the code. Python代碼也是極其簡潔的，這也是動態規劃的魅力：

def editdistance(str1, str2):
    '''
    計算字符串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)]

擴展

那么，Python功能這么強大，有沒有計算編輯距離的包呢？

答案是肯定的，Python中的Levenshtein包可以用來計算編輯距離，安裝方法很簡單，直接安裝即可：

pip install python-Levenshtein

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

import Levenshtein

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

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

這個包有很多計算距離的方法，包括如下：

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

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

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

總結

• 可以用動態規劃算法求解字符串的編輯距離。

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

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