海量去重算法simhash介绍

2007年,GoogleMoses Charikar发表的一篇论文“detecting near-duplicates for web crawling”中提出了simhash算法,这也是google出品的用于海量网页去重的一个局部敏感哈希算法。

Part 1 : 什么是Simhash

simhash是一种局部敏感的相似去重算法,是google采用的用于海量网页去重的一种算法。我们知道,哈希本身是放大分散的,两个字符串中只要有一丁点的不同,所生成的哈希(比如sha256)就会天差地别,这也就是为什么哈希能作为文件是否被篡改的原因。而局部敏感的指纹哈希则有所不同。这种局部敏感取决于两段文本的相似程度,当相似性很高时,我们可以通过一个检测阙值来判断文本是否相似。

simhash会将一串文本最终转化为64bit长度的指纹,可称为特征字。判断两个文本的特征字的距离,我们称之为海明距离。通过判断海明距离的大小即可判断两串文本是否相似(一般情况下海明距离<3则为相似)。

Part 2 : 论文基础

simhash算法的理论部分可以查阅Similarity Estimation Techniques from Rounding Algorithms(详情)这篇论文。

Part 3 : 实际用途

举个例子,假设有下面三个句子:

p1 = 'the cat sat on the mat'
p2 = 'the cat sat on a mat'
p3 = 'we all scream for ice cream'

那么我们观察后就知道p1p2其实是重复的,因为语义是相同的。而p3则和前两者不同。那么如何让代码来识别出这其中的不同呢?答案就是:simhash。

上述三段文本的指纹哈希分别如下:

irb(main):007:0> p1.hash
=> 415542861
irb(main):007:0> p2.hash
=> 668720516
irb(main):007:0> p3.hash
=> 767429688

算出了simhash,那么如何根据simhash判断重复呢?答案就是海明距离(hamming distance):

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

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

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

(p1,p2)=4
(p1,p3)=16
(p2,p3)=12

这就是整个去重的过程,我们发现p1和p2的海明距离为4,这个阙值应当根据具体业务来定。

Part 4 : Simhash原理

  1. 将一个 f 维的向量 V 初始化为 0 ; f 位的二进制数 S 初始化为 0
  2. 对每一个特征:用传统的 hash 算法对该特征产生一个 f 位的签名 b 。对 i=1 到 f : 如果b 的第 i 位为 1 ,则 V 的第 i 个元素加上该特征的权重; 否则,V 的第 i 个元素减去该特征的权重。
  3. 如果 V 的第 i 个元素大于 0 ,则 S 的第 i 位为 1 ,否则为 0 ;
  4. 输出 S 作为签名。

上述描述摘录自这里

Part 5 : 海明距离

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

计算汉明距离的一种方法,就是对两个位串进行异或(xor)运算,并计算出异或运算结果中1的个数。例如110和011这两个位串,对它们进行异或运算,其结果是:

110⊕011=101

异或结果中含有两个1,因此110和011之间的汉明距离就等于2。

Part 6 : 优势

  1. 计算速度快
  2. 存储空间小

Part 7 : 不足

  1. 很大情况下不能满足英文和中文,取决与分词词典。
  2. 存在部分语义重复的短文本无法被识别为重复。

Part 8 : 改进方案

  1. 结合语义去重LSI,计算速度慢,维度高。
  2. 结合公共最长字串LCS,计算速度慢,矩阵太庞大。
赞赏我吗