[ Java 代碼範本 ] Levenshtein distance

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

Pseudo code:
首先來看看這個演算法的 Pseudo code:

view plaincopy to clipboardprint?

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 撰寫, 完成代碼如下:

view plaincopy to clipboardprint?

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==0) return str2.length();  
6.     if(str2_len==0) return 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. 實作代碼如下:

view plaincopy to clipboardprint?

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==0) return str2.length();  
6.     if(str2_len==0) return 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 掉不需要的遞迴分支. 實作如下:

view plaincopy to clipboardprint?

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==0) return str2.length();  
36.     if(str2_len==0) return 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 :
接著我們來跑些實驗, 看看這三種實作的表現如何. 測試代碼如下:

view plaincopy to clipboardprint?

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