[ 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

[ Python 常見問題 ] formatting python timedelta objects

來源自 這裡 
問題: 
在 Python 中有一個用來處理時間的 library: datetime - basic date and time object. 透過他你可以很方便的表示與處理時間, 舉例來說當你需要計算時間差時 (某個 task 花的時間), 你可以在開始某個工作開始執行前先執行 datetime.now() 獲得代表當前時間的 datetime 物件, 接著在執行完工作後再次執行 datetime.now() 並減掉之前獲得的 datetime 物件 (會得到 timedelta 物件.), 便可以得到執行前到執行後間的時間差: 

>>> import time
>>> from datetime import datetime
>>> before = datetime.now() # 紀錄執行工作前時間
... (執行工作)
>>> tdelta = datetime.now() - before # 計算執行前後的時間差
>>> tdelta
datetime.timedelta(0, 41, 732000) # 執行時間為 41.732 秒

現在問題來了, "(0, 41, 732000)" 的表示方法不容易懂, 因此你可以希望將之表示為 "xx 分 xx 秒" , 下面介紹幾個方法來處理 timedelta 物件的 format. 

方法一: 
我們可以參考 "strftime() and strptime() Behavior", 取出 timedelta 物件的資料然後丟入一個 HashMap, 在使用 string 的 printf 方式印出客製後格式的字串. 首先我們來撰寫代碼如下, 設計一個函數 strfdelta(tdelta, fmt) 並將 timedelta 物件 tdelta 根據格式字串 fmt 輸出我們的結果. 

view plaincopy to clipboardprint?

1. from string import Template  
2.   
3. class DeltaTemplate(Template):  
4.     delimiter = "%"  
5.   
6. def strfdelta(tdelta, fmt):  
7.     d = {"D": tdelta.days}  
8.     d["H"], rem = divmod(tdelta.seconds, 3600)  
9.     d["M"], d["S"] = divmod(rem, 60)  
10.     t = DeltaTemplate(fmt)  
11.     return t.substitute(**d)  

接著可以如下使用剛剛我們設計的函數 strfdelta(): 

>>> print strfdelta(delta_obj, "%D days %H:%M:%S")
1 days 20:18:12
>>> print strfdelta(delta_obj, "%H hours and %M to go")
20 hours and 18 to go

方法二: 
如果你的時間格式不常變的話, 其實可以不用如方法一這樣麻煩, 參考代碼如下: 

view plaincopy to clipboardprint?

1. import datetime as dt  
2.   
3. turnaround = dt.timedelta(days = 1, hours = 3, minutes = 42, seconds = 54)  
4.   
5. total_seconds = int(turnaround.total_seconds())  
6. hours, remainder = divmod(total_seconds,60*60)  
7. minutes, seconds = divmod(remainder,60)  
8.   
9. print('{} hrs {} mins {} secs'.format(hours,minutes,seconds))  

上面透過 timedelta 物件中的方法 total_seconds() 取出總秒數, 接著一一處理傳換成 hr, min 與 sec 並使用 print format 輸出.