## 2012年11月8日 星期四

### [ Java 代碼範本 ] Hamming distance

Preface:

- 1011101 與 1001001 之間的漢明距離是 2。
- 2143896 與 2233796 之間的漢明距離是 3。
- "toned" 與 "roses" 之間的漢明距離是 3。

Implementation:

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

### [ Python 文章收集 ] Monitoring memory usage of a running Python program

Source From  Here Preface At  Survata , we do a lot of data processing using Python and its suite of data processing libraries like  pandas ...