1、simHash简介
simHash算法是在GoogleMoses Charikear 2007年发表的一篇论文《Detecting Near-duplicates for web crawling》中提出的，专门用于解决数亿页面的去重任务。
simHash 是一种局部敏感哈希。其主要思想是降维，将高维特征向量映射成低维特征向量，然后比较两个特征向量的汉明距离。 ) 来确定文章之间的相似性。
什么是局部敏感度？假设A和B有一定的相似度，经过hash后，相似度仍然可以保持，称为局部敏感hash
汉明距离：
汉明距离，又称汉明距离，在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置上不同字符的个数。将一个字符串转换成另一个字符串需要替换的字符个数，可以使用异或运算。
例如： 1011与1001之间的汉明距离是1。
2、simHash具体流程
simHash算法总共分为5个流程： 分词、has、加权、合并、降维。
分词
对待处理的文档进行中文分词，得到有效的特征及其权重。可以使用TF-IDF方法获取文章权重最高的前K个词（特征）和权重（权重）。可以使用 jieba.analysis.extract_tags() 来实现
hash
对获取的词（特征）进行普通哈希运算，计算哈希值，从而得到一个二进制长度为n位，得到一组（哈希：权重）。
加权
在得到的hash值的基础上，根据对应的权重值进行权重，即W=hash*weight。即如果hash为1，则乘以正权重，如果为0，则乘以负权重。例如，经过哈希（010111:5）可以得到一个词。在步骤（3）之后，可以得到列表[-5,5,-5,5,5,5]。
合并
上面得到的每个向量的加权结果相加，只有一个序列串。如[-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 的列表。
降维
对得到的n位签名的累加结果的每个值进行判断，如果大于0，则置1，否则置0，从而得到语句的simhash值。例如 [-7, 1, -9, 9, 3, 9] 得到 010111，所以我们得到一个文档的 simhash 值。
最后根据不同句子的simhash值的汉明距离来判断相似度。
根据经验值，对于 64 位的 SimHash 值，3 以内的汉明距离可以认为是比较高的相似度。
3、Python实现simHash
使用Python实现simHash算法，具体如下：
# -*- coding:utf-8 -*-
import jieba
import jieba.analyse
import numpy as np
class SimHash(object):
def simHash(self, content):
seg = jieba.cut(content)
# jieba.analyse.set_stop_words('stopword.txt')
# jieba基于TF-IDF提取关键词
keyWords = jieba.analyse.extract_tags("|".join(seg), topK=10, withWeight=True)
keyList = []
for feature, weight in keyWords:
print('weight: {}'.format(weight))
# weight = math.ceil(weight)
weight = int(weight)
binstr = self.string_hash(feature)
temp=[]
for c in binstr:
if (c == '1'):
temp.append(weight)
else:
temp.append(-weight)
keyList.append(temp)
listSum = np.sum(np.array(keyList), axis = 0)
if (keyList == []):
return '00'
simhash = ''
for i in listSum:
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('strint_hash: %s, %s'%(source, x))
return str(x)
def getDistance(self, hashstr1, hashstr2):
'''
计算两个simhash的汉明距离
'''
length = 0
for index, char in enumerate(hashstr1):
if char == hashstr2[index]:
continue
else:
length += 1
return length
if __name__ == '__main__':
simhash = SimHash()
s1 = simhash.simHash('我想洗照片')
s2 = simhash.simHash('可以洗一张照片吗')
dis = simhash.getDistance(s1, s2)
print('dis: {}'.format(dis))计算相似度对于短文本不是很准确，更适合长文本。
本文为原创文章，版权归知行编程网所有，欢迎分享本文，转载请保留出处！
内容反馈