XML地图 黑帽SEO培训为广大SEO爱好者提供免费SEO教程,致力于SEO优化、SEO服务
首页 > SEO教程 » 网页去重算法Shingling算法

网页去重算法Shingling算法

2018-10-13T11:26:53 | 人围观 | 关键词:网页去重算法Shingling算法--SEO培训


  网页去重Shingling算法
 

  Shingling算法可以被视为由两个大的步骤组成:第1步从文档中抽取能够代表文档内容的特征,第2步则根据两个文档对应特征集合的重叠程度来判断是否近似重复。
 

  之所以被称为Shingling算法,是因为该方法以Shingles作为文档的特征。所谓Shingles,即将文档中出现的连续单词序列作为一个整体,为了方便后续处理,对这个单词片段进行哈希计算,形成一个数值,每个单词片段对应的哈希值称为一个Shingle,而文档的特征集合就是由多个Shingle构成的。
 

  图10-4是Shingling算法如何将一篇文本文档转换为特征集合的示意图,可以假想有一个固定大小的移动窗口从文档第1个单词(单字)开始依次移动,每次向后移动一个单词(单字),直到文本末尾。图10-4中是以3个汉字作为移动窗口的大小,所以第1个长度为3的汉字串是“新浪发”,对这个汉字串进行哈希计算(Shingling算法在此处采用Rabin FingerPrint算法),即得到一个shingle,然后窗口向后移动一个汉字,形成第2个汉字串“浪发布”,同样对汉字串进行哈希计算,得到第2个shingle,依此类推,窗口不断后移,直到末尾的汉字串“户破亿”为止,这样所有的shingle组成的集合就是文档对应的特征集合。

 

  

 

  如果每个文档都通过如上方式转换为特征集合,如何计算两个文档是否是近似重复网页?Shingling算法考察两个特征集合的重叠程度,重叠程度越高,则越可能是近似重复网页。具体而言,采用了Jaccard相似性来计算这个重叠程度。
 

  图10-5是Jaccard相似性计算的示意图,这是一种计算集合相似性的经典方法,对于两个集合A和B来说,两者的重叠部分由C来表示。图中集合A包含4个元素,集合B包含5个元素,而两者相同的元素有2个,即集合C的大小为2。Jaccard计算两个集合相同的元素占总元素个数的比例,因为图10-5中集合A和B共有7个不同元素,相同元素个数为2,所以集合A和集合B的相似性即为2/7。

 

  
 

  Shingling算法通过以上两个步骤即可计算哪些网页是近似重复网页,但是这种方法在实际运行时,计算效率并不高,如果网页数量大,运行时间会过长,并不实用。原因在于把一个文档转换为以shingles表示的特征集合形式后,这个文档对应的特征集合仍然太大。同时对于不同长度的文档来说,转换后的特征集合大小各异。而这两点对于高效计算来说都是不利因素。为了加快计算速度,能否将文档的特征集合变为固定长度,同时使得这个长度远远小于原始的特征集合?
 

  Fetterly等人提出了针对原始Shingling算法改进的算法,其基本思想即如上所述,对于不同的网页,将其转换为固定大小的特征集合,而且这个特征集合的大小要远小于原始Shingling转换后特征集合的大小,以此手段来大大提升运算效率。
 

  图10-6即为这个改进思路的示意图。前面若干计算过程与原始Shingling算法是一致的,即首先将一个文档转换为由shingles构成的特征集合。为了能够将文档是一致的,即首先将一个文档转换为由shingles构成的特征集合。为了能够将文档特征映射为固定大小,引入m个不同的哈希函数,形成哈希函数簇。对于某个特定的哈希函数F,对每个shingle都计算出一个对应的哈希数值,取其中最小的那个哈希数值作为代表。这样m个哈希函数就获得了m个哈希数值,如此就把文档的特征集合转换为固定大小m,同时这个数值也比很多由shingles构成的特征集合小很多。通过如上方式,即可把文档对应的特征集合映射为一个固定大小,而且长度比原始方法小很多的数值向量,以加快后续相似度计算的速度。

 

  

 

  图10-6中为了方便说明问题,哈希函数簇只包含了两个哈希函数,而实际使用的时候往往会使用84个不同的哈希函数,即将一个文档映射成为由84个数值构成的数值向量。为了进一步加快计算速度,可以将84个数值进一步压缩:以14个连续数值作为一块,将84个数值分为6块,利用另外一个哈希函数对每一块的14个数值进行哈希计算,进一步将文档特征转换为6个哈希数值,如果任意两个文档有两个以上的哈希数值是相同的,即可认为是近似重复文档,这个技巧被称为SuperShingle。
 

  至于计算文档集合的Jaccard相似性,一般会采用Union-Find算法。Union-Find算法是经典的计算等价类的高效算法,参考文献众多,此处即不赘述其细节,重点仍然放在去重算法本身。
 

  经过如上诸般优化措施,改进的Shingling算法计算效率已非常高。实验表明,计算一亿五千万个网页,该方法可以在3小时内计算完毕,而原始的Shingling算法即使是处理三千万网页,也需10天才可完成,应该说速度的提升是非常显著的。
 

相关内容推荐:

Top