字元串編輯距離（Levenshtein距離）算法

轉載：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]需要操作數為op1op​1​​，那麼我插入一個字元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+1op​1​​+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]需要操作數為op2op​2​​，那麼我删掉字元A[i]A[i]也可以op2+1op​2​​+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]所需操作數為op3op​3​​的話，我将字元A[i]A[i]替換成A[i']=B[j]A[i​′​​]=B[j]，就可以op3+1op​3​​+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
  • • op​3​​。

  　　綜上所述，我們将字元串A[1…i]

  A[1…i]修改成字元串B[1…j]B[1…j]所需操作為min{op1+1, op2+1, op3+1(ai≠bi)}min{op​1​​+1, op​2​​+1, op​3​​+1​(a​i​​≠b​i​​)​​}，其中1(ai≠bi)1​(a​i​​≠b​i​​)​​代表當ai≠bia​i​​≠b​i​​時取值11，否則取值為0

  0。

  數學定義

  　　數學上，我們定義兩個字元串A

  A和BB間的Levenshtein距離為levA, B(a, b)lev​A, 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

  lev​A, B​​(i, j)=​⎩​⎪​⎪​⎪​⎪​⎨​⎪​⎪​⎪​⎪​⎧​​​​​​​​​i​j​min​⎩​⎨​⎧​​​lev​a, b​​(i, j−1)+1​lev​a, b​​(i−1, j)+1​lev​a, b​​(i−1, j−1)+1​(a​i​​≠b​i​​)​​​​​​​​​​​​, 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})，如下：

  

  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 }      

  

  以上即為Levenshtein距離算法的基本介紹