Python實(shí)現(xiàn)計(jì)算最小編輯距離
更新時(shí)間：2016年03月17日 11:23:15 投稿：hebedich
這篇文章主要介紹了Python實(shí)現(xiàn)計(jì)算最小編輯距離的相關(guān)代碼，有需要的小伙伴可以參考下
最小編輯距離或萊文斯坦距離（Levenshtein），指由字符串A轉(zhuǎn)化為字符串B的最小編輯次數(shù)。允許的編輯操作有：刪除，插入，替換。具體內(nèi)容可參見(jiàn)：維基百科—萊文斯坦距離。一般代碼實(shí)現(xiàn)的方式都是通過(guò)動(dòng)態(tài)規(guī)劃算法，找出從A轉(zhuǎn)化為B的每一步的最小步驟。從Google圖片借來(lái)的圖，
Python代碼實(shí)現(xiàn), （其中要注意矩陣的下標(biāo)從1開(kāi)始，而字符串的下標(biāo)從0開(kāi)始）：
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庫(kù)提供了一個(gè)包difflib實(shí)現(xiàn)了從對(duì)象A轉(zhuǎn)化對(duì)象B的步驟，那么計(jì)算最小編輯距離的代碼也可以這樣寫了：
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)文章
使用Python設(shè)計(jì)一個(gè)代碼統(tǒng)計(jì)工具
這篇文章主要介紹了使用Python設(shè)計(jì)一個(gè)代碼統(tǒng)計(jì)工具的相關(guān)資料，包括文件個(gè)數(shù)，代碼行數(shù)，注釋行數(shù)，空行行數(shù)。感興趣的朋友跟隨腳本之家小編一起看看吧2018-04-04
PyCharm搭建一勞永逸的開(kāi)發(fā)環(huán)境
這篇文章主要介紹了PyCharm搭建一勞永逸的開(kāi)發(fā)環(huán)境,本文通過(guò)圖文并茂的形式給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-04-04
pytorch 實(shí)現(xiàn)模型不同層設(shè)置不同的學(xué)習(xí)率方式
今天小編就為大家分享一篇pytorch 實(shí)現(xiàn)模型不同層設(shè)置不同的學(xué)習(xí)率方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-01-01
python批量telnet檢測(cè)IP地址的端口是否開(kāi)放
本文主要介紹了python批量telnet檢測(cè)IP地址的端口是否開(kāi)放，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-04-04
python matplotlib繪圖,修改坐標(biāo)軸刻度為文字的實(shí)例
今天小編就為大家分享一篇python matplotlib繪圖,修改坐標(biāo)軸刻度為文字的實(shí)例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2018-05-05
在本篇文章里小編給大家分享的是一篇關(guān)于python中寫類的方法和技巧，需要的朋友們可以學(xué)習(xí)下。2020-06-06
爬蟲代理池Python3WebSpider源代碼測(cè)試過(guò)程解析
這篇文章主要介紹了爬蟲代理池Python3WebSpider源代碼測(cè)試過(guò)程解析,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-12-12
這篇文章主要介紹了python中的全局變量用法,詳細(xì)分析了Python全局變量使用中的利弊與相關(guān)技巧,需要的朋友可以參考下2015-06-06
本文主要介紹了Python模塊域名dnspython解析，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-08-08
python argparse命令行參數(shù)解析(推薦)
Python argparse模塊是解析命令行參數(shù)的首選方法。解析命令行參數(shù)是一個(gè)非常常見(jiàn)的任務(wù)，Python腳本根據(jù)傳遞的值來(lái)執(zhí)行和操作2021-06-06