simhash值的海明距离计算
二进制串A 和 二进制串B 的海明距离 就是
A xor B
后二进制中1的个数。
举例如下：
A = 100111;
B = 101010;
hamming_distance(A, B) = count_1(A xor B) = count_1(001101) = 3;
当我们算出所有doc的simhash值之后，需要计算doc A和doc B之间是否相似的条件是：
A和B的海明距离是否小于等于n，这个n值根据经验一般取值为3
,
simhash本质上是
局部敏感性的hash
，和md5之类的不一样。 正因为它的局部敏感性，所以我们可以使用海明距离来衡量simhash值的相似度。
高效计算二进制序列中1的个数
/* src/Simhasher.hpp */
bool isEqual(uint64_t lhs, uint64_t rhs, unsigned short n = 3)
{
unsigned short cnt = 0;
lhs ^= rhs;
while(lhs && cnt <= n)
{
lhs &= lhs - 1;
cnt++;
}
if(cnt <= n)
{
return true;
}
return false;
}
由上式这个函数来计算的话，时间复杂度是 O(n); 这里的n默认取值为3。由此可见还是蛮高效的。
对比其他算法
百度的去重算法
百度的去重算法最简单，就是直接找出此文章的最长的n句话，做一遍hash签名。n一般取3。 工程实现巨简单，据说准确率和召回率都能到达80%以上。
shingle算法
shingle原理略复杂，不细说。 shingle算法我认为过于学院派，对于工程实现不够友好，速度太慢，基本上无法处理海量数据。
参考
-
Similarity estimation techniques from rounding algorithms
-
simhash与Google的网页去重
-
海量数据相似度计算之simhash和海明距离
Python的代码实现如下：
|
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
|
#!/usr/bin/python # coding=utf-8 class simhash:
s = s = |
Java的代码如下如下：
|
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 |
|
import java.math.BigInteger; import java.util.StringTokenizer; public class SimHash { private String tokens; private BigInteger strSimHash; private int hashbits = 128 ; public SimHash( String tokens) { this .tokens = tokens; this .strSimHash = this .simHash(); } public SimHash( String tokens, int hashbits) { this .tokens = tokens; this .hashbits = hashbits; this .strSimHash = 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” ); for ( int i = 0 ; i < this .hashbits; i++) { if (v[i] >= 0 ) { fingerprint = fingerprint.add( new BigInteger( “1” ).shiftLeft(i)); } } 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; } } public int hammingDistance(SimHash other) { BigInteger m = new BigInteger( “1” ).shiftLeft( this .hashbits).subtract( new BigInteger( “1” )); BigInteger x = this .strSimHash.xor(other.strSimHash).and(m); int tot = 0 ; while (x.signum() != 0 ) { tot += 1 ; x = x.and(x.subtract( new BigInteger( “1” ))); } return tot; } public static void main( String [] args) { String s = “This is a test string for testing” ; SimHash hash1 = new SimHash(s, 128 ); System.out.println(hash1.strSimHash + ” ” + hash1.strSimHash.bitLength()); s = “This is a test string for testing also” ; SimHash hash2 = new SimHash(s, 128 ); System.out.println(hash2.strSimHash + ” ” + hash2.strSimHash.bitCount()); s = “This is a test string for testing als” ; SimHash hash3 = new SimHash(s, 128 ); System.out.println(hash3.strSimHash + ” ” + hash3.strSimHash.bitCount()); System.out.println( “============================” ); System.out.println(hash1.hammingDistance(hash2)); System.out.println(hash1.hammingDistance(hash3)); } } |
python的计算能力确实很强，float可以表示任意长度的数字，而对应java、c++只能用其他办法来实现了，比如java的BigIneteger,对应的位操作也只能利用类方法。。。汗。。。
另外说明，位运算只适合整数哦。。。因为浮点的存储方案决定不能位运算，如果非要位运算，就需要Float.floatToIntBits，运算完，再通过Float.intBitsToFloat转化回去。(java默认的float,double的hashcode其实就是对应的floatToIntBits的int值)