传统相似度算法举例
针对文本相似性计算，很多开发朋友首先想到的应该是使用向量空间模型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:
- Define a fingerprint size (for instance 32 bits)
- Create an array
V[]filled with this size of zeros - For each element in the dataset, we create a unique hash with md5,
sha1 of any other hash algorithm that give same-sized results - For each hash, for each bit
iin this hash:
4.1 If the bit is0, we add1toV[i]
4.2 If the bit is1, we take1fromV[i] - For each bit
jof the global fingerprint:
5.1 IfV[j] >= 0, we setV[j] = 1
5.2 IfV[j] < 0, we setV[j] = 0
通过上述方法得到两个数据集的 fingerprint 后，对两个 fingerprint 做 XOR 操作：
10101011100010001010000101111100
XOR 10101011100010011110000101111110
= 00000000000000010100000000000010
得到结果中的 1 代表的就是两个数据的不同，计算标记的总数再与 fingerprint 的长度相除，得到的就是两个数据集的不同，这里为 3 / 32 = 0,09375。
