海量信息查重-simhash

​ 造成网页近重复的可能原因主要包括：镜像网站；内容复制；嵌入广告；计数改变；少量修改
​ 传统比较两个文本相似性的方法，大多是将文本分词之后，转化为特征向量距离的度量，比如常见的欧氏距离、海明距离或者余弦角度等等。两两比较固然能很好地适应，但这种方法的一个最大的缺点就是，无法将其扩展到海量数据。例如，试想像Google那种收录了数以几十亿互联网信息的大型搜索引擎，每天都会通过爬虫的方式为自己的索引库新增的数百万网页，如果待收录每一条数据都去和网页库里面的每条记录算一下余弦角度，其计算量是相当恐怖的。
​ 考虑采用为每一个web文档通过hash的方式生成一个指纹（fingerprint）。但是，传统的加密式hash，比如md5，其设计的目的是为了让整个分布尽可能地均匀，输入内容哪怕只有轻微变化，hash就会发生很大地变化。我们理想当中的哈希函数，需要对几乎相同的输入内容，产生相同或者相近的hashcode，换句话说，hashcode的相似程度要能直接反映输入内容的相似程度。很明显，前面所说的md5等传统hash无法满足我们的需求。
​ simhash是locality sensitive hash（局部敏感哈希）的一种，它产生的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的。距离越小，则相似度越大。一般大文本去重，大小<=3的即可判断为重复。
​ 如何实现这种hash算法呢？simhash算法分为5个步骤：1、分词、2、hash、3、加权、4、合并、5、降维

1. 分词：

选择适合自己的分词库进行分词即可。
如“欢迎来到随迹”->（分词后）“欢迎”、“来到”、“随迹”

2. hash：

对每个词计算其hash值，hash值为二进制数01组成的n-bit签名。
设“欢迎“（100101）、“来到”（101011）、“随迹”（101011）

3. 加权：

对于给定的文本，权值即为分词后对应词出现的数量。给所有特征向量进行加权，即W = Hash * weight；这里我们假设三个词权值分别为4、5、9；
根据计算规则遇到1则hash值和权值正相乘，遇到0则hash值和权值负相乘
例如给“欢迎”的hash值“100101”加权得 到：W(欢迎) = 1001014 = 4 -4 -4 4 -4 4，给“来到”的hash值“101011”加权得到：W(来到)=1010115 = 5 -5 5 -5 5 5，剩下的按此规则计算

4. 合并：

将上述各个特征向量的加权结果累加，变成只有一个序列串。拿前两个特征向量举例，例如“欢迎”的“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签名。