Python實(shí)現(xiàn)計算最小編輯距離
更新時間：2016年03月17日 11:23:15 投稿：hebedich
這篇文章主要介紹了Python實(shí)現(xiàn)計算最小編輯距離的相關(guān)代碼，有需要的小伙伴可以參考下
最小編輯距離或萊文斯坦距離（Levenshtein），指由字符串A轉(zhuǎn)化為字符串B的最小編輯次數(shù)。允許的編輯操作有：刪除，插入，替換。具體內(nèi)容可參見：維基百科—萊文斯坦距離。一般代碼實(shí)現(xiàn)的方式都是通過動態(tài)規(guī)劃算法，找出從A轉(zhuǎn)化為B的每一步的最小步驟。從Google圖片借來的圖，
Python代碼實(shí)現(xiàn), （其中要注意矩陣的下標(biāo)從1開始，而字符串的下標(biāo)從0開始）：
def normal_leven(str1, str2):
len_str1 = len(str1) + 1
len_str2 = len(str2) + 1
#create matrix
matrix = [0 for n in range(len_str1 * len_str2)]
#init x axis
for i in range(len_str1):
matrix[i] = i
#init y axis
for j in range(0, len(matrix), len_str1):
if j % len_str1 == 0:
matrix[j] = j // len_str1
for i in range(1, len_str1):
for j in range(1, len_str2):
if str1[i-1] == str2[j-1]:
cost = 0
else:
cost = 1
matrix[j*len_str1+i] = min(matrix[(j-1)*len_str1+i]+1,
matrix[j*len_str1+(i-1)]+1,
matrix[(j-1)*len_str1+(i-1)] + cost)
return matrix[-1]
最近看文章看到Python庫提供了一個包difflib實(shí)現(xiàn)了從對象A轉(zhuǎn)化對象B的步驟，那么計算最小編輯距離的代碼也可以這樣寫了：
def difflib_leven(str1, str2):
leven_cost = 0
s = difflib.SequenceMatcher(None, str1, str2)
for tag, i1, i2, j1, j2 in s.get_opcodes():
#print('{:7} a[{}: {}] --> b[{}: {}] {} --> {}'.format(tag, i1, i2, j1, j2, str1[i1: i2], str2[j1: j2]))
if tag == 'replace':
leven_cost += max(i2-i1, j2-j1)
elif tag == 'insert':
leven_cost += (j2-j1)
elif tag == 'delete':
leven_cost += (i2-i1)
return leven_cost
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了OpenCV實(shí)現(xiàn)圖像濾波之雙邊濾波，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-10-10
Python Pygame實(shí)現(xiàn)兔子獵人守護(hù)城堡游戲
這篇文章主要介紹了用python來制作的一個守護(hù)類小游戲兔子獵人守護(hù)城堡，文中的示例代碼介紹得很詳細(xì)，感興趣的小伙伴快來跟隨小編一起學(xué)習(xí)學(xué)習(xí)吧2021-12-12
Python中內(nèi)置數(shù)據(jù)類型list,tuple,dict,set的區(qū)別和用法
這篇文章主要給大家介紹了Python中內(nèi)置數(shù)據(jù)類型list,tuple,dict,set的區(qū)別和用法，都是非常基礎(chǔ)的知識，十分的細(xì)致全面，有需要的小伙伴可以參考下。2015-12-12
這篇文章主要介紹了Pytorch之?dāng)U充tensor的操作，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-03-03
這篇文章主要為大家詳細(xì)介紹了python實(shí)現(xiàn)最小二乘法線性擬合，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-07-07
這篇文章主要介紹了如何利用PyQT5制作一個桌面摸魚工具，利用摸魚，打開小說，可實(shí)行完美摸魚，實(shí)時保存進(jìn)度，快來跟隨小編一起動手試一試吧2022-02-02
今天小編就為大家分享一篇關(guān)于在Python中使用Neo4j的方法，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-03-03
python利用pyttsx3 API實(shí)現(xiàn)文本轉(zhuǎn)語音處理
這篇文章主要為大家詳細(xì)介紹了Python如何利用pyttsx3 API實(shí)現(xiàn)文本轉(zhuǎn)語音處理，文中有詳細(xì)的示例代碼，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-06-06
python多進(jìn)程下實(shí)現(xiàn)日志記錄按時間分割
這篇文章主要為大家詳細(xì)介紹了python多進(jìn)程下實(shí)現(xiàn)日志記錄按時間分割，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-07-07
Keras使用ImageNet上預(yù)訓(xùn)練的模型方式
這篇文章主要介紹了Keras使用ImageNet上預(yù)訓(xùn)練的模型方式，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-05-05