simhash的原理

xiaoxiao2021-03-01  13

转自:https://blog.csdn.net/madujin/article/details/53152619 原理:

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则判定为相似。 https://img-blog.csdn.net/20161114000908955

转载请注明原文地址: https://www.6miu.com/read-3100220.html

最新回复(0)