SimHash文档去重

1. 首先SimHash的算法生成图如下图所示：

Image.jpg

生成步骤如下：

1. 对于每篇文章，选择分词作为该篇文章的特征，获取去掉噪音的词做为文档特征，为每个词赋予一个权重，该权重可以使用TFIDF来对应
2. 根据机器的存储以及性能，可以选择使用哪种hash算法，计算出每个词的hash值，可以是32位的也可以是64位的
3. 对于上述hash值的每一位乘以相应的权重，得到新的hash序列，最后将每个词的每一位hash序列相加求和
4. 对于求和后的hash序列，如果该位>0，最终的simhash的该位=1,否则simhash=0

simhash可以用来衡量两篇文档的相似程度，如果两篇文档比较相似，那么他们的simhash值也相似，这种hash算法与MD5算法不同：

对于MD5算法，稍微对某个字符串修改一点，那么得出的MD5戳就会发生很大的变化。

2.如何通过两篇文档的simHash来检查两篇文档是否相似呢？使用海明距离。

海明距离：两个hash串异或之后1的个数，也就是两个simhash串不同的位数。根据经验，一般海明距离<=3或者4的时候，两篇文档相似。

如何高效计算某个二进制串中为1的个数呢？

int getHammingDistance(BigInteger hash1, BigInteger hash2){

    BigInteger data = hash1.xor(hash2);

    int tot = 0;

    while (data != 0) {

             tot += 1;

             data = data&(data-1);

    }

    return tot;

}

时间复杂度为o(n), 我们知道一个二进制数减掉1之后和该二进制数去&操作,相当于把最右边的一位1变成了0,因此能执行多少次这样的操作就有多少个1存在.

3. 工程实现的问题：

在工程实现中，往往数据量较大, 如每篇文章要和500万的文章进行比较，假如hash值位数是64位，比较一次的时间复杂度是o(64)

对于每篇文章都要比较500万次，时间消耗也就较大。

因此第一步需要缩小比较范围，以空间换时间的方式，可以借鉴HashMap的存储和查找方式,key代表1/4的hash值,value使用链表的方式存储多个文章的simhash:

1.将simhash值拆分成4个16位的hash
2.分别拿着4个hash去map中是否有该值,如果有的话,追加到key对应的链表中,没有的话新建key对应的链表

在查找的时候,可以分别拿着4个16为的hash值,去查找map,然后依次和value链表中的多个simhash序列比较即可.具体可参照下面的参考链接.

优缺点：

simhash用于比较大文本，比如500字以上效果比较好，距离小于3的基本都是相似，误判率也比较低。

但是如果处理的是微博信息，最多也就140个字，使用simhash的效果并不那么理想。

参考：

https://yanyiwu.com/work/2014/01/30/simhash-shi-xian-xiang-jie.html

http://www.lanceyan.com/tech/arch/simhash_hamming_distance_similarity2-html.html