浅谈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腾讯云开发者
