Python文本相似性計(jì)算之編輯距離詳解

大家在做爬蟲的時(shí)候，很容易保持一些相似的數(shù)據(jù)，這些相似的數(shù)據(jù)由于不完全一致，如果要通過人工一一的審核，將耗費(fèi)大量的時(shí)間，大家對(duì)編輯距離應(yīng)該有所了解，這篇文章我們先來了解下什么是編輯距離，然后在學(xué)習(xí)Python如何計(jì)算編輯距離，下面來一起學(xué)習(xí)學(xué)習(xí)吧。

編輯距離

編輯距離（Edit Distance），又稱Levenshtein距離，是指兩個(gè)字串之間，由一個(gè)轉(zhuǎn)成另一個(gè)所需的最少編輯操作次數(shù)。編輯操作包括將一個(gè)字符替換成另一個(gè)字符，插入一個(gè)字符，刪除一個(gè)字符。一般來說，編輯距離越小，兩個(gè)串的相似度越大。

例如將kitten一字轉(zhuǎn)成sitting：（'kitten' 和 ‘sitting' 的編輯距離為3）

sitten （k→s）

sittin （e→i）

sitting （→g）

Python中的Levenshtein包可以方便的計(jì)算編輯距離

包的安裝：pip install python-Levenshtein

我們來使用下：

上面的程序執(zhí)行結(jié)果為3，但是只改了一個(gè)字符，為什么會(huì)發(fā)生這樣的情況？

原因是Python將這兩個(gè)字符串看成string類型，而在 string 類型中，默認(rèn)的 utf-8 編碼下，一個(gè)中文字符是用三個(gè)字節(jié)來表示的。

解決辦法是將字符串轉(zhuǎn)換成unicode格式，即可返回正確的結(jié)果1。

接下來重點(diǎn)介紹下保重幾個(gè)方法的作用：

Levenshtein.distance(str1, str2)

計(jì)算編輯距離（也稱Levenshtein距離）。是描述由一個(gè)字串轉(zhuǎn)化成另一個(gè)字串最少的操作次數(shù)，在其中的操作包括插入、刪除、替換。算法實(shí)現(xiàn)：動(dòng)態(tài)規(guī)劃。   

Levenshtein.hamming(str1, str2)

計(jì)算漢明距離。要求str1和str2必須長(zhǎng)度一致。是描述兩個(gè)等長(zhǎng)字串之間對(duì)應(yīng)位置上不同字符的個(gè)數(shù)。   

Levenshtein.ratio(str1, str2)

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

計(jì)算jaro距離，Jaro Distance據(jù)說是用來判定健康記錄上兩個(gè)名字是否相同，也有說是是用于人口普查，我們先來看一下Jaro Distance的定義。

兩個(gè)給定字符串S1和S2的Jaro Distance為：

其中的m為s1, s2匹配的字符數(shù)，t是換位的數(shù)目。

兩個(gè)分別來自S1和S2的字符如果相距不超過

時(shí)，我們就認(rèn)為這兩個(gè)字符串是匹配的；而這些相互匹配的字符則決定了換位的數(shù)目t，簡(jiǎn)單來說就是不同順序的匹配字符的數(shù)目的一半即為換位的數(shù)目t。舉例來說，MARTHA與MARHTA的字符都是匹配的，但是這些匹配的字符中，T和H要換位才能把MARTHA變?yōu)镸ARHTA,那么T和H就是不同的順序的匹配字符，t=2/2=1。

兩個(gè)字符串的Jaro Distance即為：

Levenshtein.jaro_winkler(s1, s2)
計(jì)算Jaro–Winkler距離，而Jaro-Winkler則給予了起始部分就相同的字符串更高的分?jǐn)?shù)，他定義了一個(gè)前綴p，給予兩個(gè)字符串，如果前綴部分有長(zhǎng)度為ι的部分相同，則Jaro-Winkler Distance為：

dj是兩個(gè)字符串的Jaro Distance

ι是前綴的相同的長(zhǎng)度，但是規(guī)定最大為4

p則是調(diào)整分?jǐn)?shù)的常數(shù)，規(guī)定不能超過25，不然可能出現(xiàn)dw大于1的情況，Winkler將這個(gè)常數(shù)定義為0.1

這樣，上面提及的MARTHA和MARHTA的Jaro-Winkler Distance為：

個(gè)人覺得算法可以完善的點(diǎn)：

去除停用詞（主要是標(biāo)點(diǎn)符號(hào)的影響）

針對(duì)中文進(jìn)行分析，按照詞比較是不是要比按照字比較效果更好？

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家學(xué)習(xí)或者使用python能有所幫助