[转]网页查重算法Shingling和Simhash研究

1　引言

据统计,互联网上的重复网页约占30%~45%。这其中有由于镜像转载引起的内容完全相同的网页,也有仅存在微小差别的网页,比如广告,计数器,时间戳等不同,而这些差别是和搜索的内容无关的。根据中国互联网络信息中心2005年7月发布的统计报告显示,用户在回答“检索信息时遇到的最大问题”这一提问时,选择“重复信息太多”选项的占44.6%,排名第1位[1]。将相似的网页消除,可以节省网络带宽,减少占用的存储空间,提高索引的质量,即提高查询服务的效率和质量,同时减轻网页所在远程服务器的负担。在网页查重算法中shingling和simhash被认为是当前最好的两个算法。

2　Shingling算法Shingling主要是为

了发现大致相同的文档,即内容相同,除了格式上的变动,微小的修改、签名和logo的不同。同时,也可以发现一个文档“大致包含”在另一个之中。文中首先用数学的概念严格定义了什么叫“大致相同”:两个文档A和B之间的相似度是介于0和1之间的一个数字,这样如果这个数字接近1,那么这两个文档就是“大致相同”的。包含度的定义与此相同。计算两个文档之间的相似度和包含度,只为两个文档保留几百字节的sketch就可以了。Sketch的计算效率比较高,时间上和文档的大小成线性关系,而给出两个sketch,它们所对应的文档的相似度和包含度的计算在时间上和这两个sketch的大小成线性关系[2]。

该算法把文档看做文字组成的序列,首先把它词法分析为标示(token)序列,忽略一些微小的细节,比如格式,html命令,大小写。然后把文档D和标示的子串所组成的集合S(D,W)联系起来。D中的相邻子串称为shingle。给出一个文档D,定义它的w-shinglingS(D,W)为D中所有大小为W的不同的shingle。比如,(a,rose,is,a,rose,is, a, rose)的4-shingling就是集合: {(a,rose,is,a),(rose,is,a,rose),(is,a,rose,is)}给定shingle的大小,两个文档A和B的相似度r定义为:r(A,B)=|S(A)∩S(B)|S(A)∪S(B)因此,相似度是介于0和1之间的一个数值,且r(A,A)=1,即一个文档和它自身100%相似。给定一个shingle大小W,U是所有大小为W的shingle的集合。不失一般性,我们可以把U看做一个数值的集合。现在设定一个参数S,对于一个集合W U,定义Mins(w)为:Mins(w)=w中最小的s个元素组成的集合;|w|≥s;w;其他情况;其中“最小”是指U中元素的数值顺序。并且定义modm(w)=集合W中所有可以被m整除的元素的集合定理:让π:U→U为U统一选定的随机排列,F(A)=MINS(π(S(A))),V(A)=MODM(π(S(A))),F(B)和V(B)同样定义。那么:|MINS(F(A)∪F(B))∩F(A)∩F(B)||MINS(F(A)∪F(B))|是A和B相似度的无偏估计;|V(A)∩V(B)||V(A)∪V(B)|是A和B相似度的无偏估计;由上面的公式可知,我们可以选择一个随机排列,然后为每个文档保留一个sketch,这个sketch仅仅由F(D)和V(D)组成。仅通过这些sketch我们就可以估计任何一对文档的相似度或者包含度,而不需要原始文件。在文中的系统中,生成sketch方法如下:.移除文档的HTML格式,将所有文字转化为小写;. shingle的大小为10;.用改进后的基于robin fingerprints的40位指纹函数进行随机排列;.用求模取余的方法来选择shingle,m的值选取25。将此算法应用到整个网络的具体步骤为:.取得网络上的文档;.计算每个文档的sketch;.比较每对文档的sketch,看它们是否超过了一定的相似阈值;

.聚类相似文档。

算法很简单,但是简单的实施却不切实际。从网上抓取的大小为30,000,000HTML和文本文档集合做试验,需O(1015)次成对比较,这显然不可行。输入数据的数据量对数据结构的设计和算法都有很大的限制,数据结构中每个文档1位需4M。每个文档一个800字节的sketch需24G。每个文档微秒级计算总共需8个小时。如果算法有随机的硬盘存取或者有页面活动产生就完全不可行。在文中的算法设计中,通过一个简单的方法来处理数据量大的问题—分割,计算,合并。将数据切割成块,单独计算每一块然后再合并结果。选择块大小为m这样整个计算过程可以在内存中进行。合并结果很简单但是非常消耗时间,因为涉及到I/O操作。单独一次合并是线性级别的,但是全部的操作需要log(n/m),所以整个处理过程是0(nlog(n/m))级别的。

3　Simhash算法

