深圳SEO公司
欢迎您光临浏览!

搜索引擎的分析系统之网页查重

在日常上网时一般很少会留意到相同相似网页,一些偶然的机会也能看到一些相对重要的网页会被各大网站转载(比如在深圳SEO站上转载一篇文章在A5),或者在浏览BBS时会看到各种各样的转帖。对于网民来说,这种重复是有利的.健于大多数人看到重要的信息。然而对于搜家引擎来说,重复网页的存在意味着这些网页至少被多处理一次。更槽糕的是,在接下来的索引制作中可能会在索引库中索引两份相同的网页。
当有用户查询时.在有限的直询结果页中(一个查询结果页显示20条网页链接)就会出现重复的网页链接。因此无论从系统效率,还是从检索质量来说。深圳SEO在这里告诉大家重复网页都是有害的。
网页查重技术发展历史
网页查重技术起源于复制检测技术,复制检测即判断一个文件的内容是否抄袭、剽窃或者复制于另外一个或者多个文件。
1993年,Arizona大学的Manber推出一个sif工具,用于在大规模文件系统中寻找内容相似的文件。1995年,Stanford大学的Brin和Garcia-Molina等人在“数宇图书馆”工程中首次提出了文本复制检测机制COPS(Copy Protection System )系统与相应算法(Sergey Brin et al 1995)。之后这种检侧重复技术被应用到搜索引擎中.基本的核心技术即比较相似。和简单的文档不同,对于网负来说,这种相似包含了特别丰富的含义.网页具有内容和格式,因此在内容和格式上的相同相似构成了如下4种网页相似的类型(如果把相同看做相似的一种特殊情况),下面深圳SEO为大家总结了4点核心技术。
1.两个网页的内容和格式上完全相同(full-layoutduplicates)
2.两个网页的内容完全相同,但格式不同(full-contentduplicates)
3.两个网页有部分,耍的内容相同并且格式相同(partial-layout duplicates )
4.两个网页有部分且要的内容相同.但格式不同(partial-content duplicates)
如图4-12所示,搜索引擎在相似问题上按照内容和格式的组合共计4种不同的形式。对大规模网页来说,网页查重只需要找到内容相同成相似的网页,而忽视格式上的异同,因此在网页查重的过程中,图4-12所示的4种相似情况都属于网页查重的目标。

采用网页签名的方法很容易检测网页完全一致.如果两个网页签名值相同,则为相同网页,这种方法在第三章中关于网页URL不重复抓取的策略中已介绍过。因此本节主要关注的是检测网页相似的情况。

检测大规模的相似网页需要考虑准确性和效率,有关文献深圳SEO推荐:[Abdurchowdhury et al 2002] ,(Broder 1997)分别提出了两种经典的处理大规模网页相似检测的方法,下一节我们将可以在深圳SEO站上看到这一有趣的方法。
网页查重
网页查重实现方法
由于不考虑格式的异同,网页查重首先需要提取结构化网页的正文和标题,将重杂的网页转化为具有标题和正文的文档,因此下面称网页查重为“文档查重”。

日常生活中判断两个相似事物一般采用比对特征的方法,特征是那些有代表性、不易变化、能够反应主体本质的信息。文档查重的第1步就是特征抽取,下面深圳SEO为大家介绍两种特征抽取的方法。

第1种特征抽取方法着眼于尽可的抽取一个特征,这样比较两个文档是否相似只要比较一次即可。文献(Abdur chowdhury etal 2002)首先提出了称为“I-Match”的算法,这个算法基于一个假设,即一篇文档中特别高频和特别低频的词汇往往不能反映这篇文档的本质。因此通过将文档中去掉高频和低频词汇后的词汇通过排序得到一个字符串,使用签名算法获得该字符串的签名。如果有其他文档和这个签名位相同,则判定为相似。
高频词和低频词
如图4-13所示的例子中,通过去掉高频和低频词汇(词频的统计工作由索引系统提供,在第五章中会提到词频的统计方法和技巧),两个文档趋于一致,通过排序则得到完全相同的词汇列表。通过这种计算,两篇文档的相似性就转化为一个词汇列表是否相同的问题。

