文档去重算法：SimHash

网页去重算法有哪些，很多人不假思索的说出了欧氏距离、余弦向量相似度匹配，但如果是数十亿级别的网页去重呢？

这下糟糕了，因为每两个网页都需要计算一次向量内积，查重效率太低了！

当时就想：论查找效率肯定是要考虑hash算法，相同字符串的hashcode肯定相同，不同字符串的hashcode却是大不相同，这也不符合要求啊，会不会存在一种算法能够使相似字符串的code值也相同或相似呢，于是就找到了Google的网页去重算法-SimHash。我们在使用SimHash算法前需要根据文档量级选择SimHash码的位数，一般可选32位或者64位。

海明距离：在信息编码中，两个合法代码对应位上编码不同的位数称为码距，又称海明距离。

注：比如合法代码长度为8，那么00111100与11110000的海明距离是4,10101111与01101111的海明距离是2,11110000与11110000的海明距离是0.

SimHash 算法原理

谷哥（Google）出品，谷哥（Google）风格，简单（Simple）实用，算法原理图：

解释一下图片：

feature可以指一篇文档分词后的某个词，即将文档中的某个词作为一个特征。

weight是这个词的权重，这里可以是这个词在这个句子中出现的次数。

这里的hash算法就是传统的hash算法，通过调用一个hash函数实现的。

SimHash 是为了计算任意多篇文档之间的相似度存在的，通过simhash算法可以计算出文档的simhash值，通过各个文档计算出的二进制值来计算文档之间的汉明距离，然后根据汉明距离来比较文档之间的相似度。

汉明距离是指两个相同长度的字符串相同位置上不同的字符的个数。

SimHash 算法分为5个步骤：分词、hash、加权、合并、降维

具体过程如下所述：

1）分词

给定一段语句，进行分词，得到有效的特征向量，然后为每一个特征向量设置1-5等5个级别的权重（如果是给定一个文本，那么特征向量可以是文本中的词，其权重可以是这个词出现的次数）。例如给定一段语句：“CSDN博客结构之法算法之道的作者July”，分词后为：“CSDN 博客结构之法算法之道的作者 July”，然后为每个特征向量赋予权值：CSDN(4) 博客(5) 结构(3) 之(1) 法(2) 算法(3) 之(1) 道(2) 的(1) 作者(5) July(5)，其中括号里的数字代表这个单词在整条语句中的重要程度，数字越大代表越重要。

2）hash

通过hash函数计算各个特征向量的hash值，hash值为二进制数01组成的n-bit签名。比如“CSDN”的hash值Hash(CSDN)为100101，“博客”的hash值Hash(博客)为“101011”。就这样，字符串就变成了一系列数字。

3）加权

在hash值的基础上，给所有特征向量进行加权，即W = Hash * weight，且遇到1则hash值和权值正相乘，遇到0则hash值和权值负相乘。

例如给“CSDN”的hash值“100101”加权得到：W(CSDN) = 100101*4 = 4 -4 -4 4 -4 4，给“博客”的hash值“101011”加权得到：W(博客)=101011*5 = 5 -5 5 -5 5 5，其余特征向量类似此般操作。

4）合并

将上述各个特征向量的加权结果累加，变成只有一个序列串。

拿前两个特征向量举例，例如“CSDN”的“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 算法优缺点

优点：

1）算法高效，非常适用于大规模网页去重

2）算法非常容易使用在MapReduce等分布式计算中

3）对于每篇文档来说，算法消耗空间非常小

缺点：

1）对于长文档和短文档同时存在的情况，只依靠算法本身尚不能完美解决网页去重的问题

2）对于两篇看似完全不相关的文档来说，其海明距离甚至有可能为0，但出现这种情况的概率极小

SimHash 重复信息识别

在工作学习中，我往往感叹数学奇迹般的解决一些貌似不可能完成的任务，并且十分希望将这种喜悦分享给大家，就好比说：“老婆，出来看上帝”

随着信息爆炸时代的来临，互联网上充斥着着大量的近重复信息，有效地识别它们是一个很有意义的课题。

例如，对于搜索引擎的爬虫系统来说，收录重复的网页是毫无意义的，只会造成存储和计算资源的浪费；

同时，展示重复的信息对于用户来说也并不是最好的体验。

造成网页近重复的可能原因主要包括：

镜像网站
内容复制
嵌入广告
计数改变
少量修改

一个简化的爬虫系统架构如下图所示：

事实上，传统比较两个文本相似性的方法，大多是将文本分词之后，转化为特征向量距离的度量，比如常见的欧氏距离、海明距离或者余弦角度等等。两两比较固然能很好地适应，但这种方法的一个最大的缺点就是，无法将其扩展到海量数据。例如，试想像Google那种收录了数以几十亿互联网信息的大型搜索引擎，每天都会通过爬虫的方式为自己的索引库新增的数百万网页，如果待收录每一条数据都去和网页库里面的每条记录算一下余弦角度，其计算量是相当恐怖的。

