轉載:https://www.cnblogs.com/BlackStorm/p/5400809.html
基本介紹
Levenshtein距離是一種計算兩個字元串間的差異程度的字元串度量(string metric)。我們可以認為Levenshtein距離就是從一個字元串修改到另一個字元串時,其中編輯單個字元(比如修改、插入、删除)所需要的最少次數。俄羅斯科學家Vladimir Levenshtein于1965年提出了這一概念。
簡單例子
從字元串“kitten”修改為字元串“sitting”隻需3次單字元編輯操作,如下:
-
- sitten ( k -> s )
- sittin ( e -> i )
- sitting ( _ -> g )
是以“kitten”和“sitting”的Levenshtein距離為3。
實作思想
如何程式設計實作這一算法呢?許多人試圖用矩陣來解釋,但實際上矩陣是最終可視化的工具,配合了解“為什麼”比較友善,但從矩陣卻比較難想到“怎麼做”。
我們試圖找到“從字元串A
A修改到字元串BB”這一問題的子解結構。當然反過來說“從字元串BB修改到字元串AA”和它是同一個問題,因為從AA中删掉一個字元來比對BB,就相當于在BB中插入一個字元來比對A
A,這兩個操作是可以互相轉化的。
假設字元序列A[1…i]
A[1…i]、B[1…j]B[1…j]分别是字元串AA、BB的前ii、jj個字元構成的子串,我們得到一個子問題是“從字元串A[1…i]A[1…i]修改到字元串B[1…j]B[1…j]”:⎡⎣⎢A:B:A[1]B[1]A[2]B[2]⋯⋯A[i−2]B[j−2]A[i−1]B[j−1]A[i]B[j]⎤⎦⎥
⎣⎡A:B:A[1]B[1]A[2]B[2]⋯⋯A[i−2]B[j−2]A[i−1]B[j−1]A[i]B[j]⎦⎤
① 插入操作:
-
- 當将A[1…i]
A[1…i]修改成B[1…j−1]B[1…j−1]需要操作數為op1op1,那麼我插入一個字元A[i']=B[i]A[i′]=B[i]到A[i]A[i]和A[i+1]A[i+1]之間,用以比對B[i]B[i],于是A[1…i]A[1…i]修改到B[1…j]B[1…j]所需操作數為op1+1op1+1。⎡⎣⎢⋯⋯A[i−2]B[j−2]A[i−1]B[j−1]A[i]B[j]A[i′]ϕ⎤⎦⎥
-
- ⎣⎡⋯⋯A[i−2]B[j−2]A[i−1]B[j−1]A[i]B[j]A[i′]ϕ⎦⎤
② 删除操作:
-
- 當将A[1…i−1]
A[1…i−1]修改成B[1…j]B[1…j]需要操作數為op2op2,那麼我删掉字元A[i]A[i]也可以op2+1op2+1的操作數使兩個子字元串比對:⎡⎣⎢⋯⋯A[i−2]B[j−2]A[i−1]B[j−1]ϕB[j]⎤⎦⎥
-
- ⎣⎡⋯⋯A[i−2]B[j−2]A[i−1]B[j−1]ϕB[j]⎦⎤
③ 修改操作:
-
- 如果A[1…i−1]
A[1…i−1]修改成B[1…j−1]B[1…j−1]所需操作數為op3op3的話,我将字元A[i]A[i]替換成A[i']=B[j]A[i′]=B[j],就可以op3+1op3+1的操作數完成:⎡⎣⎢⋯⋯A[i−2]B[j−2]A[i−1]B[j−1]A[i′]B[j]⎤⎦⎥
- ⎣⎡⋯⋯A[i−2]B[j−2]A[i−1]B[j−1]A[i′]B[j]⎦⎤
- 但如果此時字元A[i]==B[j]
- A[i]==B[j]的話,則不需要進行修改操作,操作數仍為op3
-
- op3。
綜上所述,我們将字元串A[1…i]
A[1…i]修改成字元串B[1…j]B[1…j]所需操作為min{op1+1, op2+1, op3+1(ai≠bi)}min{op1+1, op2+1, op3+1(ai≠bi)},其中1(ai≠bi)1(ai≠bi)代表當ai≠biai≠bi時取值11,否則取值為0
0。
數學定義
數學上,我們定義兩個字元串A
A和BB間的Levenshtein距離為levA, B(a, b)levA, B(a, b),其中aa、bb分别為字元串AA、BB的長度,而levA, B⎛⎝⎜⎜⎜⎜⎜⎜⎜i, j⎞⎠⎟⎟⎟⎟⎟⎟⎟=⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪ijmin⎧⎩⎨⎪⎪⎪⎪leva, b(i, j−1)+1leva, b(i−1, j)+1leva, b(i−1, j−1)+1(ai≠bi), j=0, i=0, otherwise
levA, B(i, j)=⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧ijmin⎩⎨⎧leva, b(i, j−1)+1leva, b(i−1, j)+1leva, b(i−1, j−1)+1(ai≠bi), j=0, i=0, otherwise
更多請參考 Wikipedia - Levenshtein_distance。
C++代碼
有了狀态轉移方程,我們就可以愉快地DP了,時間複雜度O(MN)
O(MN),空間複雜度O(MN)
O(MN)。
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 using std::min; 5 int lena, lenb; 6 char a[1010], b[1010]; 7 void read() { 8 scanf("%s%s", a, b); 9 lena = strlen(a); 10 lenb = strlen(b); 11 } 12 13 int dp[1010][1010]; 14 void work() { 15 for(int i=1; i<=lena; i++) dp[i][0] = i; 16 for(int j=1; j<=lenb; j++) dp[0][j] = j; 17 for(int i=1; i<=lena; i++) 18 for(int j=1; j<=lenb; j++) 19 if(a[i-1]==b[j-1]) 20 dp[i][j] = dp[i-1][j-1]; 21 else 22 dp[i][j] = min(dp[i-1][j-1], min(dp[i][j-1], dp[i-1][j]))+1; 23 printf("%d\n", dp[lena][lenb]); 24 } 25 26 int main() { 27 read(); 28 work(); 29 return 0; 30 }
幾個小優化
1. 如果滿足A[i]==B[j]
A[i]==B[j](下标從11開始),實際上是可以直接取lev(i, j)=lev(i−1, j−1)
lev(i, j)=lev(i−1, j−1)的。因為此時字元相同是不需要任何編輯操作的。這一優化也可以從上文轉移方程中構造不等關系得出。
2. 如果使用滾動數組,則空間複雜度可以降到O(2∗max{M, N})
O(2∗max{M, N})。但也可以通過儲存lev(i−1, j−1)lev(i−1, j−1)來把空間複雜度降到O(max{M, N})
O(max{M, N}),如下:
以上即為Levenshtein距離算法的基本介紹1 int dp[1010]; 2 void work() { 3 for(int j=1; j<=lenb; j++) dp[j] = j; 4 int t1, t2; 5 for(int i=1; i<=lena; i++) { 6 t1 = dp[0]++; 7 for(int j=1; j<=lenb; j++) { 8 t2 = dp[j]; 9 if(a[i-1]==b[j-1]) 10 dp[j] = t1; 11 else 12 dp[j] = min(t1, min(dp[j-1], dp[j]))+1; 13 t1 = t2; 14 } 15 } 16 printf("%d\n", dp[lenb]); 17 }
-