Shingling算法

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

该算法把文档看做文字组成的序列,首先把它词法分析为标示(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))级别的。