第2种特征抽取方法是抽取多个特征词汇,通过比较两个特征集合的相似度实现文档查重。抽取多个特征的方法很多。这里介绍其中的一个经典算法。称为“Shingle算法”。Shingle在英文中表示相互覆盖的瓦片。接下来通过上面的例子来说明Shingle算法为什么命名为“Shingle”。例中使用每5个汉字为一个Shingle的方法,如图4-14所示。
特征词汇抽取
如图所示,每5个汉字组成的Shingle怡如其名,好似相互覆盖的瓦片一样。由于把一个文档转化为一组字符串集合(每个元素为一个Shingle),因此判断两个文档的相似性就转化为字符串集台的相似性。最后介绍一个关于Shingle算法的简单结论,对于长度L的文档,每隔N个汉字取一个Shingle,这样一共取到L- N +1 个Shingle,可见N的取值对效率和效果的影响都很大.很显然N最小取2,最大取L,在特征抽取完毕后,就需要进行特征比对,因此网页查,的第2步就是相似度计算和评价。

I-Match算法抽取的特征只有一个,因此只需要为文档计算一个签名值,如果两个文档的签名值相同,则文档相似。大规模文档做查重只需要维护一个哈希表即可。每来一个文档直找一次哈希表.如果哈希表的槽位(bucket)被置位,说明已经存在相似文档。
Shingle算法抽取的特征有多个,因此处理起来稍微麻烦一些,比较的方法是记录完全一致的Shingle个数。然后除以两个文档的Shingle总个数减去一致的Shingle个数,这种方法计算出的数值称为”Jaccard系数”,它可以用来判断集合的相似度。Jaccard系数的计算方法为集合的交集除以集合的并集。即若令集合A与集合B的jaccard系数为J,则有:
Jaccafd系数 计算方法
在如图4-14所示的例子中,完全一致的Shingle分别是“中国足球”、“世界杯决赛”、“界杯决赛阶”和“杯决弃阶段”。其中第1个文档具有Shingle总数是30个(计算方法为正文总长度-Shingle长度+1),第2个文档Shingle总数为22个,因此两个文档的相似度(jaccard系数)为jaccard系数。在通过jaccard系数量化了相似度后,即可通过评价这个数值是否达到相似所需要的标准来判断是否相似。如果在搜索引擎中相似度达到0.2才能判断为相似,那么这个例子的相似度没有达到标准,因而不能看做是相似文档。

对比一下这两种方法,I-Match算法提取特征时需要文本分词和词频比较的代价,因此提取特征比较复杂,但文档是否相似的计算简单;Shingle算法提取特征简单,但文档是否相似的计算复杂,因此各有利弊。由于Shingle算法在性能上的优异表现,因而被广泛采用。

深圳SEO在这里介绍的是最经典的两种方法.其他网页查重的方法还有很多。文献(李晓明2004)中介绍了多种网页查重的方法,有兴趣的读者可以深入阅读。网页查重的目标是消重,因此网页查重的第3步就是网页消重。
消重就不可避免遇到这样一个问题,即在相同或者相似的网页集合中保留哪一个,而消除哪些呢?从版权的角度考虑,应该尊重原创,过滤转载成者复制的网页;从网页寿命的角度考虑,过滤掉那些网站质量不高的网页,保留大型网站的网页;从容易实现的角度考虑,首先保留被爬虫抓取的网页,然后丢弃被抓取的相同或相似网页。最后一种方法最为简单实用,由于保留先被爬虫抓取的网页同时很大程度上也保证了优先保留原创网页的原则,因此被广泛采用。

综上所述,一般说来,网页查重至少需要如下三个主要步骤:
1.特征抽取
2.相似度计算,评价是否相似
3.消重
网页查重工作是分析系统不可缺少的重一环,由于去除了重复网页,所以在接下来的其他模块的处理,节约PageRank的计算代价,节省了索引在存储空间,减少了查询成本,提高了查询结果的多样化效果。

本文出自深圳SEO公司,未经允许不得转载:深圳SEO-微笑SEO服务公司 » 搜索引擎的分析系统之网页查重
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址