首頁  >  文章  >  後端開發  >  Python文字相似性計算之編輯距離詳解

Python文字相似性計算之編輯距離詳解

ringa_lee
ringa_lee原創
2018-05-14 16:26:156720瀏覽

編輯距離

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

例如將kitten一字轉換成sitting:('kitten' 和'sitting' 的編者距離為3)

     sen (k→s)

     s)(k→s)


        sitting (→g)


Python中的Levenshtein套件可以方便的計算編輯距離套件的安裝:

pip install python-Levenshteinin

<br>上面的程式執行結果為3,但是只改了一個字符,為什麼會發生這樣的情況?

原因是Python將這兩個字串看成string類型,而在 string 類型中,預設的 utf-8 編碼下,一個中文字元是用三個位元組來表示的。

解決方法是將字串轉換成unicode格式,即可傳回正確的結果1。

# -*- coding:utf-8 -*-
import Levenshtein
texta = &#39;艾伦 图灵传&#39;
textb = &#39;艾伦•图灵传&#39;
print Levenshtein.distance(texta,textb)

接下來重點介紹下保重幾個方法的作用:

# -*- coding:utf-8 -*-
import Levenshtein
texta = u&#39;艾伦 图灵传&#39;
textb = u&#39;艾伦•图灵传&#39;
print Levenshtein.distance(texta,textb)

in


Levenshtein.distance(str1, str2)

in

Levenshtein.hamming(str1, str2)

in

(距離計算編輯距離)。是描述由一個字符串轉換成另一個字符串最少的操作次數,在其中的操作包括插入、刪除、替換。演算法實作:動態規劃。

Levenshtein.ratio(str1, str2)

計算漢明距離。要求str1和str2必須長度一致。是描述兩個等長字符串之間對應位置上不同字元的個數。

Levenshtein.jaro(s1, s2)

計算萊文斯坦比。計算公式 

r = (sum – ldist) / sum

, 其中sum是指str1 和 str2 字串的長度總和,ldist是類別編輯距離。注意這裡是類別編輯距離,在類別編輯距離中刪除、插入依然+1,但替換+2。

Levenshtein.jaro_winkler(s1, s2)

計算jaro距離,Jaro Distance據說是用來判定健康記錄上兩個名字是否相同,也有說是用於人口普查,我們先來看一下Jaro Distance的定義。

兩個給定字串S1和S2的Jaro Distance為:


其中的m為s1, s2匹配的字元數,t是換位的數目。

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


時,我們就認為這兩個字符串是匹配的;而這些相互匹配的字符則決定了換位的數目t,簡單來說就是不同順序的匹配字元的數目的一半即為換位的數目t。舉例來說,MARTHA與MARHTA的字符都是匹配的,但是這些匹配的字符中,T和H要換位才能把MARTHA變為MARHTA,那麼T和H就是不同的順序的匹配字符,

t=2 /2=1


兩個字串的Jaro Distance即為:

dw = 0.944 + (3 * 0.1(1 − 0.944)) = 0.961

計算Jaro–Winkler距離,而Jarorrreee

計算Jaro–Winkler距離,而Jaro-Winkler-Winkler ,他定義了一個前綴p,給予兩個字串,如果前綴部分有長度為ι的部分相同,則Jaro-Winkler Distance為:



      dj是兩個字串的Jaro Distance
      ι是前綴的相同的長度,但是規定最大為4

      p則是調整分數的常數,規定不能超過25,不然可能出現dw大於1的情況,Winkler將這個常數定義為0.1這樣。 ,上述的MARTHA和MARHTA的Jaro-Winkler Distance為:

rrreee


個人覺得演算法可以完善的點:


標的作用是指的主要效果是指點名針對中文進行分析,依照詞比較是不是要比按照字比較效果好?

總結以上就是這篇文章的全部內容了,希望本文的內容對大家學習或者使用python能有所幫助,如果有疑問大家可以留言交流。

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn