一直想写个总结来回顾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则判定为相似。

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

 

SimHash 算法原理图

 

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

 

原文转自浅谈simhash及其python实现 (CSDN)

 

 

参考推荐

文档去重算法:SimHash

SimHash 算法原理及实现

推荐方法总结

基于内容的推荐系统概述

四种推荐解释模板及评估标准

基于协同过滤的推荐系统

基于内容和基于协同过滤的混合推荐系统

哈希表算法原理

八大排序算法图文讲解

10大程序员基础实用算法

Kafka:下一代分布式消息系统

大数据流式处理框架:Storm、Spark、Samza