程式扎記: [ Java 代碼範本 ] Levenshtein distance

標籤

2013年3月21日 星期四

[ Java 代碼範本 ] Levenshtein distance


Preface :
通常在計算字串的相似程度, 常見的是 Hamming distance, 但是它在使用上要求兩個字串必須相同長度. 在這邊要介紹另一個好用的演算法 Levenshtein distance, 它的好處是兩個字串可以是不同長度. 底下將使用 Java 來實作並改善運行效率.

Pseudo code:
首先來看看這個演算法的 Pseudo code:
  1. int LevenshteinDistance(string s, string t)  
  2. {  
  3.   int len_s = length(s), len_t = length(t)  
  4.   
  5.   if(len_s == 0) then return len_t  
  6.   if(len_t == 0) then return len_s  
  7.   if(s[len_s-1] == t[len_t-1]) then cost = 0  
  8.   else                              cost = 1  
  9.   return minimum(LevenshteinDistance(s[0..len_s-1], t) + 1, ㄥ// case 1  
  10.                  LevenshteinDistance(s, t[0..len_t-1]) + 1// case 2  
  11.                  LevenshteinDistance(s[0..len_s-1], t[0..len_t-1]) + cost) // case3  
  12. }  
其過程很簡單, 就是每次的遞迴呼叫都考慮:
Case1. 減少字串 s 一個字元, 並增加 cost 後遞迴呼叫 LevenshteinDistance
Case2. 減少字串 t 一個字元, 並增加 cost 後遞迴呼叫 LevenshteinDistance
Case3. 假設當前 s 字串的字元與 t 字串的字元不同, 設定 cost=1, 並同時減少 t 與 s 字串一個長度後遞迴呼叫 LevenshteinDistance

一直到某一方的長度為 0 便結束遞迴的執行. 過程以字串 "apple" 與 "apt" 示範如下 (灰色部分代表被每次遞迴被拿掉的部分):


而最終的結果 "apple" 與 "apt" 的 Levenshtein Distance 為 3!

