关于SimHash算法原理

最近发邮件讨论Semantic Hashing的同学和同事很多,推荐李老师的文献列表供大家参阅:http://cs.nju.edu.cn/lwj/L2H.html

前言:
SimHash: Similarity Estimation Techniques from Rounding Algorithms 2002
A locality sensitive hashing scheme: sim(x,y). is a method of performing probabilistic dimension reduction of high-dimensional data.
MinHash(Min-wise independent permutations): is a technique for quickly estimating how similar two sets are. The scheme was invented by Andrei Broder (1997), and initially used in the AltaVista search engine to detect duplicate web pages and eliminate them from search results. It has also been applied in large-scale clustering problems, such as clustering documents by the similarity of their sets of words.
W-shingling is a set of unique “shingles” — contiguous subsequences of tokens in a document — that can be used to gauge the similarity of two documents.
调研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
整个过程可以参考下图:

按照Detecting Near Duplicates for Web Crawling这篇论文中阐述的,64位simhash,海明距离在3以内的文本都可以认为是近重复文本。当然,具体数值需要结合具体业务以及经验值来确定。
Simhash具有两个“冲突的性质”:
1. 它是一个hash方法
2. 相似的文本具有相似的hash值,如果两个文本的simhash越接近,也就是汉明距离越小,文本就越相似。

因此海量文本中查重的任务转换位如何在海量simhash中快速确定是否存在汉明距离小的指纹。
也就是:在n个f-bit的指纹中,查询汉明距离小于k的指纹。

在文章的实验中(见最后),simhash采用64位的哈希函数。在80亿网页规模下汉明距离=3刚好合适。
因此任务的f-bit=64 , k=3 , n= 8*10^11

使用上述方法产生的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返回的结果呈此消彼长的关系,也就是说,时间效率与空间效率不可兼得,参看下图:

事实上,这就是Google每天所做的,用来识别获取的网页是否与它庞大的、数以十亿计的网页库是否重复。另外,simhash还可以用于信息聚类、文件压缩等。
由于文本已经压缩成8个字节了,因此其实Simhash近似查重精度并不高:

[参考]: 1. 我的数学之美系列二 —— simhash与重复信息识别
2. Similarity Estimation Techniques from Rounding Algorithms
3. Detecting Near Duplicates for Web Crawling[附:PPT报告]
4. simhash进行文本查重
5. simhash与Google的网页去重
[资料]:1. Simhash Python实现
2. Simhash java实现

关于SimHash算法原理》上有 2 条评论

  1. Pingback 引用通告: simhash算法的原理_数据结构和算法-Beiden 个人博客

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>