雁過無痕

《編程之美》讀書筆記11： 3.3 計算字符串的相似度

很經典的可使用動態規劃方法解決的題目，和計算兩字符串的最長公共子序列相似。

設A_i為字符串A(a₁a₂a₃ … a_m)的前i個字符（即為a₁,a₂,a₃ … a_i）

設B_j為字符串B(b₁b₂b₃ … b_n)的前j個字符（即為b₁,b₂,b₃ … b_j）

設 L(i , j)為使兩個字符串和A_i和B_j相等的最小操作次數。

當a_i等于b_j時 顯然L(i, j)=L(i-1, j-1)

當a_i不等于b_j時

  若將它們修改為相等，則對兩個字符串至少還要操作L(i-1, j-1)次

  若刪除a_i或在B_j后添加a_i，則對兩個字符串至少還要操作L(i-1, j)次

  若刪除b_j或在A_i后添加b_j，則對兩個字符串至少還要操作L(i, j-1)次

  此時L(i, j)=min( L(i-1, j-1), L(i-1, j), L(i, j-1) )  + 1

顯然，L(i, 0)=i，L(0, j)=j, 再利用上述的遞推公式，可以直接計算出L(i, j)值。

為了保持與書中代碼一致，下面的函數參數類型是string,而不是char*。

distance_1
 1int string_distance(const string& sa, const string& sb)
 2{
 3  const int sz_a=sa.size()+1;
 4  const int sz_b=sb.size()+1;
 5  int i,j,k,tmp;
 6  vector< vector<int> > arr(sz_a, vector<int>(sz_b) );
 7  for (i=0; i<sz_a; ++i) arr[i][0]=i;
 8  for (j=0; j<sz_b; ++j) arr[0][j]=j;
 9
10  for (i=1; i<sz_a; ++i){
11    for (j=1; j<sz_b; ++j){
12      if( sa[i-1] == sb[j-1]) arr[i][j]=arr[i-1][j-1];
13      else{
14        tmp= arr[i-1][j] > arr[i][j-1] ? arr[i][j-1] : arr[i-1][j];
15        if (tmp>arr[i-1][j-1]) tmp=arr[i-1][j-1];
16        arr[i][j]=tmp+1;
17      }
18    }
19  }
20  return arr[sz_a-1][sz_b-1];
21}
22
23

由于只要求計算兩字串的距離，計算時，只用到兩列數據，因而可以對代碼進一步優化，節省空間。

distance_2
 1int string_distance2(const string& sa, const string& sb)
 2{
 3  const int sz_a=sa.size()+1;
 4  const int sz_b=sb.size()+1;
 5  int sz_max=sz_a;
 6  int sz_min=sz_b;
 7  const char *longer=sa.data();
 8  const char *shorter=sb.data();
 9  if (sz_a < sz_b){
10    sz_max=sz_b;
11    sz_min=sz_a;
12    longer=sb.data();
13    shorter=sa.data();
14  }
15  int i,j,k,tmp;
16  vector<int>  arr(sz_min+1);
17  for (j=0; j<sz_min; ++j) arr[j+1]=j;
18
19  for (i=1; i<sz_max; ++i){
20    arr[0]=i;
21    for (j=1; j<sz_min; ++j){
22      if( longer[i-1] != shorter[j-1]) {
23        tmp= arr[j+1] > arr[j] ? arr[j] : arr[j+1];
24        if (tmp>arr[j-1]) tmp=arr[j-1];
25        arr[j]=tmp+1;  //tmp= min(arr[j-1],arr[j],arr[j+1])
26      }
27    }
28    for(j=sz_min-1; j>=0; --j) arr[j+1]=arr[j];
29  }
30  return arr[sz_min];
31}
32
33

 

上面的代碼還可進一步優化，比如通過指針而不是數組名來訪問內存。如果內存足夠大，可以多申請空間，每次循環，通過修改保存的數據起始位置，避免內存復制。

 

補充：字符串的相似度，就是求編輯距離（edit distance）。