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

网页去重算法I-Match算法

2018-10-13T11:30:36 | 人围观 | 关键词:网页去重算法I-Match算法--SEO培训


  网页去重I-Match算法
 

  是事先计算出一个全局的特征词典,具体到I-Match算法来说,则是根据大规模语料进行统计,对语料中出现的所有单词,按照单词的IDF值由高到低进行排序,之后去除掉一定比例IDF得分过高及得分过低的单词,保留得分处于中间段的单词作为特征词典,实验表明以这些单词作为特征,其去重效果较好。

 

  

 

  获得全局的特征词典后,对于需要去重的网页,扫描一遍即可获得在该页面中出现过的所有单词,对于这些单词,用特征词典进行过滤:保留在特征词典中出现过的单词,以此作为表达网页内容的特征;没有在特征词典中出现过的单词则直接抛弃。通过这种方式,抽取出文档对应的特征,之后利用哈希函数(I-Match算法采取SHA1作为哈希函数)对文档的所有特征词汇整体进行哈希计算,得到一个唯一的数值,以此哈希数值作为该网页的信息指纹。
 

  对网页集合里所有网页都计算出相应的信息指纹后,如何判断两个网页是否是近似重复网页?I-Match算法于此很直观,可以直接比较两个网页对应的信息指纹,如果两者相同,则被认为是近似重复网页。
 

  回顾上节所讲Shingling算法的特征抽取过程,从上述对应的I-Match算法的特征抽取过程可以看出,I-Match算法抽取出的文档特征是一个个独立的单词,单词之间的顺序没有被考虑进来,所以I-Match算法对于文档之间单词顺序的变化并不敏感,如果两个文档所包含的单词相同,但是单词顺序进行了变换,I-Match算法一定会将其算做重复内容。
 

  I-Match算法的优点在于其效率很高,因为每个文档被映射为单一的哈希值,以单一数值作为文档的表征,必然在计算速度上优于多值表征,因为可以避免复杂的集合运算。
 

  但是I-Match算法也包含不少问题,首先,对于短文本来说,很容易出现误判,也就是说两个文档本来不是近似重复网页,但是I-Match算法容易将两者判断为重复内容。之所以会如此,原因就在上文提到的特征词典,假设两个短文本内容并不相似,但是经过特征词典过滤后,只能保留很少几个单词作为文档的特征,而如果这几个单词是相同的,那么自然会将这两个文档误判为近似重复网页。其根本原因在于特征词典覆盖不足,导致文档很多信息被过多过滤,对于短文本这个问题尤其严重。
 

  另外一个更加突出的问题是,I-Match算法的稳定性不好。所谓稳定性不好,指的是对于某个文档A做了一些较小的内容变动,形成新文档B,本来应该将两者看做近似重复文档,但是I-Match算法很可能无法将其计算为我们希望的结果,即I-Match算法对于增删单词这种变化比较敏感,这是由于I-Match算法所采用的特征词典机制和SHA1哈希算法共同导致的。
 

  我们可以考虑如下的极端情形:对于某个文档A,我们向其中加入一个新的单词w(即w没有在A中出现过),形成文档B。通过I-Match算法的特征词典对两个文档进行特征过滤,因为两者的差别只有这个新加入的单词w,所以如果单词w不在特征词典中,那么文档A和文档B的对应特征集合相同,所以哈希后的信息指纹也一定相同,I-Match会认为两个文档是近似重复文档,这是我们想要的结果;但是,如果单词w出现在特征词典中,那么文档B的特征集合会比文档A多一个特征,即单词w,而SHA1哈希算法对于这种差异很敏感,会将两个文档映射成两个不同的信息指纹,即出现了稳定性不佳的问题。很明显,这个问题是由特征词典和SHA1哈希算法共同决定的,可以看做是I-Match算法为了计算效率所付出的代价。
 

  为了解决原始I-Match算法存在的稳定性不佳问题,Kolcz等人提出了改进算法(参考图10-8)。其基本出发点也很直观:原始I-Match算法对于文档内容改变过于敏感,原因在于其严重依赖于特征词典的选择,为了减少这种依赖性,可以考虑同时采用多个特征词典,而每个特征词典大体相近,同时又必须有微小的差异。

 

  

 

  对于某个需要判别是否重复的文档A,对应每个特征词典,生成多个信息指纹。如果向文档A增加新的单词w形成文档B,因为存在多个大致相同但有微小差异的特征词典,所以有很大可能某个特征词典不包含这个单词,所以通过这个特征词典算出的文档B的信息指纹和文档A是相同的。在判断A和B两个文档是否重复时,同时考虑多个信息指纹的情况,只要两个文档对应的众多信息指纹中有任意一个是相同的,则可以判定两者是重复文档。这样就解决了I-Match算法对增删单词过于敏感的问题。
 

  那么如何形成多个“大致相同又有微小差异”的特征词典呢?Kolcz是如此解决这个问题的:类似于原始I-Match算法,形成一个特征词典,为了和其他词典区分,可以称为主特征词典;然后根据主特征词典衍生出其他若干个辅助特征词典,为了能够达到词典内容大致相同,又能有微小差异,可以考虑从主特征词典中随机抽取很小比例的词典项,之后将其从主特征词典中抛弃,剩下的词典项构成一个辅抽取很小比例的词典项,之后将其从主特征词典中抛弃,剩下的词典项构成一个辅助特征词典,如此重复若干次就可以形成若干个辅助特征词典,这些辅助特征词典和主特征词典一起作为算法采用的多个特征词典。通过如此做法,即可保证每个词典大致内容相同,其间又有微小差异,能够达到所期望的效果。
 

  图10-8中演示了这个过程,图中包含两个从主特征词典衍生的辅助特征词典,其中一个抛弃了主特征词典的特征5和特征6,另外一个则抛弃了特征3和特征4,如此就形成了3个特征词典。对于某个文档,根据3个特征词典分别形成3个信息指纹,如果两个文档有任意一个信息指纹相同,则可以判定为重复文档。
 

  原始的I-Match算法将文档映射成唯一的信息指纹,虽然增加了计算效率,但是明显存在信息表达不足的问题,改进的I-Match算法本质上是将一个文档映射成多个信息指纹,可以认为是将文档里更多的信息进行了编码,这种做法与前述章节的SuperShingle的做法类似,SuperShingle也是将文档压缩成多个信息指纹,区别在于:SuperShingle是将信息由多到少进行进一步压缩,而改进的I-Match算法是从唯一的信息指纹将信息由少到多进行扩展。虽是殊途,毕竟同归。
 

相关内容推荐:

Top