[ 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) 則是用來計算 "編輯距離". 完整代碼如下: 

view plaincopy to clipboardprint?

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)>=0) return str1.length()-str2.length();  
39.             else  
40.             {  
41.                 return LevenshteinDistance(str1, str2);  
42.             }  
43.         }  
44.         else  
45.         {  
46.             if(str2.indexOf(str1)==0) return 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()==0) return t.length();  
57.         else if(t.length()==0) return 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: 
接著你可以使用下面範例代碼計算 "漢明距離", "漢明重量": 

view plaincopy to clipboardprint?

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