SimHash 相似度算法

传统相似度算法举例

针对文本相似性计算,很多开发朋友首先想到的应该是使用向量空间模型VSM(Vector Space Model)。使用VSM计算相似度,先对文本进行分词,然后建立文本向量,把相似度的计算转换成某种特征向量距离的计算,比如余弦角、欧式距离、Jaccard相似系数等。这种方法存在很大一个问题:需要对文本两两进行相似度比较,无法扩展到海量文本的处理。想想像Google这种全网搜索引擎,收录了上百亿的网页,爬虫每天爬取的网页数都是百万千万级别的。为了防止重复收录网页,爬虫需要对网页进行判重处理。如果采用VSM方法,计算量是相当可观的。

SimHash

传统的相似度算法想要计算两个数据集的相似性,至少需要将两个数据集全部遍历一遍,这在数据集较大时显然是不现实的。而使用类似 md5 或 sha1 这类即可以代表数据集特征,又可以大大缩小需要比较的数据集大小的 hash 算法自然是更好的选择。但是上述两种算法不能够适用于这种场景,因为即使数据集中的一个 bit 发生变化,这两种算法得到的 hash 值也会发生很大的变化。

SimHash does not behave like this: instead, it's a bit like a very compressed version of the dataset (it does not change a lot if the text does not change a lot).

The official SimHash algorithm is:

  1. Define a fingerprint size (for instance 32 bits)
  2. Create an array V[] filled with this size of zeros
  3. For each element in the dataset, we create a unique hash with md5,
    sha1 of any other hash algorithm that give same-sized results
  4. For each hash, for each bit i in this hash:
    4.1 If the bit is 0, we add 1 to V[i]
    4.2 If the bit is 1, we take 1 from V[i]
  5. For each bit j of the global fingerprint:
    5.1 If V[j] >= 0, we set V[j] = 1
    5.2 If V[j] < 0, we set V[j] = 0

通过上述方法得到两个数据集的 fingerprint 后,对两个 fingerprint 做 XOR 操作:

    10101011100010001010000101111100
XOR 10101011100010011110000101111110
  = 00000000000000010100000000000010

得到结果中的 1 代表的就是两个数据的不同,计算标记的总数再与 fingerprint 的长度相除,得到的就是两个数据集的不同,这里为 3 / 32 = 0,09375

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,771评论 0 33
  • 第一次看这个世界,第一次哇哇大哭,第一次哈哈大笑,第一次叫爸爸妈妈,第一次摔倒了爬起来,第一次自己吃饭,第一次自己...
    沫小薰阅读 221评论 0 0
  • 最近几天都在画牡丹花,因为这花开在一个我始终向往的地方,那里有我没有来得及实现的梦想,和一直思念的人。 妞是我大学...
    喵三娘stella阅读 1,772评论 3 51
  • 生活中什么样的人会让你耐心值迅速归零并想立刻马上躲得远远的? 对我来说是:拎不清的人 我是一个特怕麻烦的人,因此常...
    王小猫V阅读 769评论 0 0