I-Match算法

2019-12-03 14:56:46  浏览:168  作者:老王

  最初的I-Match算法是由Abdm等人于2002年提出的,其基本流程也遵循本章第一节所述的通用去重算法框架。

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

I-Match算法

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

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

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

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

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

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

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

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

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

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

I-Match算法

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

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

评论区

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

【随机新闻】

返回顶部