我们考虑采用为每一个web文档通过hash的方式生成一个指纹（fingerprint）

传统的加密式hash，比如md5，其设计的目的是为了让整个分布尽可能地均匀，输入内容哪怕只有轻微变化，hash就会发生很大地变化。我们理想当中的哈希函数，需要对几乎相同的输入内容，产生相同或者相近的hashcode，换句话说，hashcode的相似程度要能直接反映输入内容的相似程度。很明显，前面所说的md5等传统hash无法满足我们的需求。

simhash是locality sensitive hash（局部敏感哈希）的一种，最早由Moses Charikar在《similarity estimation techniques from rounding algorithms》一文中提出。

Google就是基于此算法实现网页文件查重的。

我们假设有以下三段文本：

the cat sat on the mat
the cat sat on a mat
we all scream for ice cream

使用传统hash可能会产生如下的结果：

引用

irb(main):006:0> p1 = 'the cat sat on the mat'
irb(main):005:0> p2 = 'the cat sat on a mat'
irb(main):007:0> p3 = 'we all scream for ice cream'
irb(main):007:0> p1.hash
=> 415542861
irb(main):007:0> p2.hash
=> 668720516
irb(main):007:0> p3.hash
=> 767429688

使用simhash会应该产生类似如下的结果：

引用

irb(main):003:0> p1.simhash
=> 851459198
00110010110000000011110001111110

irb(main):004:0> p2.simhash
=> 847263864
00110010100000000011100001111000

irb(main):002:0> p3.simhash
=> 984968088
00111010101101010110101110011000

海明距离的定义，为两个二进制串中不同位的数量。

上述三个文本的simhash结果，其两两之间的海明距离为(p1,p2)=4，(p1,p3)=16，(p2,p3)=12。

事实上，这正好符合文本之间的相似度，p1和p2间的相似度要远大于与p3的。

如何实现这种hash算法呢？以上述三个文本为例，整个过程可以分为以下六步：
1、选择simhash的位数，请综合考虑存储成本以及数据集的大小，比如说32位
2、将simhash的各位初始化为0
3、提取原始文本中的特征，一般采用各种分词的方式。比如对于"the cat sat on the mat"，采用两两分词的方式得到如下结果：{"th", "he", "e ", " c", "ca", "at", "t ", " s", "sa", " o", "on", "n ", " t", " m", "ma"}
4、使用传统的32位hash函数计算各个word的hashcode，比如："th".hash = -502157718
，"he".hash = -369049682，……
5、对各word的hashcode的每一位，如果该位为1，则simhash相应位的值加1；否则减1
6、对最后得到的32位的simhash，如果该位大于1，则设为1；否则设为0

整个过程可以参考下图：

按照Charikar在论文中阐述的，64位simhash，海明距离在3以内的文本都可以认为是近重复文本。

当然，具体数值需要结合具体业务以及经验值来确定。

使用上述方法产生的SimHash可以用来比较两个文本之间的相似度。

问题是，如何将其扩展到海量数据的近重复检测中去呢？

譬如说对于64位的待查询文本的simhash code来说，如何在海量的样本库（>1M）中查询与其海明距离在3以内的记录呢？

下面在引入simhash的索引结构之前，先提供两种常规的思路。

第一种是方案是查找待查询文本的64位simhash code的所有3位以内变化的组合，大约需要四万多次的查询，参考下图：

另一种方案是预生成库中所有样本simhash code的3位变化以内的组合，大约需要占据4万多倍的原始空间，参考下图：

显然，上述两种方法，或者时间复杂度，或者空间复杂度，其一无法满足实际的需求。

我们需要一种方法，其时间复杂度优于前者，空间复杂度优于后者。

假设我们要寻找海明距离3以内的数值，根据抽屉原理，只要我们将整个64位的二进制串划分为4块，

无论如何，匹配的两个simhash code之间至少有一块区域是完全相同的，如下图所示：

由于我们无法事先得知完全相同的是哪一块区域，因此我们必须采用存储多份table的方式。

在本例的情况下，我们需要存储4份table，并将64位的simhash code等分成4份；

对于每一个输入的code，我们通过精确匹配的方式，查找前16位相同的记录作为候选记录，如下图所示：

让我们来总结一下上述算法的实质：
1、将64位的二进制串等分成四块
2、调整上述64位二进制，将任意一块作为前16位，总共有四种组合，生成四份table
3、采用精确匹配的方式查找前16位
4、如果样本库中存有2^34（差不多10亿）的哈希指纹，则每个table返回2^(34-16)=262144个候选结果，大大减少了海明距离的计算成本

我们可以将这种方法拓展成多种配置，不过，请记住，table的数量与每个table返回的结果呈此消彼长的关系，也就是说，时间效率与空间效率不可兼得，参看下图：