simHash 简介以及java实现
?
传统的hash算法只负责将原始内容尽量均匀随机地映射为一个签名值，原理上相当于伪随机数产生算法。产生的两个签名，如果相等，说明原始内容在一定概率?下是相等的；如果不相等，除了说明原始内容不相等外，不再提供任何信息，因为即使原始内容只相差一个字节，所产生的签名也很可能差别极大。从这个意义上来?说，要设计一个hash算法，对相似的内容产生的签名也相近，是更为艰难的任务，因为它的签名值除了提供原始内容是否相等的信息外，还能额外提供不相等的?原始内容的差异程度的信息。?
?
而Google的simhash算法产生的签名，可以用来比较原始内容的相似度时，便很想了解这种神奇的算法的原理。出人意料，这个算法并不深奥，其思想是非常清澈美妙的。
?
Simhash算法
?
simhash算法的输入是一个向量，输出是一个f位的签名值。为了陈述方便，假设输入的是一个文档的特征集合，每个特征有一定的权重。比如特征可以是文档中的词，其权重可以是这个词出现的次数。simhash算法如下：
?
1，将一个f维的向量V初始化为0；f位的二进制数S初始化为0；
?
2，对每一个特征：用传统的hash算法对该特征产生一个f位的签名b。对i=1到f：
如果b的第i位为1，则V的第i个元素加上该特征的权重；
否则，V的第i个元素减去该特征的权重。?
?
3，如果V的第i个元素大于0，则S的第i位为1，否则为0；
?
4，输出S作为签名。
?
?
?
算法几何意义和原理
?
这个算法的几何意义非常明了。它首先将每一个特征映射为f维空间的一个向量，这个映射规则具体是怎样并不重要，只要对很多不同的特征来说，它们对所对应的?向量是均匀随机分布的，并且对相同的特征来说对应的向量是唯一的就行。比如一个特征的4位hash签名的二进制表示为1010，那么这个特征对应的?4维向量就是(1,?-1,?1,?-1)T，即hash签名的某一位为1，映射到的向量的对应位就为1，否则为-1。然后，将一个文档中所包含的各个特征对应的向量加权求和，?加权的系数等于该特征的权重。
?
得到的和向量即表征了这个文档，我们可以用向量之间的夹角来衡量对应文档之间的相似度。最后，为了得到一个f位的签名，需要?进一步将其压缩，如果和向量的某一维大于0，则最终签名的对应位为1，否则为0。这样的压缩相当于只留下了和向量所在的象限这个信息，而64位的签名可以?表示多达264个象限，因此只保存所在象限的信息也足够表征一个文档了。
?
?
比较相似度
?
?
海明距离：两个码字的对应比特取值不同的比特数称为这两个码字的海明距离。一个有效编码集中,任意两个码字的海明距离的最小值称为该编码集的海明距离。举例如下：10101和00110从第一位开始依次有第一位、第四、第五位不同，则海明距离为3.
?
异或：只有在两个比较的位不同时其结果是1，否则结果为0?
?
??对每篇文档根据SimHash算出签名后，再计算两个签名的海明距离（两个二进制异或后1的个数）即可。根据经验值，对64位的SimHash，海明距离在3以内的可以认为相似度比较高。
?
?
假设对64位的SimHash，我们要找海明距离在3以内的所有签名。我们可以把64位的二进制签名均分成4块，每块16位。根据鸽巢原理（也成抽屉原理，见组合数学），如果两个签名的海明距离在3以内，它们必有一块完全相同。
?
?
我们把上面分成的4块中的每一个块分别作为前16位来进行查找。建立倒排索引。
?
?
?
?
如果库中有2^34个（大概10亿）签名，那么匹配上每个块的结果最多有2^(34-16)=262144个候选结果(假设数据是均匀分布，16位的数据，产生的像限为2^16个，则平均每个像限分布的文档数则2^34/2^16?=?2^(34-16))，四个块返回的总结果数为?4*?262144（大概100万）。原本需要比较10亿次，经过索引，大概就只需要处理100万次了。由此可见，确实大大减少了计算量。?
?
?
?
Java?代码实现：
?
?
?
package com.gemantic.nlp.commons.simhash;import java.math.BigInteger;import java.util.ArrayList;import java.util.List;import java.util.StringTokenizer;public class SimHash { private String tokens; private BigInteger intSimHash; private String strSimHash; private int hashbits = 64; public SimHash(String tokens) { this.tokens = tokens; this.intSimHash = this.simHash(); } public SimHash(String tokens, int hashbits) { this.tokens = tokens; this.hashbits = hashbits; this.intSimHash = this.simHash(); } public BigInteger simHash() { int[] v = new int[this.hashbits]; StringTokenizer stringTokens = new StringTokenizer(this.tokens); while (stringTokens.hasMoreTokens()) { String temp = stringTokens.nextToken(); BigInteger t = this.hash(temp); for (int i = 0; i < this.hashbits; i++) { BigInteger bitmask = new BigInteger("1").shiftLeft(i); if (t.and(bitmask).signum() != 0) { v[i] += 1; } else { v[i] -= 1; } } } BigInteger fingerprint = new BigInteger("0"); StringBuffer simHashBuffer = new StringBuffer(); for (int i = 0; i < this.hashbits; i++) { if (v[i] >= 0) { fingerprint = fingerprint.add(new BigInteger("1").shiftLeft(i)); simHashBuffer.append("1"); }else{ simHashBuffer.append("0"); } } this.strSimHash = simHashBuffer.toString(); System.out.println(this.strSimHash + " length " + this.strSimHash.length()); return fingerprint; } private BigInteger hash(String source) { if (source == null || source.length() == 0) { return new BigInteger("0"); } else { char[] sourceArray = source.toCharArray(); BigInteger x = BigInteger.valueOf(((long) sourceArray[0]) << 7); BigInteger m = new BigInteger("1000003"); BigInteger mask = new BigInteger("2").pow(this.hashbits).subtract( new BigInteger("1")); for (char item : sourceArray) { BigInteger temp = BigInteger.valueOf((long) item); x = x.multiply(m).xor(temp).and(mask); } x = x.xor(new BigInteger(String.valueOf(source.length()))); if (x.equals(new BigInteger("-1"))) { x = new BigInteger("-2"); } return x; } } /** * 取两个二进制的异或，统计为1的个数，就是海明距离 * @param other * @return */ public int hammingDistance(SimHash other) { BigInteger x = this.intSimHash.xor(other.intSimHash); int tot = 0; //统计x中二进制位数为1的个数 //我们想想，一个二进制数减去1，那么，从最后那个1（包括那个1）后面的数字全都反了，对吧，然后，n&(n-1)就相当于把后面的数字清0， //我们看n能做多少次这样的操作就OK了。 while (x.signum() != 0) { tot += 1; x = x.and(x.subtract(new BigInteger("1"))); } return tot; } /** * calculate Hamming Distance between two strings * 二进制怕有错，当成字符串，作一个，比较下结果 * @author * @param str1 the 1st string * @param str2 the 2nd string * @return Hamming Distance between str1 and str2 */ public int getDistance(String str1, String str2) { int distance; if (str1.length() != str2.length()) { distance = -1; } else { distance = 0; for (int i = 0; i < str1.length(); i++) { if (str1.charAt(i) != str2.charAt(i)) { distance++; } } } return distance; } /** * 如果海明距离取3，则分成四块，并得到每一块的bigInteger值 ，作为索引值使用 * @param simHash * @param distance * @return */ public List<BigInteger> subByDistance(SimHash simHash, int distance){ int numEach = this.hashbits/(distance+1); List<BigInteger> characters = new ArrayList(); StringBuffer buffer = new StringBuffer(); int k = 0; for( int i = 0; i < this.intSimHash.bitLength(); i++){ boolean sr = simHash.intSimHash.testBit(i); if(sr){ buffer.append("1"); } else{ buffer.append("0"); } if( (i+1)%numEach == 0 ){ BigInteger eachValue = new BigInteger(buffer.toString(),2); System.out.println("----" +eachValue ); buffer.delete(0, buffer.length()); characters.add(eachValue); } } return characters; } public static void main(String[] args) { String s = "This is a test string for testing"; SimHash hash1 = new SimHash(s, 64); System.out.println(hash1.intSimHash + " " + hash1.intSimHash.bitLength()); hash1.subByDistance(hash1, 3); System.out.println("\n"); s = "This is a test string for testing, This is a test string for testing abcdef"; SimHash hash2 = new SimHash(s, 64); System.out.println(hash2.intSimHash+ " " + hash2.intSimHash.bitCount()); hash1.subByDistance(hash2, 3); s = "This is a test string for testing als"; SimHash hash3 = new SimHash(s, 64); System.out.println(hash3.intSimHash+ " " + hash3.intSimHash.bitCount()); hash1.subByDistance(hash3, 3); System.out.println("============================"); int dis = hash1.getDistance(hash1.strSimHash,hash2.strSimHash); System.out.println(hash1.hammingDistance(hash2) + " "+ dis); int dis2 = hash1.getDistance(hash1.strSimHash,hash3.strSimHash); System.out.println(hash1.hammingDistance(hash3) + " " + dis2); }}??
?
?
?
?
?
?
参考：?http://blog.sina.com.cn/s/blog_72995dcc010145ti.html
http://blog.sina.com.cn/s/blog_56d8ea900100y41b.html
http://blog.csdn.net/meijia_tts/article/details/7928579
?
?
?
?
?
?