基本介紹
Levenshtein distance是一種度量?jī)蓚€(gè)序列(字符串)差異大小的方法骇吭。
該方法定義如下：
兩個(gè)序列(以單詞為例歧寺，這里序列也可以表示一個(gè)句子)的Levenshtein distance是在使用一個(gè)單詞修改為另一個(gè)單詞時(shí)斜筐，通過(guò)編輯單個(gè)字符(如插入，刪除目代，修改)所需要的最小次數(shù)像啼。
這個(gè)概念由俄羅斯數(shù)學(xué)家Vladimir Levenshtein于1965年提出潭苞。目前這個(gè)距離常用來(lái)評(píng)價(jià)字符識(shí)別任務(wù)的好壞此疹。
舉個(gè)例子
將單詞“kitten”修改為“sitting”最少需要3次單字符的操作：
- kitten -> sitten(將“k”改為“s”)
- sitten -> sittin(將“e”改為“i”)
- sittin -> sitting(將“g”刪除)
原理
假設(shè)現(xiàn)在兩個(gè)字符串A和B蝗碎，其中A的長(zhǎng)度為a蹦骑，B的長(zhǎng)度為b，現(xiàn)要計(jì)算A與B之間的Levenshtein distance
我們可以考慮使用動(dòng)態(tài)規(guī)劃的思想解決這個(gè)問(wèn)題
假設(shè)和
分別為字符串A边败、B的前
個(gè)字符組成的子串登疗，現(xiàn)在我們來(lái)看看將
修改為
需要的最少編輯次數(shù)，即兩個(gè)子串的Levenshtein distance脱吱，下面我們來(lái)分別討論三種操作的操作次數(shù)：
- 插入操作
假設(shè)將修改為
需要操作數(shù)為
急凰，那么在
后插入一個(gè)字符
，這樣就可以將
修改為
乔外，這時(shí)所需要的操作數(shù)為
2.刪除操作
假設(shè)將修改為
需要操作數(shù)為
一罩，那么刪除
就可以將
修改為
杨幼，這時(shí)所需要的操作數(shù)為
3.修改操作
假設(shè)將修改為
需要操作數(shù)為
，這時(shí)要將
修改為
分兩種情況：
a. 聂渊，則將
替換成
即可完成修改差购，這時(shí)操作數(shù)為
b. ，則將不需要進(jìn)行修改操作汉嗽，操作數(shù)仍為
?
最后可以得到狀態(tài)轉(zhuǎn)移方程如下
上式中表示
表達(dá)式取0欲逃，否則取1
Python代碼如下
得到上述轉(zhuǎn)移方程后我們就很容易寫出下面程序了
1.按照上述公式編寫，沒(méi)做優(yōu)化的情況
import numpy as np
def Lev_distance():
A = "fafasa"
B = "faftreassa"
dp = np.zeros((len(A) + 1, len(B) + 1))
for i in xrange(len(A) + 1):
dp[i][0] = i
for j in xrange(len(B) + 1):
dp[0][j] = j
for i in xrange(1, len(A) + 1):
for j in xrange(1, len(B) + 1):
if A[i - 1] == B[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(dp[i - 1][j - 1], min(dp[i][j - 1], dp[i - 1][j])) + 1
print("Levenshtein distance: {}".format(dp[len(A)][len(B)]))
if __name__=="__main__":
Lev_distance()
2.使用滾動(dòng)數(shù)組優(yōu)化上述代碼
import numpy as np
def Lev_distance():
A = "fafasa"
B = "faftreassa"
dp = np.array(np.arange(len(B)+1))
for i in xrange(1, len(A)+1):
temp1 = dp[0]
dp[0] += 1
for j in xrange(1, len(B)+1):
temp2 = dp[j]
if A[i-1] == B[j-1]:
dp[j] = temp1
else:
dp[j] = min(temp1, min(dp[j-1], dp[j]))+1
temp1 = temp2
print("Levenshtein distance: {}".format(dp[len(B)]))
if __name__=="__main__":
Lev_distance()
參考
[1] https://en.wikipedia.org/wiki/Levenshtein_distance
[2] http://www.cnblogs.com/BlackStorm/p/5400809.html
歡迎加入OCR交流群：785515057(此群已滿)
歡迎加入OCR交流群2：826714963
