SimHash算法详解

• 更多分享：www.catbro.cn

一、前言：

• 算法是程序的灵魂，本次小编入手SimHash算法是为了后在在自己编写的博客上增加一个相似文章推荐的功能。
• 选择SimHash主要考虑其：1、Google的东西都以简洁高效著称，既然Google能用其来判断海量网页的相似度，既然能判断相似度，那么相似度高的也就可以理解为相关性高，小编觉得用在技术博文上还是可行的。2、实现相对简单，主要是可以在上传文章的时候就计算获取其simhash的值，在用户查阅文章的时候直接比较即可

二、SimHash介绍：

• 先贴一张网上找的图

• simhash可以计算文本间的相似度，我们可以通过simhash算法计算出文档的simhash值，通过比较各个文本的simhash值之间的汉明距离的大小来判断其相似度，汉明距离越小，则相似度越大。一般大文本去重，大小<=3的即可判断为重复。

• simhash算法分为5个步骤：1、分词、2、hash、3、加权、4、合并、5、降维

• 1、分词：

  • 选择适合自己的分词库进行分词即可。
  • 如“欢迎来到随迹”->（分词后）“欢迎”、“来到”、“随迹”

• 2、hash：

  • 对每个词计算其hash值，hash值为二进制数01组成的n-bit签名。
  • 设“欢迎“（100101）、“来到”（101011）、“随迹”（101011）

• 3、加权：

  • 对于给定的文本，权值即为分词后对应词出现的数量。给所有特征向量进行加权，即W = Hash * weight；这里我们假设三个词权值分别为4、5、9；
  • 根据计算规则遇到1则hash值和权值正相乘，遇到0则hash值和权值负相乘
  • 例如给“欢迎”的hash值“100101”加权得 到：W(欢迎) = 1001014 = 4 -4 -4 4 -4 4，给“来到”的hash值“101011”加权得到：W(来到)=1010115 = 5 -5 5 -5 5 5，剩下的按此规则计算

• 4、合并

  • 将上述各个特征向量的加权结果累加，变成只有一个序列串。拿前两个特征向量举例，例如“欢迎”的“4 -4 -4 4 -4 4”和“来到”的“5 -5 5 -5 5 5”进行累加，得到“4+5 -4+-5 -4+5 4+-5 -4+5 4+5”，得到“9 -9 1 -1 1”。

• 5、降维

  • 对于n-bit签名的累加结果，如果大于0则置1，否则置0，从而得到该语句的simhash值，最后我们便可以根据不同语句simhash的海 明距离来判断它们的相似度。例如把上面计算出来的“9 -9 1 -1 1 9”降维（某位大于0记为1，小于0记为0），得到的01串为：“1 0 1 0 1 1”，从而形成它们的simhash签名。

三、总结

• 通过以上内容的学习，我们基本明白来simhash的计算过程，下一章我们将通过使用simhash来实现博文的相似度判断来实际的动手实现该算法。
• 更多分享请点击：www.catbro.cn