simhash的原理

电玩女神 2022-05-24 09:28 169阅读 0赞

转自：[https://blog.csdn.net/madujin/article/details/53152619][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_img-blog.csdn.net_20161114000908955]

[https_blog.csdn.net_madujin_article_details_53152619]: https://blog.csdn.net/madujin/article/details/53152619
[https_img-blog.csdn.net_20161114000908955]: https://img-blog.csdn.net/20161114000908955