浅谈simhash及其python实现

作者原创，转载请注明出处。

一直想写个总结来回顾simhash，一直没抽出时间，现在还是好好写写总结一下。作者随笔，废话有点多，不喜勿喷，欢迎指教。

谷歌每天从网上抓取海量的信息，怎么样区分重复的呢，据说就采用了simhash算法，当然肯定也不仅仅就只采用它，不过至少可以说明其性能。

预备知识：

我们知道，在文本去重的时候，有很多方式，在文本与文本之间对比，如果是整篇对比，费时费力，有人就想到用什么东西代表每篇文章，如摘要，当然，对计算机来说，摘要和整篇的区别只是缩小了篇幅，所以又有人想到了采用关键字来对比。这样确实可以大大缩减我们对比的复杂性。那我们怎么得到一篇文章的关键字呢？一般采用词频（TF），但是只用词频，如中文出现类似“的”、“我们”之类的词语很多，应该怎么去掉这些词语呢，手动去掉实在是麻烦，于是可以结合逆向词频（IDF)，这就是著名的TD-IDF，一种提取一个文章的关键词的算法。词频我们很好理解，一个词语在整篇文章中出现的次数与词语总个数之比。IDF又怎么算呢，假如一个词语，在我们所有文章中出现的频率都非常高（例如“的”在我们多个文本中出现的次数很多），我们就认为，这个词语不具有代表性，就可以降低其作用，也就是赋予其较小的权值。

那这个权重，我们怎么计算呢，（这里敲公式比较麻烦，直接找来图片），如下图，分子代表文章总数，分母表示该词语在这些文章（|D|）出现的篇数。一般我们还会采取分母加一的方法，防止分母为0的情况出现，在这个比值之后取对数，就是IDF了。

好了，在得到idf之后，最终用tf*idf得到一个词语的权重。这里我知道了TD-IDF可以计算一篇文章的关键词。在我们取得一篇的文章的关键词，之后，我们可以采取每篇文章对比其关键词的方法来去重。

这里又有一个权衡，假如我们取的关键词过少，就不能很好代表一篇文章，假如我们取很多，又会降低效率。有没有一种方法，既可以很少的对比，又能有好的代表性呢。答案肯定是有的，于是simhash产生了。

（汗，终于讲到正题来了）

原理：

simhash是一种局部敏感hash。我们都知道什么是hash。那什么叫局部敏感呢，假定A、B具有一定的相似性，在hash之后，仍然能保持这种相似性，就称之为局部敏感hash。

在上文中，我们得到一个文档的关键词，取得一篇文章关键词集合，又会降低对比效率，我们可以通过hash的方法，把上述得到的关键词集合hash成一串二进制，这样我们直接对比二进制数，看其相似性就可以得到两篇文档的相似性，在查看相似性的时候我们采用海明距离，即在对比二进制的时候，我们看其有多少位不同，就称海明距离为多少。在这里，我是将文章simhash得到一串64位的二进制，一般取海明距离为3作为阈值，即在64位二进制中，只有三位不同，我们就认为两个文档是相似的。当然了，这里可以根据自己的需求来设置阈值。

就这样，我们把一篇文档用一个二进制代表了，也就是把一个文档hash之后得到一串二进制数的算法，称这个hash为simhash。

具体simhash步骤如下：

（1）将文档分词，取一个文章的TF-IDF权重最高的前20个词（feature）和权重（weight）。即一篇文档得到一个长度为20的（feature：weight）的集合。

（2）对其中的词（feature），进行普通的哈希之后得到一个64为的二进制，得到长度为20的（hash : weight）的集合。

（3）根据（2）中得到一串二进制数（hash）中相应位置是1是0，对相应位置取正值weight和负值weight。例如一个词进过（2）得到（010111：5）进过步骤（3）之后可以得到列表[-5,5,-5,5,5,5]，即对一个文档，我们可以得到20个长度为64的列表[weight，-weight...weight]。

（4）对（3）中20个列表进行列向累加得到一个列表。如[-5,5,-5,5,5,5]、[-3,-3,-3,3,-3,3]、[1,-1,-1,1,1,1]进行列向累加得到[-7，1，-9，9，3，9]，这样，我们对一个文档得到，一个长度为64的列表。

（5）对（4）中得到的列表中每个值进行判断，当为负值的时候去0，正值取1。例如，[-7，1，-9，9，3，9]得到010111，这样，我们就得到一个文档的simhash值了。

（6）计算相似性。连个simhash取异或，看其中1的个数是否超过3。超过3则判定为不相似，小于等于3则判定为相似。

呼呼呼，终于写完大致的步骤，可参考下图理解步骤。

python实现：

在下面python实现中，用的结巴分词，得到tf-idf的权值。

# -*- coding: utf-8 -*-
import jieba
import jieba.analyse
import numpy as np
import json

class simhash:
    def __init__(self,content):
        self.simhash=self.simhash(content)

    def __str__(self):
        return str(self.simhash)

    def simhash(self,content):
        seg = jieba.cut(content)
        jieba.analyse.set_stop_words('stopword.txt')
        keyWord = jieba.analyse.extract_tags(
            '|'.join(seg), topK=20, withWeight=True, allowPOS=())#在这里对jieba的tfidf.py进行了修改
        #将tags = sorted(freq.items(), key=itemgetter(1), reverse=True)修改成tags = sorted(freq.items(), key=itemgetter(1,0), reverse=True)
        #即先按照权重排序，再按照词排序
        keyList = []
        # print(keyWord)
        for feature, weight in keyWord:
            weight = int(weight * 20)
            feature = self.string_hash(feature)
            temp = []
            for i in feature:
                if(i == '1'):
                    temp.append(weight)
                else:
                    temp.append(-weight)
            # print(temp)
            keyList.append(temp)
        list1 = np.sum(np.array(keyList), axis=0)
        print(list1)
        if(keyList==[]): #编码读不出来
            return '00'   
        simhash = ''
        for i in list1:
            if(i > 0):
                simhash = simhash + '1'
            else:
                simhash = simhash + '0'
        return simhash


    def string_hash(self,source):
        if source == "":
            return 0
        else:
            x = ord(source[0]) << 7
            m = 1000003
            mask = 2 ** 128 - 1
            for c in source:
                x = ((x * m) ^ ord(c)) & mask
            x ^= len(source)
            if x == -1:
                x = -2
            x = bin(x).replace('0b', '').zfill(64)[-64:]
            print(source,x)

            return str(x)

        '''
        以下是使用系统自带hash生成，虽然每次相同的会生成的一样，
        不过，对于不同的汉子产生的二进制，在计算海明码的距离会不一样，
        即每次产生的海明距离不一致
        所以不建议使用。
        '''
        # x=str(bin(hash(source)).replace('0b','').replace('-','').zfill(64)[-64:])
        # print(source,x,len(x))
        # return x


    def hammingDis(self,com):
        t1 = '0b' + self.simhash
        t2 = '0b' + com.simhash
        n=int(t1, 2) ^ int(t2, 2)
        i=0
        while n:
            n &= (n-1)
            i+=1
        return i