編輯距離

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

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

     sitten （k→s）

     sittin （e→i）

     sitting （→g）

Python中的Levenshtein包可以方便的計算編輯距離

包的安裝： pip install python-Levenshtein


我們來使用下：

# -*- coding:utf-8 -*-import Levenshteintexta = '艾倫 圖靈傳'textb = '艾倫•圖靈傳'print Levenshtein.distance(texta,textb)

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

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

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

# -*- coding:utf-8 -*-import Levenshteintexta = u'艾倫 圖靈傳'textb = u'艾倫•圖靈傳'print Levenshtein.distance(texta,textb)

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

Levenshtein.distance(str1, str2)

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

Levenshtein.hamming(str1, str2)

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

Levenshtein.ratio(str1, str2)

計算萊文斯坦比。計算公式  r = (sum