错误博客( cuowu.com )发布于 2019-06-10 19:13:18

信息检索重复检测

信息检索重复检测教程。

重复和近似重复(near-duplicate)的文档会在很多情况下出现。在办公室中,对文档进行备份、对文档创建新的版本是很常见的行为,对这些行为进行跟踪是信息管理中的重要内容。然而,在互联网上,情况会更加极端。除了一般的重复来源,抄袭(plagiarism)和垃圾(spam)是很普遍的,还有使用多个URL地址指向同一网页以及镜像站点(mirror site),都会使爬虫程序产生大量的重复页面。研究表明,在一个大型的信息采集系统中,30%的网页是和另外70%的网页完全重复或近似重复的(如Fetterly et al.,2003)。

通常,非常相似的文档内容不能或者只能给用户提供少量的新信息,但在信息采集、索引和搜索过程中却消耗了大量的资源。为了解决这个问题,学者们提出了一些用于重复文档检测的算法,这样可以在索引和排序过程中将重复的文档删除,或者将重复的文档看作是一组文档。

对完全重复的文档的检测是相对简单的任务,可以使用检验和(checksumming)技术。检验和是根据文档内容计算的一个数值。最直接的检验和是文档文件中各字节的和。例如,对于一个含有文本“Tropical fish”的文件,检验和可以按如下的方式计算(以十六进制表示):

检验和技术

含有相同文本的任意文档会含有相同的检验和。当然,任意的文档如果恰好具有相同的检验和,也将被认为是重复的文档。例如,文件中含有相同的字符但顺序不同,会具有相同的检验和。一些复杂的函数,如循环冗余校验(cyclic redundancy check,CRC)中,考虑到了字节出现的位置。

对于近似重复文档的检测比较困难,甚至如何定义近似重复也是不容易的。例如,对于网页来说,可能含有相同的文档内容,但广告、日期、格式不同。其他的页面可能由于修订或者更新在内容上略有不同。通常,使用两个文档之间相似度的域值来定义近似重复的文档。例如,如果文档D1和文档D2中有90%的词是重复的,那么它们就是近似重复的文档。

对于近似重复的检测,有两种应用场合。一个是在搜索场景(search scenario)下,这时它的目标是找到与给定文档D近似重复的文档。类似于所有的搜索问题,涉及查询文档和所有其他文档之间的比较。对于含有N个文档的集合,这样的比较需要的开销为O(N)。另外一个场景是发现(discovery),涉及在集合中找到所有近似重复的文档对。这个过程需要的开销为O(N2)。尽管在信息检索技术中,在搜索场景中用基于词表达的文档来进行相似度的计算对于近似重复的文档检测是有效的。但在发现的场景中,相似度的计算需要一些新的技术,得出文档的简洁表示形式。这些简洁的表示形式也就是指纹(fingerprint)。

生成指纹的过程如下:

1)首先对文档进行分词处理。删除那些不是词的内容,如标点、HTML标签和空格。

2)对于给定的n,将这些词组合成n-gram。尽管在一些技术中使用非重叠的词序列,但n-gram通常是相互重叠的词序列(见4.3.5节)。

3)其中的一些n-gram被选择用于表示该文档。

4)对这些被选择的n-gram进行散列,以提高检索的效率,并进一步减少文档表示的大小。

5)将散列值进行存储,通常存储在倒排索引中。

很多的指纹算法都使用该方法实现,各算法之间主要的区别在于如何对n-gram的子集进行选择。对于近似重复文档的检测,随机选择固定数量的n-gram并不能改善性能。考虑两个近似相同的文档D1和D2。通过随机地从文档D1中选择n-gram而生成的指纹,与随机地从文档D2中选择n-gram而生成的指纹不可能有很多的重叠。更加有效的方法是使用事先制订的字符组合,选择以这些字符开始的n-gram。另外一个常见的方法称作 0 mod p,选择那些散列值模p为0的n-gram,这里p为参数。

图3-14中显示了使用重叠的3-gram生成指纹的过程,假定了散列值,以及 0 mod p 的选择方法,其中 p=4。在选择过程之后,文档(在这里是句子)通过一些n-gram的指纹来表示,“fish include fish”、“found in tropical”、“the world including”以及“including both fresh water”。

指纹生成过程实例

在大规模的应用中,例如在网络上找到近似重复的文档,n-gram通常有5~10个词,而散列值为64位。

通过对表示文本的指纹进行比较,可以找出近似重复的文档。近似重复的文档对是通过两个文档相同的指纹数量或者相同指纹占总指纹数量的比例来进行定义的。然而,指纹并不能代表所有的文档信息,这会导致在近似重复的检测中出现错误。恰当的选择方法可以减少这些错误,但不能消除这些错误。正如上面提到的,评价结果显示出,与指纹方法相比,基于词表的相似度计算如余弦相似度计算,通常更加有效。但这些方法的主要问题是效率不高。

最新开发的一种称为simhash(Charikar,2002)的指纹技术,吸取了基于词的相似度计算的优点,以及基于散列的指纹技术的高效性。该方法中散列函数具有特殊的性质,即相似的文档具有相似的散列值。更准确地说,通过余弦相似度计算的两个页面的相似度,正比于simhash方法生成的指纹中相同的位数。

simhash方法中,指纹计算的过程如下:

1)利用具有权值的特征集合来表示文档。简单的情况下,假定特征都是由词组成的,词的权值由它们出现的频率来确定。其他的权值计算方案在第7章中讨论。

2)对每一个词,生成b位的散列值(指纹的期望长度)。每个词都具有各自不同的散列值。

3)在b维的向量V中,分别对每维向量进行计算。如果词相应位的散列值为1,则进行对其特征权值的加法运算,否则进行减法运算,通过这种方式对向量进行更新。

4)当所有的词都处理完毕之后,如果向量V中第i维是正数,则将b位的指纹中第i位设置为1,否则为0。

图3-15给出了一个8位指纹的处理过程。去除常用词(停用词)作为文本处理的一部分。实际中,b会取很大的值。Henzinger(2006)中叙述了一个基于大规模网页的评价方法,他使用的指纹有384位。如果一个网页和另外一个网页的simhash指纹中有多于372位是相同的,那么这两个网页就是近似重复的。研究表明,simhash指纹方法比n-gram的指纹方法有更好的效果。


2020年错误博客亲测项目系列

错误教程( cuowu.com )专注网推培训、SEO培训和网赚培训,微信/电话:13722793092

关注微信公众号:第一时间获得错误博客最新教程,让我们一起成长!

公众号二维码