simHash是否适合短文本的相似文本匹配

发表于 由

附注：用BigInteger类型来存储64位的hash码
http://doc.java.sun.com/DocWeb/api/all/java.math.BigInteger
很好用，xor()异或、BigInteger.bitLength()取位长、.bitCount()取位为1的个数。
simHash算法流程：
1): 计算simHash码
a). 字符串String分词得到tokens；
       b). 计算每个tokens的64位Hash码；
       c). 按Hash码的位进行标记，1则标记为1、否则标记为-1；
       d). 把每个tokens的Hash码按位进行统计求和；
       e). 进行签名，大于0则为1，否则为0，得到64位simHash指纹。
2): 把64位simHash码均分为汉明距离n+1块，方便后续查找的所有近邻simHash码；
3): 计算两个simHash码的汉明距离，
       方法一：给出simHash的64位二进制码字符串：str1.charAt(i) != str2.charAt(i)；
       方法二：给出simHash的int值：先做异或，然后统计异或后二进制位数为1的个数
问题！？：simHash在短文本的可行性！
测试相似文本的相似度与汉明距离
测试文本：20个城市名作为词串：北京,上海,香港,深圳,广州,台北,南京,大连,苏州,青岛,无锡,佛山,重庆,宁波,杭州,成都,武汉,澳门,天津,沈阳
相似度矩阵：
simHash码：
勘误：0.667, Hm:13 是对比的msg 1与2。
可见：相似度在0.8左右的Hamming距离为7，只有相似度高到0.9412，Hamming距离才近到4，此时，反观Google对此算法的应用场景：网页近重复。
镜像网站、内容复制、嵌入广告、计数改变、少量修改。
以上原因对于长文本来说造成的相似度都会比较高，而对于短文本来说，如何处理海量数据的相似度文本更为合适的？？
附：simHash生成代码 参考：Simhash java实现

  1. import java.math.BigInteger;   
  2. import java.util.ArrayList;   
  3. import java.util.List;   
  4. import java.util.StringTokenizer;   
  5.   
  6. public class SimHash {   
  7.     private String tokens;   
  8.     private BigInteger intSimHash;   
  9.     private String strSimHash;   
  10.     private int hashbits = 64;   
  11.     public SimHash(String tokens) {   
  12.         this.tokens = tokens;   
  13.         this.intSimHash = this.simHash();   
  14.     }   
  15.   
  16.     public SimHash(String tokens, int hashbits) {   
  17.         this.tokens = tokens;   
  18.         this.hashbits = hashbits;   
  19.         this.intSimHash = this.simHash();   
  20.     }   
  21.     public BigInteger simHash() {   
  22.         int[] v = new int[this.hashbits];   
  23.         StringTokenizer stringTokens = new StringTokenizer(this.tokens);   
  24.         while (stringTokens.hasMoreTokens()) {   
  25.             String temp = stringTokens.nextToken();   
  26.             BigInteger t = this.hash(temp);   
  27.             for (int i = 0; i < this.hashbits; i++) {   
  28.                 BigInteger bitmask = new BigInteger(“1″).shiftLeft(i);   
  29.                  if (t.and(bitmask).signum() != 0) {   
  30.                     v[i] += 1;   
  31.                 } else {   
  32.                     v[i] -= 1;   
  33.                 }   
  34.             }   
  35.         }   
  36.         BigInteger fingerprint = new BigInteger(“0″);   
  37.         StringBuffer simHashBuffer = new StringBuffer();   
  38.         for (int i = 0; i < this.hashbits; i++) {   
  39.             if (v[i] >= 0) {   
  40.                 fingerprint = fingerprint.add(new BigInteger(“1″).shiftLeft(i));   
  41.                 simHashBuffer.append(“1″);   
  42.             }else{   
  43.                 simHashBuffer.append(“0″);   
  44.             }   
  45.         }   
  46.         this.strSimHash = simHashBuffer.toString();   
  47.         System.out.println(this.strSimHash + “ length ” + this.strSimHash.length());   
  48.         return fingerprint;   
  49.     }   
  50.     private BigInteger hash(String source) {   
  51.         if (source == null || source.length() == 0) {   
  52.             return new BigInteger(“0″);   
  53.         } else {   
  54.             char[] sourceArray = source.toCharArray();   
  55.             BigInteger x = BigInteger.valueOf(((long) sourceArray[0]) << 7);   
  56.             BigInteger m = new BigInteger(“1000003″);   
  57.             BigInteger mask = new BigInteger(“2″).pow(this.hashbits).subtract(   
  58.                     new BigInteger(“1″));   
  59.             for (char item : sourceArray) {   
  60.                 BigInteger temp = BigInteger.valueOf((long) item);   
  61.                 x = x.multiply(m).xor(temp).and(mask);   
  62.             }   
  63.             x = x.xor(new BigInteger(String.valueOf(source.length())));   
  64.             if (x.equals(new BigInteger(“-1″))) {   
  65.                 x = new BigInteger(“-2″);   
  66.             }   
  67.             return x;   
  68.         }   
  69.     }   
  70.     public int hammingDistance(SimHash other) {         
  71.         BigInteger x = this.intSimHash.xor(other.intSimHash);   
  72.         int tot = 0;        
  73.         //统计x中二进制位数为1的个数   
  74.         //我们想想，一个二进制数减去1，那么，从最后那个1（包括那个1）后面的数字全都反了，对吧，然后，n&(n-1)就相当于把后面的数字清0，   
  75.         //我们看n能做多少次这样的操作就OK了。         
  76.          while (x.signum() != 0) {   
  77.             tot += 1;   
  78.             x = x.and(x.subtract(new BigInteger(“1″)));   
  79.         }   
  80.         return tot;   
  81.     }       
  82.     public int getDistance(String str1, String str2) {    
  83.         int distance;    
  84.         if (str1.length() != str2.length()) {    
  85.             distance = -1;    
  86.         } else {    
  87.             distance = 0;    
  88.             for (int i = 0; i < str1.length(); i++) {    
  89.                 if (str1.charAt(i) != str2.charAt(i)) {    
  90.                     distance++;    
  91.                 }    
  92.             }    
  93.         }    
  94.         return distance;    
  95.     }     
  96.     public List subByDistance(SimHash simHash, int distance){   
  97.         int numEach = this.hashbits/(distance+1);   
  98.         List characters = new ArrayList();          
  99.         StringBuffer buffer = new StringBuffer();   
  100.         int k = 0;   
  101.         for( int i = 0; i < this.intSimHash.bitLength(); i++){   
  102.             boolean sr = simHash.intSimHash.testBit(i);   
  103.               
  104.             if(sr){   
  105.                 buffer.append(“1″);   
  106.             }      
  107.             else{   
  108.                 buffer.append(“0″);   
  109.             }   
  110.               
  111.             if( (i+1)%numEach == 0 ){   
  112.                 BigInteger eachValue = new BigInteger(buffer.toString(),2);   
  113.                 System.out.println(“—-” +eachValue );   
  114.                 buffer.delete(0, buffer.length());   
  115.                 characters.add(eachValue);   
  116.             }   
  117.         }   
  118.         return characters;   
  119.     }    
  120.     public static void main(String[] args) {   
  121.         String s = “This is a test string for testing”;   
  122.         SimHash hash1 = new SimHash(s, 64);   
  123.         System.out.println(hash1.intSimHash + “  ” + hash1.intSimHash.bitLength());         
  124.         hash1.subByDistance(hash1, 3);   
  125.         System.out.println(“\n”);   
  126.         s = “This is a test string for testing, This is a test string for testing abcdef”;   
  127.         SimHash hash2 = new SimHash(s, 64);   
  128.         System.out.println(hash2.intSimHash+ “  ” + hash2.intSimHash.bitCount());   
  129.         hash1.subByDistance(hash2, 3);   
  130.         s = “This is a test string for testing als”;   
  131.         SimHash hash3 = new SimHash(s, 64);   
  132.         System.out.println(hash3.intSimHash+ “  ” + hash3.intSimHash.bitCount());   
  133.         hash1.subByDistance(hash3, 3);   
  134.         System.out.println(“============================”);   
  135.         int dis = hash1.getDistance(hash1.strSimHash,hash2.strSimHash);         
  136.         System.out.println(hash1.hammingDistance(hash2) + “ ”+ dis);        
  137.         int dis2 = hash1.getDistance(hash1.strSimHash,hash3.strSimHash);   
  138.         System.out.println(hash1.hammingDistance(hash3) + “ ” + dis2);   
  139.     }   
  140. }  

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性： <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>