Code Implementation 1:
最直覺的實作便是按照 pseudo code 撰寫, 完成代碼如下:
  1. public static int Levenshtein(String str1, String str2)  
  2. {  
  3.     int str1_len = str1.length();  
  4.     int str2_len = str2.length();  
  5.     if(str1_len==0return str2.length();  
  6.     if(str2_len==0return str1.length();  
  7.     int cost = 0;  
  8.     if(str1.charAt(0) != str2.charAt(0)) cost=1;  
  9.     return Math.min(Math.min(Levenshtein(str1.substring(1, str1_len), str2)+1,  
  10.                              Levenshtein(str1, str2.substring(1, str2_len))+1),  
  11.                     Levenshtein(str1.substring(1, str1.length()), str2.substring(1, str2_len)))+cost;  
  12. }  
這樣的作法事實上效率並不好, 因為在遞迴展開的過程中, 很多的分支是可以 prone 掉而不必繼續遞迴下去, 例如當 str1 與 str2 相同時便可以返回 cost=0 的結果回去.

Code Implementation 2: 
另一種做法是當發現遞迴中的參數 str1 與 str2 相等便直接返回 0, 而不繼續遞迴下去. 這樣的好處是當一開始的 str1 與 str2 有許多連續相同的字元時可以省掉許多遞迴的時間, 但是卻增加了字串比對的 cost. 實作代碼如下:
  1. public static int Levenshtein2(String str1, String str2)  
  2. {  
  3.     int str1_len = str1.length();  
  4.     int str2_len = str2.length();  
  5.     if(str1_len==0return str2.length();  
  6.     if(str2_len==0return str1.length();  
  7.     if(str1.equals(str2)) return 0// 如果字串相等, 無須遞迴下去!  
  8.     int cost = 0;  
  9.     if(str1.charAt(0) != str2.charAt(0)) cost=1;  
  10.     return Math.min(Math.min(Levenshtein2(str1.substring(1, str1_len), str2)+1,  
  11.                              Levenshtein2(str1, str2.substring(1, str2_len))+1),  
  12.                     Levenshtein2(str1.substring(1, str1.length()), str2.substring(1, str2_len)))+cost;  
  13. }   
這種做法在 str1 與 str2 有很多不一樣的地方時, 在字串比對的 cost 會降低執行的效率.

Code Implementation 3:
最後一種做法是當每次遞迴的一開始, 就 trim 掉 str1 與 str2 在 front 與 back 相同的子字串, 這樣的好處也是可以 prone 掉不需要的遞迴分支. 實作如下:
  1. public static int Levenshtein3(String str1, String str2)  
  2. {         
  3.     // 1) Trim front same sub string  
  4.     int diff = -1;  
  5.     for(int i=0; i
  6.     {  
  7.         if(str1.charAt(i)!=str2.charAt(i))  
  8.         {  
  9.             diff=i;  
  10.             break;  
  11.         }  
  12.     }  
  13.     if(diff>0)  
  14.     {  
  15.         str1 = str1.substring(diff, str1.length());  
  16.         str2 = str2.substring(diff, str2.length());  
  17.     }  
  18.     // 2) Trim back same sub string  
  19.     for(int i=0; i
  20.     {  
  21.         if(str1.charAt(str1.length()-i-1)!=str2.charAt(str2.length()-i-1))  
  22.         {  
  23.             diff=i;  
  24.             break;  
  25.         }  
  26.     }  
  27.     if(diff>0)  
  28.     {  
  29.         str1 = str1.substring(0, str1.length()-diff);  
  30.         str2 = str2.substring(0, str2.length()-diff);  
  31.     }  
  32.       
  33.     int str1_len = str1.length();  
  34.     int str2_len = str2.length();  
  35.     if(str1_len==0return str2.length();  
  36.     if(str2_len==0return str1.length();  
  37.       
  38.     return Math.min(Math.min(Levenshtein3(str1.substring(1, str1_len), str2)+1,  
  39.                Levenshtein3(str1, str2.substring(1, str2_len))+1),  
  40.                Levenshtein3(str1.substring(1, str1.length()), str2.substring(1, str2_len)))+1;        
  41. }  
Experiment :
接著我們來跑些實驗, 看看這三種實作的表現如何. 測試代碼如下:
  1. String str1 = "appgregatent";  
  2. String str2 = "apparentint";  
  3. long st = System.currentTimeMillis();  
  4. System.out.printf("Levenshtein distance1=%d (%d ms)\n", Levenshtein1(str1, str2), System.currentTimeMillis()-st);  
  5. st = System.currentTimeMillis();  
  6. System.out.printf("Levenshtein distance2=%d (%d ms)\n", Levenshtein2(str1, str2), System.currentTimeMillis()-st);  
  7. st = System.currentTimeMillis();  
  8. System.out.printf("Levenshtein distance3=%d (%d ms)\n", Levenshtein3(str1, str2), System.currentTimeMillis()-st);  
執行結果如下:
Levenshtein distance1=5 (1519 ms)
Levenshtein distance2=5 (787 ms)
Levenshtein distance3=5 (3 ms)
可以發現第三種方法完勝! 接著設定 String str1 = "abcdefgh" 與 String str2 = "hgfedcba", 也就是兩個字串完全沒有 sub string 相同:
Levenshtein distance1=8 (84 ms)
Levenshtein distance2=8 (88 ms)
Levenshtein distance3=8 (161 ms)
這時候可以發現第一種的方法較好, 因為後面兩種方法沒有機會進行遞迴的 prone , 但多了 cost 去做字串比對與 trim 的動作, 故花費較多時間. 結論就是根據 str1 與 str2 的相似程度選擇適當的方法便是王道! (沒比前, 天曉得 str1 與 str2 相似程度 ><")

Supplement:
Algorithm Implementation/Strings/Levenshtein distance
This message was edited 21 times. Last update was at 22/03/2

1 則留言:

  1. 請問程式碼 Levenshtein3 第5行與19行 式缺了什麼? 謝謝

    回覆刪除

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!