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

標籤

2012年11月8日 星期四

[ Java 代碼範本 ] Hamming distance

Preface: 
資訊理論中,兩個等長字元串之間的 漢明距離 是兩個字元串對應位置的不同字元的個數。換句話說,它就是將一個字元串變換成另外一個字元串所需要替換的字元個數. 例如: 
- 1011101 與 1001001 之間的漢明距離是 2。
- 2143896 與 2233796 之間的漢明距離是 3。
- "toned" 與 "roses" 之間的漢明距離是 3。

漢明重量 是字元串相對於同樣長度的零字元串的漢明距離,也就是說,它是字元串中非零的元素個數:對於二進制字元串來說,就是 1 的個數,所以 11101 的漢明重量是 4. 

當你的比較的兩個字串是不同長度時, 漢明距離 便無法使用, 這時你可以考慮另一種方法叫 "編輯距離". 底下的範例代碼提供你計算 "漢明距離", 當兩個字串長度不同時, 就會替換成 "編輯距離". 

Implementation: 
這邊使用類別 HammingUtil 上的靜態方法 getDistance(String str1, String str2) 來計算 "漢明距離"; 靜態方法 getWeight(int i) 用來計算 "漢明重量"; 而靜態方法 LevenshteinDistance(String s, String t) 則是用來計算 "編輯距離". 完整代碼如下: 
  1. package flib.util.coding;  
  2.   
  3. /** 
  4. * BD: Hamming Toolkit 
  5. * Reference: 
  6. *      - Hamming distance 
  7. *        http://en.wikipedia.org/wiki/Hamming_distance 
  8. *      - Levenshtein distance 
  9. *        http://en.wikipedia.org/wiki/Levenshtein_distance 
  10. *      - Java實例9 - 漢明距離Hamming Distance 
  11. *        http://blog.csdn.net/kindterry/article/details/6581344 
  12. *    
  13. * @author John 
  14. * 
  15. */  
  16. public class HammingUtil {  
  17.     /** 
  18.      * BD: Calculate Hamming Distance between str1 and str2. 
  19.      * @param str1: Input string1 
  20.      * @param str2: Input string2 
  21.      * @return Hamming distance 
  22.      */  
  23.     public static int getDistance(String str1, String str2)  
  24.     {  
  25.           
  26.         if(str1.length()==str2.length())  
  27.         {  
  28.             int distance=0;  
  29.             for  ( int  i =  0 ; i < str1.length(); i++) {    
  30.                 if  (str1.charAt(i) != str2.charAt(i)) {    
  31.                     distance++;    
  32.                 }    
  33.             }   
  34.             return distance;  
  35.         }  
  36.         else if(str1.length()>str2.length())  
  37.         {  
  38.             if(str1.indexOf(str2)>=0return str1.length()-str2.length();  
  39.             else  
  40.             {  
  41.                 return LevenshteinDistance(str1, str2);  
  42.             }  
  43.         }  
  44.         else  
  45.         {  
  46.             if(str2.indexOf(str1)==0return str2.length()-str1.length();  
  47.             else  
  48.             {  
  49.                 return LevenshteinDistance(str1, str2);  
  50.             }  
  51.         }  
  52.     }  
  53.       
  54.     public static int LevenshteinDistance(String s, String t)  
  55.     {  
  56.         if(s.length()==0return t.length();  
  57.         else if(t.length()==0return s.length();  
  58.           
  59.         int cost = 0;  
  60.         if(s.charAt(0) != t.charAt(0)) cost = 1;          
  61.         return Math.min(LevenshteinDistance(s.substring(1), t)+1,   
  62.                         Math.min(LevenshteinDistance(s, t.substring(1))+1,   
  63.                                 LevenshteinDistance(s.substring(1), t.substring(1))+cost));  
  64.         //return LevenshteinDistance(s.substring(1), t.substring(1))+cost;  
  65.     }  
  66.       
  67.     public static int getWeight(int i)  
  68.     {  
  69.         int  n;    
  70.         for  (n =  0 ; i >  0 ; n++) {    
  71.             i &= (i -  1 );    
  72.         }    
  73.         return  n;  
  74.     }  
  75.       
  76.     public  static  void  main(String[] args) {    
  77.         String str1 =  "www.facebook.com" ;    
  78.         String str2 =  "www.faecbok.com" ;     
  79.         int  distance = HammingUtil.getDistance(str1, str2);    
  80.         System.out.println( "distance is "  + distance);    
  81.         int  weight = HammingUtil.getWeight( 255 );    
  82.         System.out.println( "weight is "  + weight);    
  83.     }  
  84. }  
Sample Code: 
接著你可以使用下面範例代碼計算 "漢明距離", "漢明重量": 
  1. public  static  void  main(String[] args) {           
  2.        String str1 =  "facebook" ;    
  3.        String str2 =  "facboak" ;     
  4.        String str3 =  "toned";  
  5.        String str4 =  "roses";  
  6.          
  7.        int  distance1 = HammingUtil.getDistance(str1, str2);    
  8.        int  distance2 = HammingUtil.getDistance(str3, str4);  
  9.        System.out.printf("\t[Info] Hamming distance between '%s' and '%s' is %d...\n",str1, str2, distance1);  
  10.        System.out.printf("\t[Info] Hamming distance between '%s' and '%s' is %d...\n",str3, str4, distance2);  
  11.        int strInBinary = 255;  
  12.        int  weight = HammingUtil.getWeight( strInBinary );    
  13.        System.out.printf("\t[Info] Hamming weight of '%s' is %d...\n", Integer.toBinaryString(strInBinary), weight);    
  14.    }  
執行結果如下: 
[Info] Hamming distance between 'facebook' and 'facboak' is 2...
[Info] Hamming distance between 'toned' and 'roses' is 3...
[Info] Hamming weight of '11111111' is 8...

Supplement: 
Java example of Hamming distance 
Java實例9 - 漢明距離Hamming Distance

沒有留言:

張貼留言

網誌存檔

關於我自己

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