（计算机应用技术专业论文）搜索引擎中网页净化与消重技术研究.pdf

j i ，、 、 ， ， _ rt 省， ：、 重 at h e s i si nc o m p u t e ra p p f i c a t i o nt e c h n o l o g y r e s e a r c ho fw e bp a g ep u r i f i c a t i o na n dr e p l i c a s d e t e c t i o ni ns e a r c he n g i n e b yz h uf e n g f a n g s u p e r v i s o r ：a s s o c i a t e p r o f e s s o rl i uh u i l i n n o r t h e a s t e r nu n i v e r s i t y j u n e2 0 0 8 蜘(， 矗主 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢 ：也 思。 学位论文作者签名：柴风葛 e l 期：加。言7 牛 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 作者和导师同意网上交流的时间为作者获得学位后： 半年囱一年口一年半口两年口 学位论文作者签名：朱风芳 签字日期： w o 舌、，7 午 导师签名：胡乞姝 签字日期：加，彦。1 4 唯f0& o内嫡，1t 、0，v - k + 东北大学硕士学位论文摘要 搜索引擎中网页净化与消重技术研究 摘要 互联网的飞速发展导致数字化信息呈爆炸式增长。搜索引擎作为帮助人们在海量 信息中寻觅所需信息的工具，其重要性与日俱增。然而，由于网页噪音和重复网页的 存在，搜索引擎的检索结果中存在着大量的冗余信息，使得搜索引擎的服务质量降低。 因此，如何快速准确地去除网页噪音和重复网页成为一个亟待解决的问题。 本文深入研究了搜索引擎中网页净化与消重的技术。首先分析了网页噪音及网页 重复对搜索引擎的影响；然后介绍了网页噪声和网页重复的相关概念及特点，研究了 网页净化与消重的经典算法，并分析了这些算法的优点和不足。 在网页净化方面，根据同一网站的网页结构布局基本相同的特点，提出了一种新 的基于树编辑距离的网页净化算法。该算法利用树编辑距离和严格自顶向下映射原理， 以最小的代价检测网站的模板，并将该模板作为噪音信息从网页中去除。实验结果表 明，该算法在保证网页主题内容完整的同时，有效的去除了网页噪音。 在网页消重方面，针对w e b 上网页重复的现象，提出了一种新的基于信息指纹的 网页消重算法。该算法为了排除噪音的干扰，将网页净化技术融入算法中，并充分利 用网页文本的内容和结构信息来提取网页特征，然后结合信息指纹技术，实现了重复 网页的去除。实验结果表明，该算法在保证较高准确率的情况下，具有更高的召回率。 关键词：网页噪音；网页净化；网页重复；网页消重 一一 。 囊 +唾舞； 、t。l砖 气 ， i l 东北大学硕士学位论文 a b s t r a c t r e s e a r c ho fw e bp a g ep u r i f i c a t i o na n dr e p l i c a sd e t e c t i o ni n s e a r c he n g i n e a b s t r a c t t h er a p i dd e v e l o p m e n to ft h ei n t e m e tl e a d st od i g i t a li n f o r m a t i o ng r o w i n ge x p l o s i v e l y t h ei m p o r t a n c eo fs e a r c he n g i n ew h i c hi sat o o lt h a th e l p sp e o p l et of i n dt h en e c e s s a r y i n f o r m a t i o ni nt h em a s si n f o r m a t i o ni si n c r e a s i n gs t e a d i l y h o w e v e r , d u et ot h ee x i s t e n c eo f w e bp a g en o i s ea n dr e p l i c a s ，t h e r ei sal o to fr e d u n d a n ti n f o r m a t i o ni nt h er e t r i e v a lr e s u l t s ， w h i c hr e d u c et h eq u a l i t yo fs e r v i c eo fs e a r c he n g i n e t h e r e f o r e ，i ti sap r o b l e mr e q u i r i n g u r g e n ts o l u t i o nt h a th o w t or e m o v ew e bp a g en o i s ea n dr e p l i c a sq u i c k l ya n da c c u r a t e l y i nt h i st h e s i s ，w es t u d yd e e p l yo nw e bp a g ep u r i f i c a t i o na n dr e p l i c a sd e t e c t i o ni ns e a r c h e n g i n e f i r s t ，w ea n a l y z et h ee f f e c to ns e a r c he n g i n ew h i c hi sc a u s e db yw e bp a g en o i s ea n d r e p l i c a s ，a n dt h e ni n t r o d u c et h ec o n c e p t sa n df e a t u r e sr e l a t e dt ow e bp a g en o i s ea n dr e p l i c a s t h ec l a s s i c a la l g o r i t h m so fw e bp a g ep u r i f i c a t i o na n dr e p l i c a sd e t e c t i o na r es t u d i e d ，t h e a d v a n t a g e sa n ds h o r t c o m i n g so fw h i c ha r ea n a l y z e d o nt h eo n eh a n d ，an e ww e bp a g ep u r i f i c a t i o na l g o r i t h mi sp r o p o s e db a s e do nt r e ee d i t d i s t a n c ea c c o r d i n gt ot h ef e a t u r et h a tt h es t r u c t u r ea n dl a y o u to fw e bp a g ei naw e bs i t ea r e s i m i l a r t h ea l g o r i t h mu s e st r e ee d i td i s t a n c ea n ds t r i c tt o p d o w nm a p p i n gp r i n c i p l et od e t e c t s i t et e m p l a t ew h i c hc a nb er e m o v e df r o mn e ww e bp a g e sa sw e bp a g en o i s eb ys i m p l e p r o c e d u r e o u re x p e r i m e n t ss h o wt h a tt h ea l g o r i t h mc a l le n s u r et h ei n t e g r i t yo fw e bp a g e c o n t e n t s a tt h es a m et i m e ，w e bp a g en o i s ec a nb er e m o v e de f f e c t i v e l y o nt h eo t h e rh a n d ，an e w w e bp a g er e p l i c a sd e t e c t i o na l g o r i t h mi sp r o p o s e db a s e do n f i n g e r p r i n tt or e m o v ew e bp a g er e p l i c a s i no r d e rt oe l i m i n a t et h ei n t e r f e r e n c eo f w e bp a g e n o i s e ，w e bp a g ep u r i f i c a t i o ni sm e r g e di n t ot h ea l g o r i t h m t h ea l g o r i t h mm a k e sf u l lu s eo f w e bp a g ec o n t e n ta n ds t r u c t u r ef e a t u r e sa n dc o m b i n e sw i t hf i n g e r p r i n tt e c h n o l o g yt oa c h i e v e t h er e m o v a lo fd u p l i c a t ep a g e s o u re x p e r i m e n t ss h o wt h a tt h ea l g o r i t h mh a sh i g h e rr e c a l l r a t ei nt h ec o n d i t i o nt h a th i g ha c c u r a c yr a t ei se n s u r e d k e y w o r d s ：w e bp a g en o i s e ；w e bp a g ep u r i f i c a t i o n ；w e bp a g er e p l i c a s ；r e p l i c a sd e t e c t i o n i i i 二 ， f ， 冀， 东北大学硕士学位论文目录 目录 摘要i i a b s t r a c t i i i 第一章绪论1 1 1 课题背景1 1 2 课题提出及意义。2 1 3 本文的研究内容3 1 4 本文的组织结构4 第二章相关工作5 2 1 网页净化与消重5 2 1 1 网页噪音。5 2 1 2 网页重复。6 2 2 网页净化技术7 2 2 1 单一页面网页净化8 2 2 2 同一模板网页净化1 0 2 3 网页消重技术1 2 2 3 1 完全重复网页消重1 2 2 3 2 近似重复网页消重1 4 2 4 本章小结1 6 第三章基于树编辑距离的网页净化1 7 3 1 树编辑距离1 7 3 2 网页净化方法2 1 3 2 1 网页预处理2 2 3 2 2 标签树构建2 3 3 2 3 模板生成与去除2 5 3 3 实验3 0 3 3 1 评测标准3 0 3 3 2 实验设置31 3 3 3 实验结果与分析3 1 3 4 本章小结3 6 第四章基于信息指纹的网页消重3 7 4 1 网页消重方法3 7 一一 东北大学硕士学位论文目录 4 1 1 网页特征抽取3 8 4 1 2 信息指纹生成4 1 4 1 3 重复网页判定4 4 4 2 实验4 7 4 2 1 评测标准4 7 4 2 2 实验设置4 8 4 2 3 实验结果与分析4 9 4 3 本章小结5 2 第五章总结与展望5 3 5 1 总结5 3 5 2 展望5 4 参考文献5 5 致谢。5 9 一v 一 、鼍 ； - 墨 ， ； - ， 东北大学硕士学位论文第一章绪论 1 1 课题背景 第一章绪论 在互联网发展初期，网站相对较少，查找信息比较容易。然而随着信息科学的进 步和互联网的迅猛发展，w e b 信息呈爆炸性的增长。根据中国互联网信息中心最新的 统计，互联网基础资源增长迅猛，年增长率均超过3 8 ，尤其是域名、网站和网页数 量，年增长率均超过了6 0 t 。这一方面使w e b 成为一个巨大的信息仓库，另一方面 使得极小部分的有用信息淹没在无用信息中，对于用户而言，想找到所需的资料如同 大海捞针。如何从海量的数据中找到人们真正需要的数据变得越来越困难和富有挑战 性，人们迫切需要有效的网络信息导航，来帮助他们在网络信息的海洋里，准确、快 捷地查找所需的信息，于是搜索引擎应运而生。 搜索引擎是将w e b 上的特定信息与用户需求连接起来的桥梁，它对网上分散的信 息进行搜集、索引并存储在数据库内，然后根据用户的检索要求在一个可以接受的时 间内返回一个和该用户查询匹配的网页信息列表给用户。搜索引擎不同于传统的门户 网站，因为它涵盖的信息量更大，并且很容易根据用户需求来返回结果，更能贴近用 户的需求。搜索引擎的出现在很大程度上解决了信息和知识获取的困难，节约了用户 的处理时间，受到了互联网使用者的欢迎。人们的工作、学习、生活、娱乐越来越离 不开搜索引擎，搜索引擎在互联网应用中己占有举足轻重的地位。搜索引擎渐渐成为 新一代的“门户网站。 然而互联网规模的几何级数增长推动搜索引擎的普及和应用的同时，由于其缺乏 规范性，使搜索引擎面向的对象为海量数据，导致搜索引擎搜索的内容比较繁杂，存 在一些亟待解决的问题，主要表现在以下几个方面。 ( 1 ) 重复信息多、死链接多 返回给用户的信息存在大量的重复，目前的搜索引擎没有很好的解决这个问题。 另外在检索的结果中存在大量的死链接，不能定位到检索的页面。 ( 2 ) 覆盖面窄，检索结果质量差，检索的召回率和准确率低 返回的检索结果含有大量无关和冗余信息，需要用户自己逐个鉴别和挑选，费力 耗时，浪费大量的上网时间和费用。这就是有用信息匮乏，方面网络信息过载和泛 一1 一 东北大学硕士学位论文第一章绪论 滥，另一方面用户却难以得到真正需要的信息，出现了“假性饥饿现象。 ( 3 ) 缺乏为用户提供的检索导航信息 w w w 是一个结构复杂的巨大的信息网络，用户很容易迷失其中而无法顺利、快 速地找到自己所需的目标。目前虽然有专门进行网络导航的搜索引擎，但是针对个人 用户的导航还远远不够，有待于进一步深入研究个性化的检索导航技术。 ( 4 ) 为用户定制服务的能力差 用户的需求是多种多样的，每个用户的需求各有不同。如果允许用户定制自己的 特殊需求，在用户提交的定制服务基础上自动提供所需要的信息将在最大程度上满足 用户的需求。然而目前绝大多数搜索引擎不提供这样的服务。 如何提高搜索引擎检索效果，成为是人们不断研究的课题。因为对一个成功的搜 索引擎来说，首先必须具有相当高的检索效率和相关度，w e b 上没有用户会去使用一 个响应迟缓和检索结果存在大量冗余信息的检索系统。目前有几个途径来提高搜索引 擎的检索效率，例如网页净化与消重、网页分类、自动文摘、网页聚类等【2 】，而网页 的净化与消重是本论文研究的重点。 1 2 课题提出及意义 w e b 上的网页通常包含两部分的内容：一部分内容体现的是网页主题信息；另一 部分则是与主题内容无关的导航条、广告信息、版权信息以及调查问卷等内容，称其 为“噪音内容”。它们分布于网页四周，甚至附着在正文旁边，有时也夹杂在主题内 容中间，通常是以链接导航文字( a n c h o r t e x t ) 的形式出现的。噪音内容一般无内容 相关性，同时它们链接的网页常常也无内容相关性。噪音内容的存在不仅给w e b 上基 于网页内容的应用系统带来困难，如网页分类系统、聚类系统、网页信息抽取系统等， 也给基于网页超链指向的应用系统带来困难，如网页评级系统。因此，如何快速准确 地识别并清除网页内的噪音是提高w c b 应用程序处理结果准确性的一项关键技术，我 们将该项技术称之为网页净化。网页净化【3 】( n o i s er e d u c t i o n ) 是分析网页结构，识别 和清除网页内的噪音内容，如广告、版权信息，并提取网页的主题以及和主题相关的 内容。目的是排除网页中噪音内容的干扰，除去影响搜索引擎获取网页主题的噪音内 容，得到真正的主题内容。人工去除噪音块的代价很大，而且容易出错。如何采用自 动方式去除网页噪音成为研究的热点。 与生俱来的数字化和网络化给网页的复制以及转载和修改再发表带来了便利。受 一2 东北大学硕士学位论文第一章绪论 用户兴趣的驱动，在网络上进行信息转载相当容易。网络信息在传播中，人们通过复 制方式进行信息共享。越是经典的文章和有价值的新闻，越会有更多的人关注，所以 转载的可能性更大，致使大量的重复网页充斥着互联网，网络上重复信息的比例达到 了2 0 3 0 。这些网页有的是一字不差的完全重复，有的只是其中一部分重复。重复 网页的出现，给网民带来了好处。重要网页可以有更多的机会被人们看到，并且在一 些网络速度慢的地区，人们可以从多个镜像中选择一个距离自己较近的网页进行访问。 然而重复网页的存在，一方面对于各类资源是一种浪费，另一方面大量减少了信息的 有效性和可用性。这对于网络信息资源的发展有一定的负面影响。对于搜索引擎来说， 保存相同或相似内容的网页，会影响检索的准确度，并造成存储资源的浪费和检索时 的低效率。大量的“无效的 结果常常冲掉用户真正感兴趣的结果，加重了用户浏览 的负担，浪费了时间和精力，同时也浪费了网络资源和检索资源。因此，有效地去除 冗余网页是提高搜索引擎检索质量的有效途径。 网页消重( r e p l i c a so rn e a r - r e p l i c a sd e t e c t i o n ) 是指去除所搜集网页集合中与主题 内容重复的网页。目的是对内容重复的网页进行识别，处理和合并，以节省网页数据 库的存储空间和在网页数据库上进行操作的时间的过程。重复网页的消除，对于面向 网络的检索系统而言，无疑会提高信息的深加工效率。因此，获取网页的核心文本并 进行网页消重是一项具有实际意义的工作，也是本文研究工作的所在。 对于海量信息，若单单依靠人工进行网页消重，不仅耗费宝贵的人力资源，而且 时效性也不能满足实际需要。如何自动地在网页集中检测出重复的内容亦成为我们关 注的焦点。如何快速准确地去除网页重复以提高信息检索领域性能成为一个亟待解决 的问题，也成为信息检索领域一个具有挑战性的研究课题。 1 3 本文的研究内容 大量网页噪音和重复网页的存在严重影响了搜索引擎检索的效率和查询结果的准 确率。本文以提高搜索引擎的服务质量为目标，深入研究网页净化与消重的关键技术。 首先深入理解网页净化与消重的相关概念，分析网页噪音和网页重复的特点；其次研究 网页净化与消重的关键技术，剖析网页净化与消重经典算法的优缺点；然后在总结现有 的网页净化与消重算法的基础上，提出新的网页净化与消重算法，并通过大量的实验验 证本文提出的净化和消重算法的有效性。最后总结本文所做的研究工作并对进一步的工 作进行展望。 一3 一 东北大学硕士学位论文第一章绪论 1 4 本文的组织结构 本文主要的内容安排如下： 第一章，阐述了课题背景及意义，论述了目前搜索引擎中存在的问题，分析了网 页噪音与网页重复对搜索引擎的影响，并介绍了课题所要解决的主要问题及论文的结 构安排； 第二章，介绍了网页噪音和网页重复的相关概念及其特点，论述了网页净化与消 重的关键技术，介绍了经典的网页净化与消重算法，并分析了这些算法的优点与不足； 第三章，根据一般网站的网页结构布局基本相同的特点及树编辑距离的原理，提 出一种新的网页净化算法，并通过实验对算法进行了性能评测； 第四章，深入分析已有的网页消重算法基础上，提出一种新的基于信息指纹网页 消重算法。该算法同时考虑了网页文本的内容、结构信息，并结合网页净化和信息指 文技术，实现重复网页去除，并通过实验对算法进行了性能评测； 第五章，总结了全文并提出了对进一步研究工作的设想。 一4 一 东北大学硕士学位论文第二章相关工作 2 1 网页净化与消重 第二章相关工作 大多数w e b 网页都采用h t m l 书写而成，h t m l 是一种标识语言，其中定义了一 套标签来刻画网页显示时的页面布局。标签的作用是提供了有关文档结构的信息( 如标 题、头部及段落等) 和格式( 如粗体和斜体等) 。另外，由于h t m l 本身不具备自描述 的特性，页面在书写时，负责显示和承担主题描述的信息混在一起，并且设计者可随意 把各类内容加入到页面中，因此页面中充满与主题无关的噪音是常见的现象。 2 1 1 网页噪音 在一个网页中常见噪音信息包括这样几类【4 】：( 1 ) 导航条，为了维护网页间的链接 关系，方便浏览者对网站进行浏览而设置的链接。( 2 ) 修饰类，为了美化页面而采用的 背景、修饰图片、动画等。( 3 ) 交互类，为了收集用户提交信息或提供站内搜索服务的 表单等。( 4 ) 其它类，网页中声明的版权信息、创建时间、作者等描述性信息。它们通 常是以链接导航文字( a n c h o r t e x t ) 的形式出现的。与传统的文本文档相比，许多网页 在内容上比较随意，不仅文字不讲究规范，不完整，还可能包含许多和主要内容无关的 信息。因此，网页噪音根据其划分粒度的不同，可以从整个w e b 和单一页面本身来加 以定义。根据噪音内容的粒度大小，w e b 上的噪音内容分为两类【5 - 6 。 ( 1 ) 局部噪音( l o c a ln o i s e ) ：指w e b 网页内与网页主题内容无关的噪音内容，比 如：广告、导航条以及版权声明等内容。局部噪音影响对网页主体内容的判断，局部噪 音使得应用程序很难确切得到网页的主题内容，因此它严重的影响了基于网页内容的应 用程序。同时，局部噪音很多情况下是伴随着超链接出现，因此，局部噪音也对基于网 页间链接关系的应用程序造成影响。 ( 2 ) 全局噪音( g l o b a ln o i s e ) ：指w e b 上具有较大粒度的噪音内容，它通常包含 镜像网站、重复网页以及近似网页。全局噪音内容不仅影响了w e b 上信息检索系统( 比 如搜索引擎) 的网页搜集、索引和检索结果排序的质量，也使得w e b 信息存储系统浪 费大量的磁盘空间去保存重复的网页。 噪音内容一般无内容相关性，它们链接的网页常常也无内容相关性。人工去除噪音 块的代价很大，而且容易出错。如何采用自动方式去除网页噪音成为研究的热点。 一5 一 东北大学硕士学位论文第二章相关工作 2 1 2 网页重复 在信息检索中，已经定义了字符串之间和文献之间的语法相似度的概念。相似度可 以通过距离函数( d i s t a n c ef u n c t i o n ) 来测量。然而“重复和文献的相似度绝不能混 为一谈。长久以来，对于“重复的定义都非常模糊，没有一个清晰的定义。c o n r a d 对于“重复 的定义是【7 】：如果2 篇文章之间有超过8 0 的用词相同，而且长度相差不 超过正负2 0 ，则这2 篇文章就是重复的。w i l l i a mp u g h 对于“重复的定义就要简单 的多：如果两篇文档之间有超过r 个特征相同，则它们就是相似的。本文首先给出完全 相同的网页的定义。 同样大小的网页a 和扔是相似的( p 。= p 2 ) ，满足- f n 条件： ( 1 ) 相同网页内容：c o n t e n t ( p 1 ) = c o n t e n t ( p 2 ) ，即对应的网页的内容是相同的； ( 2 ) 相同的链接结构：存在一一映射m ：p 。一p 2 对于p 中任何一个超文本链接，l ， 都存在仍中的一个超文本连接乞，使得乞= m ( ) 。 需要说明的是，我们定义两个超文本链接是相同的，当且仅当这两个超文本链接在 各自文本中所在的位置是相同的，它们的连接信息是相同的，并且它们所指向的页面是 相同的。而许多对于近似重复网页的应用并不关心严格的相同性。放宽上述对于网页内 容和网页链接结构两方面定义来得到近似重复网页的定义。 定义s t ( p ，p j ) 为一个判定网页对( 办，p ，) 相似程度的测试，r 0 s t ( p l ，p j ) l 。当 s t ( p l ，p j ) = 1 ，网页b 和p ，是相同的。给定一个相似程度测试s t ( p i ，p ，) 和阈值t ，基于 这个测试我们可以说这两个页面只，p ，是相似的，如果s t ( p ，p ，) t 。记作b p j 。 主题内容基本相同但可能有额外的编辑信息等的网页称作转载网页，又称近似镜像 网页) ，而网页p 的近似镜像度c ( 一是指整个网络中网页p 的近似镜像个数，在一定程 度上反映了网页的重要程度。并且从近似重复网页定义可知，就消除主题内容重复的网 页而言，我们完全可以把完全重复网页看作转载网页的特例来处理。在本文中，我们所 指的重复网页是因各个网站转载而形成的重复网页，而对于在原文的基础上进行大量的 修改的情况，我们认为是不同的。与自然语言文本相比，网页有其自己的特点【8 】。 ( 1 ) 转载率非常高。这要比自然语言文本的转载率高很多。这主要是因为网页往 往会有用户在网络上轻易的拷贝，粘贴，通过这种方式，实现信息的传播和共享。而对 于一些新闻类的网页，例如新华网的内容，各大网站的编辑都会转载到自己的网站上， 以提高点击率以及网站的时新性。这种转载，我们经过观察，往往都会转载十次以上。 一6 一 东北大学硕士学位论文 第二章相关工作 ( 2 ) 时间的局部性。这里是因为，往往一件事情，尤其是新闻事件一般都会在一 段时间内发生，有较强的时间性。因为如果一篇文章出现太晚，就不会有别人看了，所 以在计算网页去重的时候，只需将一段时间内的网页进行比较即可，而不需要与所有的 网页进行比较，而自然语言文本的转载就不会有这样的时间局部性。 ( 3 ) 需要检测的网页数量非常多。也就是我们开始并不知道有哪些网页是重复的， 所以我们要处理的是新出现的所有网页，那么我们需要对这些所有的网页都进行比较去 重，而这些网页数量是非常庞大的，如果仍然采用类似于自然语言文本的某些消重方法， 进行两两比较，那么时间上是不允许的。 ( 4 ) 大量的噪音信息干扰。这又不同于自然语言文本的转载，因为自然语言文本 在转载时，一般只会有少量的修改，所以干扰不大。而网页的转载，由于只转载了网页 正文内容，而网页的版权信息，网页的导航信息，以及相关链接信息等都没有进行转载， 这样网页之间虽然经过了转载，但是由于网站之间的差别，它们的外部表现形式可能会 差别非常大。 前三点内容，主要从效率的要求来说明网页去重的难度。因为网页转载同时具有大 规模性和突然出现性，所以要想发现互联网上的转载信息，效率是第一位的。而第四点 内容，则说明了网页消重问题的复杂性，如何剔除掉网页的噪音部分，成了提高网消去 重准确率的关键。并且对于海量信息，若单单依靠人工进行网页消重，不仅耗费宝贵的 人力资源，而且时效性也不能满足实际需要。如何自动地在网页集中检测出重复的内容 也成为我们关注的焦点。 2 2 网页净化技术 网页净化技术成为网络信息检索特有的一个研究领域，受到越来越多的研究者的关 注。国内外研究者针对大规模网页数据的网页净化算法进行了许多研究工作，相关算法 也较成熟。针对大量数据的网页净化一般需要预先准备一个人工选择的包含大量网页的 数据库，通过在数据库中的统计计算，得到网页噪音的判断规则。在处理数据库中网页 的时候，需要初步判断哪些内容属于网页噪音，因此需要一种不依赖训练集的网页净化 算法，不依赖训练集的净化算法不依赖于具体的网页模版，能够准确地识别出网页中噪 音，有很好的适应能力。另外网络服务个性化的相关研究也需要不依赖训练集的净化算 法，但是这方面的研究并不多。 一般去除网页噪音有两类情形：一种是为基于单一页面的处理，根据所处理页面的 一7 一 东北大学硕士学位论文第二章相关工作 d o m 树或d o m 树的变体，应用一些启发性规则对页面内的噪音去除。另一种是基于 一个或多个网站中的页面集进行页面的模板检测，把为了生成页面而在网站中使用的模 板作为噪音从页面中去除。 2 2 1 单一页面网页净化 2 2 1 1 基于标签树的净化方法 基于标签树的净化方法【9 d 0 1 针对网页净化的特殊需求，首先对h t m l 规范中的标签 按照功能进行分类，进而提出更加适合网页净化的标签树的构造方法。该方法在依据规 划网页布局的标签( 、 、 、 、 等) 和属性标签构提取出适合网 页净化的标签树后，网页净化过程就变为对标签树中结点的剪裁。依据内容块中词频数 与图片数和超链接数的比值将内容块分为主题型、多链接型、图片型三种。从而将w e b 上的网页根据内容分为有主题网页、目录网页和图片网页。对于目录型网页，将网页中 间区域的内容块作为网页的主题内容，而边缘的内容块则通过与主题内容计算相似性的 方法来决定取舍。对于图片网页，由于网页中文字较少，因而传统的向量表示不够准确， 在这种情况下，保留网页中间区域的图片型内容块就可以完成网页净化的功能。对于主 题网页，如果一个内容块是丰题类型的，则该内容块中的内容为网页主题内容的一部分。 依据该规则，深度优先遍历d o m 树并依次记录主题类型的内容块，得到该网页的主题 内容。通过与主题内容的相似性来判断剩余内容块的主题相关性。内容块的特征向量为 ( w ，w 2 ，) ，其中w 的计算如公式2 1 所示。 w 2 b n b w e i g h t j 幸曰玩 j = l ( 2 1 ) 其中，b n 为网页中内容块的总数；力为网页中不同关键词的总数；b 耽动务为网页 中内容块歹的权重，它的值由一个内容块中的重要标签来决定；b 砺为关键词i 出现在 内容块，中的词频。 基于标签树的净化方法的缺点对于目录型网页和图片型网页，净化方法比较粗糙。 对于目录型网页是将中间内容作为主题内容，但中间区域的划分不是很明确。对于图片 型网页，只是保留中间部分。另外网页块的划分方法有待改进。有些网页常常将同一个 新闻或内容用多个 或 分割开来，根据标签树的构建方法同一个新闻或内容会划 分到不同的内容块中，不能将同一个新闻或内容划分到同一个内容块中。标签树并不能 一8 一 东北大学硕士学位论文第二章相关工作 完全反映页面的语义结构。啡，。 。一二 2 2 1 2 基于视觉特征的净化方法 基于视觉特征的净化方法主要是抽取一个网页的内容结构，该方法是利用页面中各 元素的布局信息，从而能够利用布局信息对页面进行划分，保留页面中间区域，而其它 区域则认为是噪音。文献 1 1 1 3 1 q b 提出了v i p s 算法及其改进，该算法综合考虑了文件 对象模型d o m 中具有特殊作用的标签( 如：p 表示一段文字的开始，u l 用来表示一个 列表) 和视觉上的分隔符( 如空白区域、字体大小) ，将一个网页分割成语义上相近的 段落。通过观察，具有相似路径的同层网页在使用v i p s 算法进行分割后，噪音块和主 题块基本上被分割开来，而且噪音块d o m 树结构基本上是相似的，只是在颜色或者文 字上有些微差别。算法通过可视块抽取，分隔条检测及构造内容结构三步迭代进行，以 各块的内聚度值与预定义的终止条件比较作为迭代的终止条件。算法流程如图2 1 所示。 图2 1v i p s 算法流程 f i g 2 1t h ef l o wo f v i p sa l g o r i t h m 文献【1 4 】提出了根据布局信息对页面分块的方法，以消除噪音对分类的影响，但其 在分块过程中采用的页面布局方法对于h t m l 规范中的框架、图层及c s s 不支持，因 此页面布局方法并不总能反映实际的页面布局。同时分块中主要依赖t a b l e 标记作为分 块的主要参考标记，因此对于没有用t a b l e 做布局的页面不适应。 基于视觉特征的网页净化方法对页面进行细致地划分，且并未对噪音数据进行进一 步的处理。该方法虽然能综合各个方面对网页进行净化，但时间效率不高。主要是网页 块相似度比较上，用时较多。利用视觉特征对页面进行解析，能在一定程度上满足复杂 页面对算法的要求。但由于视觉特征的复杂性，运用的启发知识往往较为模糊，需要人 工来不断地总结调整规则，需要的规则往往非常多，一条规则的加入会对已经成功分析 的网页产生影响，因此，如何保证规则集的一致性是该算法的一大难点。 一9 一 东北大学硕士学位论文 第二章相关工作 这些方法都有一个共同的缺点，即必须对每一个新的网页都进行同样的处理，以致 对于处理通过模板产生的网页集信息提取效率比较低，尤其不利于搜索引擎在大量抓取 网页时的网页预处理。 2 2 2 同一模板网页净化 在基于同一个模板的网页集的去噪方面，文献 1 5 发现模板表示的数据占w e b 上的 4 0 5 0 ，并且这个数量每年以大约6 的速度在增长，另外大约3 0 的可视关键词和 超链接出现在模板中。w e b 上大量的模板的存在给许多基于网页中的关键词和超链接的 数据挖掘和检索工具带来危害，也给以网页为处理对象的应用程序的性能带来负面影 响。因此基于模板的网页净化方法越来越受到研究者的高度关注。 文献 1 6 提出了一个去除网页中噪音内容的方法。该方法首先依据 标签构造 网页的标签树，进而依据 标签将一张网页规划为相互嵌套的内容块；然后对于使 用同一个模板生成的网页集，找出在该网页集中多次出现的内容，作为冗余内容，而在 该网页集中共同出现较少的内容块就是有效信息块。这种方法假定页面的内容和布局是 基于表格的，这导致它对不是使用表格进行页面布局的页面不再适用。 文献 1 7 提出了基于模板化的网页主题提取方法，该方法采用机器学习方式生成网 页集的模板，以网页链接关系中的锚文本作为提取目标对模板进行标记，生成对应模板 的提取规则，依据模板的提取规则对网页主题信息进行提取。实验结果表明，该方法可 以快速、有效地提取模板生成的网页集主题信息，准确率达9 9 5 。将该方法应用于搜 索引擎系统中，与原来的检索系统相比较，索引文件的大小减少约5 0 ，检索的速度和 精确度也得到提高。但该方法必须局限在基于同一个模板的网页集，而w e b 上的网页 模板不计其数，因此该方法显然不够通用。 文献 1 8 1 q 了提出的d s e ( d a t a 黜c hs e c t i o ne x t r a c t i o n ) 算法使用网页u r l 作为衡量 网页模板相似性的因子，选取一个结构相似的网页模板，通过自顶向下比较两棵同模板 的网页树，去除相同的子树，把剩余部分作为网页的主题内容。匹配过程如图2 2 所示。 通过对两个页面的d o m 树进行匹配，把相同的部分作为噪声删除，这种方法对于数据 比较相近的页面，可能会将有用的数据作为噪声删除，使页面结构的完整性遭到破坏， 导致最终结果出现错误。 d s e 算法仅仅是网页结构的比较，并且对于某些网页，类似新浪博客的网页，匹配 过滤后依然保留大量的导航结点，并且i o 的开销较大。 一1 0 一 东北大学硕士学位论文 第二章相关工作 匹配后目标树a 图2 2 样本树与目标树匹配 f i g 2 2t h em a t c h i n go fs a m p l et r e ea n dt a r g e tt r e e 。 文献【5 研究一个网站中所有网页的共同风格，并提出s t y l et r e e 的概念，用来描述 一组相关网页的共同表达风格。该算法将多个网页的标签树合并成一棵s t 树，在净化 x 过程中这些网页属于同一个网站，因此s t 树又称之为s s t 树。一般，s t 树包含两种 类型的结点，类型结点和元素结点。类型结点s 表示一种布局或描述形式，用( e s ，n ) 表示，它由两部分组成，e s 表示一个元素结点序列，设e s 在各个网页的d o m 树中处 于l 层，则n 是在l 层中具有e s 这种类型的网页个数。对于一个元素结点e 来说，它 有三部分组成，用( t a g ，a t t r ，s s ) 表示，t a g 是标签名称，a t t r 是t a g 的属性集合， s s 是e 结点下的类型结点集合。s s t 获取表示噪音信息和主题内容的标签结点，并根据 每个结点的信息熵的方法判断结点是否为噪音结点来达到消除网页噪音的目的。 该方法的缺点主要产生于树的构建，在构建某个网站的树时，需要保证该网站是按 照同一种风格来构建的。如果一个网站中大多数网页使用不同的风格，可能没有相同的 类型结点。这样就不容易构建良好的树，进而会影响基于模式树净化算法的准确性。根 据页面的d o m 结构，构造模式树，进行同一网站内页面模版的检测，以排除页面内的 噪音，但对从任意网站下载的页面集或对单一页面无法处理。 一 东北大学硕士学位论文第二章相关工作 2 3 网页消重技术 重复网页的消除一直是信息检索领域一个待解决的问题。目前，网页消重技术属 于搜索引擎的研究前沿，专门的网页消重算法还比较少。国际上对转载文档消重算法 的研究最初主要是针对大型文件系统的，后来又被拓展应用于数字化图书馆项目和搜 索引擎系统。美国a r i z o n a 大学的研究人员采用计算文档的重叠程度的方法来发现一 个大型文件系统中的相似文件【1 9 】。s t a n f o r d 大学的研究人员开发了s c a m ( s t a n f o r d c o p ya n a l y s i sm e c h a n i s m ) 原型系纠2 0 1 用于发现相似的数字化文档，后来s h i v a k u m a r 和g a r c a - m o l i n a 在s c a m 的基础上，后来n a r a y a n a n 等人又对s c a m 原型系统的近 似镜像检测算法作了改进，提出了一种全文分段签名的网页消重算法【2 1 1 ，并将此用于 g o o g l e 系统，取得了良好的效果。 针对网络中大量数据重复的现状，提出的网页消重的方法比较多，目前主要采用 在信息发布系统2 1 也1 中检测相同或相似文档的方法。根据重复网页的特征，重复网页 可分成两种类型：一种是通过各网站间的直接转载而形成的内容完全一致的重复网页； 另一种是对网页内容经过了适度的加工，如截取部