Shingling算法

2019-12-03 14:55:04  浏览:118  作者:老王

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

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

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

Shingling算法

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

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

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

Shingling算法

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

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

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

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

Shingling算法

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

评论区

共0条评论
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~

【随机新闻】

返回顶部