SimHash算法原理

一、什么是SimHash
SimHash算法是Google在2007年发表的论文《Detecting Near-Duplicates for Web Crawling》中提到的一种指纹生成算法，被应用在Google搜索引擎网页去重的工作之中。
简单的说，SimHash算法主要的工作就是将文本进行降维，生成一个SimHash值，也就是论文中所提及的“指纹”，通过对不同文本的SimHash值进而比较海明距离，从而判断两个文本的相似度。
对于文本去重这个问题，常见的解决办法有余弦算法、欧式距离、Jaccard相似度、最长公共子串等方法。但是这些方法并不能对海量数据高效的处理。
比如说，在搜索引擎中，会有很多相似的关键词，用户所需要获取的内容是相似的，但是搜索的关键词却是不同的，如“北京好吃的火锅“和”哪家北京的火锅好吃“，是两个可以等价的关键词，然而通过普通的hash计算，会产生两个相差甚远的hash串。而通过SimHash计算得到的Hash串会非常的相近，从而可以判断两个文本的相似程度。

二、SimHash的计算原理
SimHash算法主要有五个过程：分词、Hash、加权、合并、降维。
借用一张网络上经典的图片来描述整个过程：

1.分词
对给定的一段文本进行分词，产生n个特征词，并赋予每个特征词一个权重。比如一段文本为“中国科大计算机系的学生的能力怎么样”，产生的特征词就应该是“中国科大”、“计算机系”、“的”、“学生”、“能力”、“怎么样”，然后对这些词分别赋予权重，假设有1-5五个分类，分词之后以上五个词便会各有一个权重，比如中国科大（4）、计算机系（3）、的（1）、学生（4）、能力（5）、怎么样（3）。
其中，数字越大，代表特征词在句子中的重要性就越高。这样，我们就得到了一个文本的分词的词向量和每个词向量对应的权重。

2.Hash
通过hash函数对每一个词向量进行映射，产生一个n位二进制串，比如****的hash值就是100101。

3.加权
前面的计算我们已经得到了每个词向量的Hash串和该词向量对应的权重，这一步我们计算权重向量W=hash*weight。
具体的计算过程如下：hash二进制串中为1的乘以该特征词的分词权重，二进制串中为0的乘以该特征词的分词权重后取负，继而得到权重向量。
举个例子，****的hash二进制串是100101，****的权重是3，那么生成的权重向量就是[3，-3，-3，3，-3，3]。

4.合并
对于一个文本，我们计算出了文本分词之后每一个特征词的权重向量，在合并这个阶段，我们把文本所有词向量的权重向量相累加，得到一个新的权重向量，形如[3，4，1，5，-5，1]

5.降维
对于前面合并后得到的文本的权重向量，大于0的位置1，小于等于0的位置0，就可以得到该文本的SimHash值，以上面提到的[3，4，1，5，-5，1]为例，我们得到[1，1，1，1，0，1]这个bit串，也就是论文中提及的该文本的指纹。
到此为止，我们已经计算出了一个文本的SimHash值。那么，如何判断两个文本是否相似呢？我们要用到海明距离。

三、相似度判断
对于两个文本的SimHash的相似度判断，我们使用海明距离来计算。
什么是海明距离呢？
简单的说，海明距离可以理解为，两个二进制串之间相同位置不同的个数。举个例子，[1，1，1，0，0，0]和[1，1，1，1，1，1]的海明距离就是3。
在处理大规模数据的时候，我们一般使用64位的SimHash，正好可以被一个long型存储。这种时候，海明距离在3以内就可以认为两个文本是相似的。

四、大规模数据下的海明距离计算
在大规模数据量的情况下，如果对两个文本64位的SimHash的海明距离采用每一位比较的方法进行计算，找出海明距离小于等于3的文本，这样会耗费大量时间和资源。
这时候有一种较好的办法来均衡计算海明距离的时间复杂度和空间复杂度，具体的计算思想是这样的：
把64位的SimHash分成四个part，如果两个SimHash相似（海明距离小于等于3），根据鸽巢原理，必然有一个part是完全相同的。
这样，我们通过比较part，快速的得出两个文本是否相似。