Charikar的simhash算法对检测数万亿的存储级别的相似网页是非常实用的。作为指纹技术的simhash具有相似文档的指纹代写论文只存在很小位数的不同特性。在detecting near-duplicates for webcrawling一文中验证了,对于8B的网页,64位的指纹和k=3是合适的。Simhash是一种降维技术,可以将高维向量映射为位数较小的指纹。它在网页中的应用过程如下:首先将文档转化为特征码的集合,每个特征码附有一个权值。特征码的生成采用IR技术,比如分词、大小写转换、停止词去除。一个附有权值的特征码的集合构成一个高维向量,通过simhash可以将这个高维向量转化为f位的指纹,f的值很小,比如64[3]。

给出一个从文档中提取的带有权值的特征码集合,通过simhash生成f位指纹的过程如下:首先生成一个f维的向量V,每一维都初始化为0。将每个特征码哈希为f位的哈希值。这些f位的哈希值可以将V的f个元素增加或减少它所对应的权值大小的值。过程如下:如果哈希值的第i位对应的值是1,就将V的第i个元素增加它所对应的权值大小的值;如果哈希值的第i位为0,就将V的第i个元素减去它对应的权值大小的值。当所有的特征码都这样处理完,V中有的元素为正,有的为负。这些元素的符号决定了最终指纹的相应位数上的值[4~5]。

那给出一个刚抓取的网页的64位的指纹,如何快速发现有哪些指纹和它最多相差3位呢?假设有8B的64位的指纹,我们要在微秒级的时间里判断其中是否有和要查询的指纹F最多有3位不同,首先探讨两种简单但并不切合实际的方法。第一种,为所有存储的指纹建立一张排序表,给定要查询的指纹F,检索该表查找和F的海明距离最大是K的指纹F′。因要检索的次数太大而不切合实际,如果是64位的指纹,K的值为3,那么需要C(64,3)=41664次。另一个改进的方法是预先计算出和所有F′的海明距离最大是K的指纹。这种方法的预先计算量也因太大而不切实际:是表中指纹数的41664倍之多。

设想一个2d由f位随机指纹组成的排序表,其中最高的d位几乎相当于一个计数器,因为对很少有这d位重复的,另一方面,低f-d位几乎是随机的。

选择一个d′,使得|d′-d|的值很小,因为表是有序的,一次检测就能够找出所有和F′在最高的d′位相同的指纹,因为|d′-d|的值很小,所有符合要求的指纹数目也比较小,对于其中的每一个符合要求的指纹,我们可以轻易的判断出它是否和F最多有K位不同(这些不同很自然的限定在低f-d′位)。上面介绍的方法帮我们定位和F有K位不同的指纹,多有不同的位被限定在低f-d′位中。这对大部分情况来说是合适的,为了覆盖所有的情况,需要建立一小部分附加的表。

我们建t个表:T1,T2,……Tt。每一个表都有两个相关的量:一个整数pi和一个f位指纹上的排列πi。Ti是对每一个指纹应用排列πi后形成的有序表。给定一个指纹F和整数值K,我们并行的检索这些表:

第一步:找出Ti中所有排列后最高Pi位是和πi(F)的最高Pi位相同的指纹。第二步:对所有第一步中查找出的排列后的指纹,查看它是否和πi(F)最多有K位不同。举例如下:假设f=64,k=3,那么近似网页的指纹最多有3位不同。假设我们有8B=234的已有指纹,即d=34。我们有不同的设计,每种设计有不同的排列集和PI值。

20个表:把64位分成6块,分别是11,11,11,11,10和10位。共有C(6,3)=20种方法从6块中选择3块。对于每种选择,排列π使得选出的块中的位成为最高位(有几种这样的排列,我们统一的随机选择其中一种)。Pi的值就是选出的块中的位数的总和。因此Pi=31,32,或者33。平均每次检测返回最多234~31个排列后的指纹。16个表:把64位分成4块,每块有16位,共有C(4,1)=4种方法从4块中选择一块,对于每种选择,我们把这48位再分割成4块,每块有12位。共有C(4,1)=4种选择方法。对表的排列使得选出的块中的位成为最高位。Pi的值是28。平均每次检测返回最多234-28个排列后的指纹。

4　结语

Shingling算法虽然有很好的数学依据,可以给予严密准确的证明,但因计算文档的交集开销太大而难以实现,从而通过supershingle,计算文档的sketch等对原有算法进行改进。网页查重的难点就在于一方面是网页数量的巨大,另一方面是搜索引擎对用户的查询必须很快响应。Simhash可以降维,将文档用很少位数的fingerprint表示,对检测数万亿的存储级别的相似网页是非常实用的。Google采用了simhash算法来生成网页的finger-print,通过比较网页的fingerprint是否最多有k位不同来判断网页是否重复。对两个fingerprint来说,如果穷举所有的k位不同的情况,计算量和时间要求都很大,难以实现,于是google将finger-print分块,将所分块进行各种排列,只穷举了低位的排列,这样如果最多有K位不同,总存在一种排列,使得这K位出现在低f-d′位。这样就可以首先查找高d′位相同的fingerprint,然后再在这些fingerprint中查找低f-d′位存在k位不同的fin-gerprint,大大提高了效率。