SimHash 算法 笔记

根据《数学之美》里的介绍,相似哈希(SimHash)是Moses S. Charikar 在2002年提出的 《Similarity estimation techniques from rounding algorithms》但真正得到重视是当Google在网页爬虫中使用它,并把它发表在WWW会议上以后。

simhash是google用来处理海量文本去重的算法。 google出品,你懂的。
simhash最牛逼的一点就是将一个文档,最后转换成一个64位的字节,暂且称之为特征字,
然后判断重复只需要判断他们的特征字的距离是不是<n(根据经验这个n一般取值为3),就可以判断两个文档是否相似。

原理

simhash值的生成图解如下
simhash

大概花三分钟看懂这个图就差不多怎么实现这个simhash算法了。特别简单。谷歌出品嘛,简单实用。

算法过程大概如下:

  1. 将Doc进行关键词抽取(其中包括分词和计算权重),抽取出n个(关键词,权重)对, 即图中的(feature, weight)们。
    记为 feature_weight_pairs = [fw1, fw2 … fwn],其中 fwn = (feature_n, weight_n)。
  2. hash_weight_pairs = [ (hash(feature), weight) for feature, weight in feature_weight_pairs ] 生成图中的(hash,weight)们,
    此时假设hash生成的位数bits_count = 6(如图);
  3. 然后对 hash_weight_pairs 进行位的纵向累加,如果该位是1,则+weight,如果是0,则-weight,最后生成bits_count个数字,
    如图所示是[13, 108, -22, -5, -32, 55], 这里产生的值和hash函数所用的算法相关。
  4. [13,108,-22,-5,-32,55] -> 110001这个就很简单啦,正1负0。

到此,如何从一个doc到一个simhash值的过程已经讲明白了。 但是还有一个重要的部分没讲,simhash值的海明距离计算

二进制串A 和 二进制串B 的海明距离 就是 A xor B 后二进制中1的个数。

举例如下:

1
2
3
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的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 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。由此可见还是蛮高效的。

References

[1] 《数学之美》 吴军 第16章 信息指纹及其应用
[2] 海量数据相似度计算之simhash和海明距离
[3] 《Similarity estimation techniques from rounding algorithms》
[4] CharikarEstim.pdf
[5] Algorithm 使用SimHash进行海量文本去重