SimHash算法详解

  发布日期:   2018-06-11
  最新修改:   2020-10-27
  阅读次数:   371 次

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

2019090906_3726e5e13f7439a38a4dec204781712e.png

  • 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

   转载规则

《SimHash算法详解字》GajAngels 采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可。