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

2013年3月16日 星期六

[ 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 輸出我們的結果. 
  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

方法二: 
如果你的時間格式不常變的話, 其實可以不用如方法一這樣麻煩, 參考代碼如下: 
  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 輸出.

[Git 常見問題] error: The following untracked working tree files would be overwritten by merge

  Source From  Here 方案1: // x -----删除忽略文件已经对 git 来说不识别的文件 // d -----删除未被添加到 git 的路径中的文件 // f -----强制运行 #   git clean -d -fx 方案2: 今天在服务器上  gi...