在Windows下,python-Lev

(1)首先下載python-Levenshtein 網址:https://pypi.python.org/pypi/python-Levenshtein/0.10.2 (2)在切換到第三方包所在目錄下,執行pip setup.py install 的命令後,報錯「microsoft visual c++ 9.0 is required「,這是因為:Windows下使用pip安裝包的時候,需要機器裝有VS2008或VS2010才行, 如果不想裝VS,可以安裝一個Micorsoft Visual C++ Compiler for Python 2.7的包。下載網址:https://www.microsoft.com/en-us/download/confirmation.aspx?id=44266 (3)然後再cd /d +文件目錄 執行pip setup.py install 命令。 (4)驗證Levenshtein是否安裝成功。from Levenshtein import*;看是否報錯。 (5)簡單的實現代碼 注意若使用」from Levenshtein import*「導入,則在調用函數時,不用加Levenshtein; Levenshtein.distance(str1,str2)函數 計算編輯距離是描述一個字符串轉化成另一個字符串最少的操作次數,在其中的操作包括插入、刪除、替換。

>>>distance('abc','ac')  >1                          由abc刪除b得到ac操作一次  >distance('kitten','sitting')  >3                          kitten(k先替換為s)sitten(e替換為i)sittin(最後添加g)sitting  >>>ratio('abc','ac')  >0.8

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

>>>hamming('abc','cba')  >2  >>>hamming('abc','cam')  >3

Levenshtein.distance(str1,str2) 計算萊文斯坦比。計算公式r = (sum-Idist)/sum, 其中sum是指str1和str2字串的長度總和,Idist是類編輯距離:這裡的類編輯距離不是1中所說的編輯距離,1中三種操作中每個操作+1,而此處,刪除,插入依然+1,但是替換+2 這樣設計的目的:ratio(『a』,』c』), sum = 2,按1中的計算為(2-1)/2 = 0.5, 但是『a』,』c』顯然沒有重合,不合算,但是替換操作+2,就可以解決這個問題。

>>>ratio('abc','abc')   (6-0)/6=1  >1.0  >>>ratio('abc','ab')    (6-1)/6=0.8  >0.8  >>>ratio('abc','abd')   (6-2)/6=0.6666666666  >0.66666666666

(6)編輯距離實現要動態規劃:參考:https://www.microsoft.com/en-us/download/confirmation.aspx?id=44266