Simhash 小记

Simhash 最早是Google 用来对海量的数据文本进行去重的算法,算法的原理很简单,但很实用。

1、simhash的第一步是对每个要去重的文本集合进行Finger Print 计算,计算方法如下图:

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 infeature_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。

simhash和普通hash最大的不同在于传统的hash函数虽然也可以用于映射来比较文本的重复,但是对于可能差距只有一个字节的文档也会映射成两个完全不同的哈希结果,而simhash对相似的文本的哈希映射结果也相似。Google的论文中取了f=64,即将整个网页的加权特征集合映射到一个64-bit的fingerprint上。

2、

『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。由此可见还是蛮高效的。

simhash 实现的工程项目

主要是针对中文文档,也就是此项目进行simhash之前同时还进行了分词和关键词的抽取。

 

应用

  • 每篇文档得到SimHash签名值后,接着计算两个签名的海明距离即可。根据经验值,对64位的 SimHash值,海明距离在3以内的可认为相似度比较高。
    • 海明距离的求法:异或时,只有在两个比较的位不同时其结果是1 ,否则结果为0,两个二进制“异或”后得到1的个数即为海明距离的大小。

举个例子,上面我们计算到的“CSDN博客”的simhash签名值为“1 0 1 0 1 1”,假定我们计算出另外一个短语的签名值为“1 0 1 0 0 0”,那么根据异或规则,我们可以计算出这两个签名的海明距离为2,从而判定这两个短语的相似度是比较高的。

换言之,现在问题转换为:对于64位的SimHash值,我们只要找到海明距离在3以内的所有签名,即可找出所有相似的短语。

但关键是,如何将其扩展到海量数据呢?譬如如何在海量的样本库中查询与其海明距离在3以内的记录呢?

  • 一种方案是查找待查询文本的64位simhash code的所有3位以内变化的组合
    • 大约需要四万多次的查询。
  • 另一种方案是预生成库中所有样本simhash code的3位变化以内的组合
    • 大约需要占据4万多倍的原始空间。

这两种方案,要么时间复杂度高,要么空间复杂度复杂,能否有一种方案可以达到时空复杂度的绝佳平衡呢?答案是肯定的:

  • 我们可以把 64 位的二进制simhash签名均分成4块,每块16位。根据鸽巢原理(也称抽屉原理),如果两个签名的海明距离在 3 以内,它们必有一块完全相同。如下图所示:
  • 然后把分成的4 块中的每一个块分别作为前16位来进行查找,建倒排索引。

具体如下图所示:

如此,如果样本库中存有2^34(差不多10亿)的simhash签名,则每个table返回2^(34-16)=262144个候选结果,大大减少了海明距离的计算成本。

  • 假设数据是均匀分布,16位的数据,产生的像限为2^16个,则平均每个像限分布的文档数则为2^34/2^16 = 2^(34-16)) ,四个块返回的总结果数为 4* 262144 (大概 100 万)。
    • 这样,原本需要比较10亿次,经过索引后,大概只需要处理100万次。

 

【References】

http://leoncom.org/?p=650607

http://taop.marchtea.com/06.03.html

Advertisements

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google+ photo

You are commenting using your Google+ account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s