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。