（计算机软件与理论专业论文）基于新闻版权的并行网页消重技术研究.pdf

基于新闻版权的并行网页消重技术的研究 摘要 随着网络上信息的飞速增长，搜索引擎已经成为人们查找信息的重要 途径。搜索引擎对互联网上的网页进行检索时，由于存在大量的重复网页， 不但加重了用户检索和阅读的负担，而且浪费了大量的存储资源。为了达 到更高的采集效率并满足用户需求，需要去掉这些重复的网页。论文在分 析现有的去重算法基础上，针对现有算法的缺点，提出了一种新的网页去 重算法，该算法利用转载的网页大多会标出其来源、出处这一特征进行网 页的初步去重，并结合特征串的方法对初步去重后的网页进行二次去重。 算法减少了网页文档之间相互比较的次数，更适合海量空间网页的去重。 实践表明该算法有较高的准确率和召回率。 现阶段的网页去重方法无论是基于网页内容还是基于网页特征都是单 机去重，并不能充分利用计算机资源，高效地进行网页去重。目前的并行 计算技术大多是基于m p i p v m 的，它们存在的主要问题是程序可移植性 差，不便于扩展，配置复杂等缺点。论文在对p r o a c t i v e 中间件进行深入研 究的基础上，提出了基于p r o a c t i v e 网格网络并行分布计算中间件的并行网 页消重算法一- d e l _ d u p l i c a t e ，该算法解决了目前并行技术存在的问题，实 现了并行去重。实验表明该并行去重软件可以节省更多时间，具有较高的 实用价值。 关键词：网页消重版权p r o a c t i v e 搜索引擎并行 r e s e a r c ho fd u p l i c a t e dn e w sw e b p a g e sd e l e t i o ni n p a r a l l e lb a s e d - - o nc o p y r i g h t a b s t r a c t w i t ht h ep r o m p ti n c r e a s ei n f o r m a t i o no nt h ew e b ，s e a r c he n g i n eb e c o m e s a ni m p o r t a n tm e a n sf o rr e t r i e v i n gi n f o r m a t i o ni nd i f f e r e n tk i n d so fw e bp a g e s a l a r g en u m b e ro fd u p l i c a t e dw e bp a g e sa r eg o tw h e ns e a r c he n g i n er e t r i e v e st h e w e b p a g e s i tn o to n l yb u r d e n st h eu s e rb u ta l s ow a s t e sl a r g en u m b e ro fs t o r a g e r e s o u r c e s i ti si m p o r t a n tt od e l e t et h ed u p l i c a t e dw e bp a g e st oo b t a i nh i g h e r e f f i c i e n c ya n ds a t i s f yt h eu s e r sr e q u i r e m e n t a c c o r d i n gt oa n a l y s i so ft h e s h o r t c o m i n go fe x i s t i n gm e t h o d s ，an e ww e br e m o v a la l g o r i t h mi sp r o p o s e d t h ea l g o r i t h mb a s e do nt h ew e bp a g e s o r i g i nt od e t e c tt h ed u p l i c a t e dw e b p a g e s ，w h i c hi n t e g r a t e sw i t hf e a t u r es t r i n g t h ea l g o r i t h md e c r e a s e st h et i m e so f c o m p a r i s o nb e t w e e nt e x t s i tm o r ef i tt or e m o v ed u p l i c a t e dw e bp a g e si n m i l l i o n so fw e bp a g e s 。t h ee x a m p l es h o w st h a tt h ea l g o r i t h mh a sh i g hr e c a l l a n dp r e c i s i o nr a t e e x i s t i n ga l g o r i t h m so nr e m o v i n gd u p l i c a t e dw e bp a g e s a l lw o r ko na s i n g l e m a c h i n ea n dc a r l tm i xr e s o u r c e se f f e c t i v e l y t h ep r e s e n tp a r a l l e lc o m p u t i n g t e c h n o l o g ym o s t l y b a s e do nm p i p v m ，w h i c hh a ss h o r t c o m i n g ss u c ha s d i f f i c u l tt ot r a n s p l a n t ，i n c o n v e n i e n tt oe x p a n da n dc o m p l i c a t et oi n s t a l l a nn e w d i s t r i b u t e dp a r a l l e la l g o r i t h m - - t d e l _ d u p l i c a t eb a s e do nt h ef o m a m e da l g o r i t h m w a sp r o p o s e d ，w h i c hi n t e g r a t e sw i t hp r o a c t i v et h a ti s a g r i d a n dn e t w o r k p a r a l l e l d i s t r i b u t e dc o m p u t i n gm i d d l e w a r e t h et e s ts h o w st h a tt h ea l g o r i t h m d e c r e a s e st h et i m ea n dh a sh i g h e rp r a c t i c a lv a l u e k e yw o r d s ：d u p l i c a t i o nr e m o v a l ；c o p y r i g h t ；p r o a c t i v e ；s e a r c he n g i n e ； d i s t r i b u t e dp a r a l l e l l 广西大学学位论文原创性声明和使用授权说明 原创性声明 本人声明：所呈交的学位论文是在导师指导下完成的，研究工作所取得 的成果和相关知识产权属广西大学所有。除已注明部分外，论文中不包含其 他人已经发表过的研究成果，也不包含本人为获得其它学位而使用过的内 容。对本文的研究工作提供过重要帮助的个人和集体，均已在论文中明确说 明并致谢。 论文作者签名：和砰虹矽，年月节日 学位论文使用授权说明 本人完全了解广西大学关于收集、保存、使用学位论文的规定，即： 本人保证不以其它单位为第一署名单位发表或使用本论文的研究内容； 按照学校要求提交学位论文的印刷本和电子版本； 学校有权保存学位论文的印刷本和电子版，并提供目录检索与阅览服 务： 学校可以采用影印、缩印、数字化或其它复制手段保存论文； 在不以赢利为目的的前提下，学校可以公布论文的部分或全部内容。 请选择发布时间： 口即时发布口解密后发布 ( 保密论文需注明，并在解密后遵守此规定) 论文作者签名：柳五导师签名张妒7 年 占月毕日 广西大学硕士掌位论文基于新闻版权的并行网页消重技术研究 1 1 研究背景 第l 章绪论 随着互联网技术的高速发展，网络中网站的数量也飞速的增加，网络上蕴含的信息 越来越丰富，网络成为人们获取信息的一个重要手段。人们的日常生活和网络越来越密 不可分，不论是查找资料，写博客，寻人寻物，网上购物还是远程教育，诸如此类的需 求使得相应的网站应运而生，确实方便丰富了人们的生活。如果要在如此浩瀚的网页中 寻找自己需要的信息，着实让人望而却步，而搜索引擎的诞生使其成为现实。目前使用 最为广泛的搜索引擎有：百度、o o o g l e 、天网等。这些搜索引擎的数据量巨大、查找过 程快而且准。利用搜索引擎人们可以尽情地在网上冲浪，享受搜索引擎带给我们的方便 与快捷。 据统计【1 1 ，在2 0 0 9 年2 月的网站数量已经增加至2 1 5 ，6 7 5 ，9 0 3 ，比2 0 0 8 年同期增 加了近3 0 。在这些网站上的网页又存在大量重复，据天网搜的中国互联网上从2 0 0 1 年11 月6 日16 时2 0 0 1 年1 1 月2 2 日8 时，共搜集到网页4 7 7 0 7 ，9 9 8 ，其中不重复 网页数为2 2 ，3 8 2 ，6 2 3 ，重复率为5 3 1 【6 】。如此多的重复网页既浪费抓取时间又浪费 存储空间。尤其在建立索引时必须对大量的重复网页建立索引，也使倒排文件变得庞 大，影响提供查询服务时的响应速度。如果能够找出这些重复网页并从网页数据库中 去掉，就能够节省一部分存储空间，进而可以利用这部分空间来存放更多的有效网页 内容来进行增量收集，同时也提高了w e b 页面检索质量。所以，如何高效、准确的去 掉重复的网页，提高检索效率，增加用户的检索体验是我们所要解决的问题，也是本 论文的重点。 著名的中文搜索引擎b a i d u 针对互联网上的新闻被大量转载的情况，已经在其新 闻搜索中提供了网页去重功能【2 】。图1 1 是在百度新闻搜索里输入“北京2 1 家房产商 联合降价”时，在第一页检索结果中出现的2 0 条相关新闻中，有一条新闻竟然有1 4 4 条与之相同的新闻，而仅仅是2 0 条检索结果其中的一条就有这么多的重复网页，后 面还有几十页的检索结果，可见新闻网页的重复率是非常高的。 广西大掌硕士掣坷立论文 基于新闻版权的并行网页消重技术研究 韭塞至! 丝圭童璧盒睦鲶量矗造型至! q 垒丞地篓慧聪网2 0 0 9 3 ，1 20 9 ：0 4 北京2 1 家房产商联台推出2 6 个项目景计2 0 万平方米、2 3 0 0 余套优惠商品房庸 图1 1 ：百度新闻搜索中的重复网页链接 f i g 1 - lt h ed u p l i c a t e dw e bp a g e sl i n ko fb m d un e w s 如果我们继续点击“1 4 4 条相同新闻”，则会得至u 1 4 4 条内容相同的新闻的链接和摘 要。这些相同内容的网页大部分是一字不差的转载，有少数会在导航信息或标题上做少 许改动。可见重复的网页数量之多，而且消耗了太多的资源，给搜索引擎带来了沉重的 负担，也给用户带来不便。尤其是这种新闻网页，我们只需要一篇就足够了。但b a i d u 有时候会将类别划分地过细或将内容不同的网页文本划到一类中去。例如不同年份发生 的相似新闻会被划分为一类。即使是这样b a i d u 的这个功能已经提高了用户的检索效率， 节省了服务器的处理时间。 国外的搜索引擎如g o o g l e 最近己经对网页提供了去重的功能。据文献 5 0 】介绍，在 2 0 0 4 年的7 月，如果在g o o g l e 中输入“人工智能”进行检索，则会返回几十万条符合条件 的结果，而前面的大部分都是重复的网页。在2 0 0 5 年的5 月当再次在g o o g l e 中输入“人工 智能，进行检索的时候，所返回的页面中已经基本上没有重复的网页了【3 】【4 】。因此我们 有理由相信g o o g l e 已经采用了一定的网页去重的技术。但它的去重算法效果显然不理 想，因为如果我们同样在g o o g l e 中输入“北京2 1 家房产商联合降价”进行检索时，返回 的结果中，前2 0 页的结果几乎都是重复的。 不管是b a i d u 还是g o o g l e ，由于在商业利益和技术上的保密性，我们无从知道它们 的去重技术，而且这两个款搜索引擎的去重效果仍然不尽人意，因此我们有必要对网页 去重技术进行研究、改进，以达到更好的效果。 1 2 搜索引擎简介 目前搜索引擎的商业开发非常活跃，在国外，如s t a n f o r d 大学在其数字图书馆项 目中开发了g o o g l e 搜索引擎，在w e b 信息的高效搜索、文档的相关度评价、大规模 索引等方面作了深入的研究，取得了很好的成果，使用也非常广泛。在中国g o o g l e 的发展也很迅速。在国内，先后有北京大学、清华大学、国家智能研究中心等高校和 2 广西大学硕士掌位论文 基于新闻版权的并 亍网页消重技术研究 研究单位对搜索引擎技术开展研究，并开发出了几个较好的系统。如由北京大学计算 机系网络研究室开发的“天网中英文搜索引擎，在系统规模及系统性能方面达到了 国外中型搜索引擎系统的技术水平，为国内用户提供了很好的互联网搜索服务，受到 了用户的好评。而在国内的商业搜索引擎中，“百度则以其优良的中文检索性能为 众多门户网站提供检索服务。 5 3 1 所谓“搜索引擎 ，说到底是一个网络应用软件系统，或者说是计算机应用软件 系统。从用户的角度看，它根据用户提交的类自然语言查询词或者短语，也就是所谓 的关键词，返回一系列与该查询相关的网页信息，供用户进一步判断和选取【5 l 。 1 2 1 基本原理 搜索引擎大致上被分成三个功能模块：即网页搜集、预处理和用户查询服务1 6 1 。 网页去重属于预处理阶段。工作流程如图1 2 所示： 1 2 1 1 网页搜集 图1 2 搜索引擎的三段式工作流程 f i g 1 - 2t h r e es e g m e n tf l o wo f s e a r c he n g i n e 网页搜集般采用w e bs p i d e r ，被形象的称为网络蜘蛛。它向异地的w 曲服务 器发送请求，读取网页。所以我们通过搜索引擎查询到的网页也是存储在服务器上的 而不是实时查询互联网上的网页，这也就是为什么有些网页的链接是死链接的原因。 网络蜘蛛是通过网页中的链接地址来寻找网页，下载网页文本，形成网页文本库。它 从网站某一个页面开始读取网页的内容，找到网页中的其它链接地址，根据这些链接 地址向下继续查找，这样直循环下去，直到把这个网站所有的网页都抓取完为止， 这种类型的s p i d e r 一般被称为环球s p i d e r 。实际上，我们在进行网页抓取时一般要限 制抓取的深度和抓取内容的大小，不可能无限的抓取下去，这要看搜索引擎的抓取环 境和硬件设施以及搜索引擎的用途来决定这是什么类型的s p i d e r 。 广西大掌硕士掌位论文基于新闻版权的并千5 - 网页消重技术研究 1 2 1 2 网页预处理 网页抓取下来之后就要对它们进行预处理，这其中包括了重复网页的消除、索引 的建立、链接的分析、网页重要程度的计算。 重复网页的消除是提高w e b 检索技术的关键，可以为用户提供高效的检索结果。 索引器对经过净化处理的网页进行分析，负责从网页库中读取网页、并解析网页 对每一个网页记录词频、位置、字体大小和字体大小写等信息，存到存储桶和链接文 件中嗍。简单的说，就是采用全文检索技术对文本库建立索引库，为搜索提供服务。 查询时只需对索引库进行查询，通过索引表进行链接到相关的网页，不需对原来的网 页进行查询，极大地提高了网页检索的速度。 1 2 1 3 用户查询服务 用户查询服务是通过查询搜索引擎的索引库获得相关网页，然后按照一定的排序 算法计算每个网页和查询条件的相关度，再根据相关度的高低顺序将搜索结果返回给 用户。排序器负责从数据库中提取文件，按照w o r d i d 重新排序，存到倒排文件中， 同时产生w o r d 字典，快速对查询需求进行响应。 用户接口( u s e ri n t e r f a c e ) ：其作用是输入用户查询，显示查询结果，并提供用户 相关性反馈机制。为了方便用户的使用，设计良好的搜索引擎应该拥有人性化的人机 界面，使用户可以方便的查询信息并显示查询结果1 5 j 。 1 2 2 搜索引擎的类型 搜索引擎主要分为以下几类【5 3 j ： 1 、关键词搜索引擎 关键词搜索引擎是由一个被称为蜘蛛的机器人程序以某种策略自动地在网络中 搜集和发现信息，按一定的策略对搜集的信息进行净化去重处理后，由索引器为搜集 到的信息建立索引形成索引库，然后检索器根据用户的查询词检索索引库，并将查询 结果以某种排序规则返回给用户，该类搜索引擎的优点是信息量大，更新及时，不需 要人工干预；但是返回信息过多，其中有很多无关或重复的信息，不但占用了大量的 存储资源、网络带宽，而且加重了用户的担重。目前大多数搜索引擎都是关键词搜索 4 基于新闻版权的并行网页消重技术研究 引擎。 2 、目录式搜索引擎 目录式搜索引擎是以人工方式或半自动方式搜集信息，网站的编辑人员对这些信 息进行编排整理后，提取出文章的摘要信息，然后再将信息分类放到相关的类别框架 中。这类信息多数是面向网站的，提供目录浏览服务和直接检索服务。因为这类搜索 引擎对摘要的提取是人来掌控，所以摘要都能真实的反应文章的内容，也用户不必再 逐一的打开查看。但是它信息量少、信息更新不及时，而且需要人工介入，维护工作 量非常大、。y a h o o ! 是典型的目录式搜索引擎。 3 、元搜索引擎 元搜索引擎也称为集合型搜索引擎。这类搜索引擎并没有自己的数据库，也就是 说并没有网络蜘蛛他是将用户的查询关键词同时向各搜索引擎提交，然后将返回的 结果按照自己的查重、索引、排序策略进行重新改良，再把这些结果返回给用户。服 务方式为面向网页的全文检索，通过统一的界面，在多个独立检索中根据选择和利 用合适的检索来进行网络信息查询。这类搜索引擎的优点就是返回的信息量大；但 它并不能充分使用原搜索引擎的功能，用户需要进一步的筛选 7 1 。 1 2 3 搜索引擎缺陷与不足 随着网络上信息的爆炸式增长，网页数量越来越多，搜索引擎越来越不能满足多 方面的需要。目前的搜索引擎虽然在不断完善和发展，但它的发展只有十几年的历程， 很多地方需要改进，同时也存在一些亟待解决的问题，主要表现在以下几个方面【5 】： 1 重复的网页太多，而且还不同程度的存在死链接 查询时返回给用户的信息存在大量的重复，很多时候用户找不到所需要的信息。目 前的搜索引擎没有很好的解决这个问题。就像在g o o g l e 输入“北京2 1 家房产商联合降 价 进行检索时，返回的结果中，前2 0 页的结果几乎都是重复的，而大多数人只看到第 五页就已经没有耐心和兴致继续往下看了。 另外在检索的结果中存在大量的死链接，不能定位到检索的页面，所以定期的增量 收集还有待提高。 2 抓取的广度和深度还不够，使得返回的结果不尽如人意。 要查询界面反馈给用户的结果中有很多是重复的，甚至是不相关的，这样用户就 得一个一个的去识别，判断，浪费了大量的时间和存储资源。也就是说有用信息匮乏， 广西大掌硕士掌位论文 基于新闻版权的并行网页消 技术研究 一方面网络信息过载和泛滥，转载网页重复的网页随处可见，造成了网页数量的快速 增长；另一方面用户却很难在数亿的网页中找到自己真正需要的信息，出现了“假性 饥饿 现象。f 9 】 3 缺少指导信息 互联网是一个结构复杂的巨大的信息网络，用户置身其中很容易手足无措，不知 道怎么查找。尤其是大部分是对搜索引擎甚至计算机都不太了解的普通用户，查找时 要输入什么关键词才能更直接准确的找到自己所需要的结果仍然是一个难题。目前虽 然有专门进行网络导航的搜索引擎，但是针对个人用户的导航非常的少，还有待于进 一步深入研究个性化导航技术或者针对不同用户的个性化搜索引擎。 4 为用户定制服务的能力差 用户的需求是多种多样的，每个用户都有自己的需求。如果搜索引擎可以让用户 定制自己的特殊需求，类似于智能高级搜索，按用户提出的定制需求为提供用户所需 要的信息，这将在最大程度上满足用户的需求，提高搜索引擎的人性化设计。然而目 前绝大多数搜索引擎都没有这样的服务。 5 提供主动服务和个性化服务能力差【5 3 】 为了提高用户的检索效率和效果，提高用户的满意度，必须分析、理解用户的检 索习惯、兴趣、爱好，综合这些分析主动提供给用户可能感兴趣的信息，也就是搜索 引擎提供主动服务和个性化服务，改进传统的搜索引擎只能被动地提供服务的缺陷。 目前这类技术的研究很多，但是应用实际的还很少。 高效的页面检索技术 如果我们在g o o g l e _ z 输入关键词“j a v a 学 - 3 ”进行搜索，则会返回多达5 4 3 0 0 0 项 结果。而在b a i d u 上输入同样的关键词来进行搜索，竟会返回11 8 ，0 0 0 0 项结果。要在如 此之多的结果中找到自己所需要的资料，仍然需要花费用户很多的时间来从结果中筛 选，检索的效率仍然不高。由于互联网上的资料浩如烟海，g o 0 9 1 e 和b a i d u 爬行的也仅 仅是互联网上网页的一部分。 3 8 1 因此，目前国内外有很多学者进行了如何提高搜索引 擎的检索效率的研究。目前有如下几个途径来提高搜索引擎的检索效率u 川。 6 f - - 西大掌硕士掌位论文 基于新闻版权的并行网页消重技术研究 1 3 1 基于词频统计的方法 基于词频的方法是考虑对检索到的信息中出现的关键词进行统计，然后按关键词多 少( 或频率) 的顺序呈现给用户，体现网页的重要程度或相关度。由于搜索引擎缺乏知识 处理能力和自然语言理解能力，对信息的检索仅仅采取机械的关键词匹配来实现。而文 档的作者一般对于文中的关键信息都会重点强调，所以关键信息会频繁出现。 1 3 2 基于网页去重的方法 互联网上的重复网页越来越多，主要是由于商业利益的驱使，各大网站都会争相报 道所发生的一些重大事件。有的网站没有自己的记者，因此使得有的新闻会被不同的网 站频繁转载。根据我们的统计，有的新闻的转载可达上百次之多。这种转载造成了搜索 引擎网页数据库中的数据大量重复，加重了索引的负担，降低了用户的查询效率。可以 在后台处理时，对内容基本相同但来自于不同链接的信息合并，去除冗余，提高检索速 度和精度。 1 3 3 基于网页分类的方法 将检索到的关键词所在的u r l 和文档等都列出来，按内容分类，并按类别属性分别 选择。这样可以引导用户尽快找到所需，有较高的查准率。这是种结合主题检索和基 于关键信息检索二者优势的方法，既可以使用户查找到与自己查询需求相关的一类网 页，扩大了搜索范围，同时又可以返回给用户全面的搜索结果，它将查询条件按主题分 类，形成了清晰的层次结构。 1 3 4 基于知识表示 基于知识表示的方法可以对用户输入的关键词给出它的其他描述形式。比如输入 “防盗门 ，搜索引擎也应该检索出“安全门”等。这样对于具有表达差异的关键词检 索，在建立_ w o r d 词典时，应该将这种具有相同意思但采用不同词汇的同义词将关键信息 按某种策略链接在一起，搜索时进行查找比较。比如“防盗门”与“安全门”这种都 是相同意义但不同表达方式的词语表达。 广西大掌硕士掌位论文 基于新闻版权的并行网页消重技术研究 1 3 5 基于自然语言理解 由于i n t e m e t 中的绝大多数文本型数据都是用自然语言表达，对自然语言的处理使 用机器词典，知识库，规则，统计方法等手段进行句法分析，语义分析和推理等，使得 信息检索与自然语言处理技术相结合，成为当前国际上的一个重点研究方面，因此具有 广阔的应用前景。尤其是近年来基于语料库技术，基于统计模型的方法在自然语言处理 领域的广泛应用，以及以大规模真实文本为处理对象，更加强了信息检索与自然语言结 合的趋势。 1 3 6 面向跨语言信息检索 由于i n t e r n e t 的全球信息化，用户对于从w e b 信息中查询一个多语种文档集的情形 变得越来越普遍。然而，由于存在语言障碍，这要求用户必须具备一定的外语知识，以 便明确的表述自己的查询要求。如果用户能够以自己最熟悉的语言正确输入查询需求， 而同时得到用其他多国语言描述的信息，这种跨语言信息检索对于用户来说无疑是最希 望的，但这种跨语言的检索显然难度更大。 1 3 7 基于自动文摘 随着自然语言处理技术的发展和应用，可以根据用户的检索条件，在数据库中匹配 能高度概括文章内容的摘要信息，过滤到无关的信息。而目前大多数的搜索引擎都是随 意抽取带有查询词的句子组成摘要，这样的摘要根本不能反应文章的真实内容，而且摘 要看起来杂乱无章，无法理解。这样很多时候用户只看摘要根本无法判断返回结果是不 是自己需要的信息。类似于g o o g l e 这样的搜索引擎，其网络数据库中的信息及网页，均 按一定的策略进行存储。 1 4 研究的意义和研究成果 我们可以看到检索效率不高仍是目前搜索引擎存在的一个很大的问题，使得我们不 能充分体验到搜索引擎应该带给我们的方便与快捷。根据中国互联网络信息中一c 。, 2 0 0 5 年7 n 发布的统计报告显示，用户在回答“检索信息时遇到的最大问题这一提问时， 选择“重复信息太多选项的占4 4 6 ，排名第1 位【l l 】。据统计，目前h n e m e t 重复网页 广西大掌硕士掌位论文基于新闻版权的并行网页消重壑。爿乞研究 约占3 0 4 5 1 2 , 1 3 】，于是将相同的网页进行分类或者去除内容相同的重复网页成为了 搜索引擎技术中的一项很有意义的工作。重复网页的消除对于提高搜索引擎检索质量有 着至关重要的作用，是网页搜集和网页索引之间的桥梁。如果能够找出这些重复网页并 从数据库中去掉，就能够节省一部分存储空间，进而可以利用这部分空间来存放更多的 有效网页内容，同时也提高w e b 页面检索质量。因而如何快速准确地发现这些内容上 相似的网页已经成为提高搜索引擎服务质量的关键技术之一。而目前存在的技术或多或 少的存在一些缺陷，还有待进一步的改进。 本论文的主要工作如下： 1 对现有的网页去重算法进行深入研究，熟悉其去重原理和实现方法，了解现 有算法的不足。 2 针对现有网页去重算法网页间比较次数巨大，准确率和召回率不理想这一特 点，本论文提出了一种基于新闻版权信息的网页的去重算法，该算法利用版权信 息和特征码相结合的方法，大大减少了海量网页去重时两两之间的比较次数，提 高了去重的质量和效率。 3 将本文提出的基于新闻版权的去重算法与传统的特征码去重的算法相比较，通 过实验表明基于新闻版权的去重算法在去重时间上是线性增长的，而特征码方法 是指数级增长，本文算法去重总时间明显优于特征码算法。 4 针对现有网页去重方法都采用单机去重的缺点，引入p r o a c t i v e 中间件，搭建 分布式并行计算环境，提高工作效率并高效整合资源，充分利用c p u ，同时实现 节点对等，不存在中心节点瓶颈问题。实验证明该并行环境部署灵活，一处编写， 随处配置，去重效果理想。 1 5 本论文的结构 本论文分为五个部分： 第一章主要介绍了搜索引擎的基本原理以及现有的提高页面检索质量的方 法，进而引出了本论文研究意义和主要工作 第二章详细阐述了本论文所用到的相关知识，包括文档复制技术、重复网页 的定义及特点、网页去重技术，并对现有的网页去重技术进行对比， 指出其中的缺点和不足 9 基于新闻版权的并行网页消童 技术研究 第三章详细介绍了一种新的基于新闻版权信息的网页去重方法，并结合实验 加以说明其良好的去重准备率和召回率，以及在处理海量网页时的优 势。 第四章 对分布、并行的网格技术p r o a e t i v e 中间件的相关知识点进行了详细介 绍。对结合p r o a e t i v e 实现的并行网页去重原型d e ld u p l i c a t e 进行详 细阐述，然后将其应用于实践，通过实践结果表明并行去重的优越性。 第五章结论和展望。 1 0 广西大学硕七掌位论文 基于新闻版权的并行网页消重技术研究 第2 章网页去重的国内外研究现状 网页去重在网页预处理阶段乃至整个搜索引擎都有着至关重要的作用，本章介 绍有关网页去重的发展起源及国内外研究现状。 2 1 网页查重的相关知识 早在2 0 世纪7 0 年代初，就有学者研究阻止大规模拷贝程序的技术和软件。但是这只 是用于复制检测，也就是剽窃、抄袭的检测，其目的在于知识产权的保护，o t t e n s t e i n 在1 9 7 6 年提出了基于属性计数法( a t t r i b u t ec o u n t i n g ) 检测软件剽窃的方法。但是，单 纯的属性计数法抛弃了太多的文章结构信息，导致错误率太高。 在二十年后，出现了自然语言的复制检测，这一部分就涉及到了网页查重技术。 当前，提出的网页去重的方法还比较少，主要沿用信息发布系统中相同或相似文档 的检测或去重时应用的方法。 2 1 1 文档复制检测技术 复制检测又称剽窃检测，也有人称为副本检测，它不但是实施知识产权保护的一种 重要手段，也是提高信息检索效率的一种手段。所谓复制检测，就是判断一个文件的内 容是否抄袭、剽窃或者复制于另外一个或者多个文件中的部分或全部内容。剽窃不仅仅 意味着原封不动地照搬，还包括对原作的移位变换、同义词替换以及改变说法重述等方 式【1 4 1 。 复制检测基本上都集中在文档检测上，网页去重中的许多方法都是基于文档复制检 测技术。2 0 世纪末就有学者开始研究文档复制检测技术，至今涌现了许多具有里程碑 意义的成果。简述如下： l 、c o p s 原型系统 1 9 9 5 年，斯坦福大学的b r i n n g a r c i a m o l i n a 等人开发出 c o p s 原型系统【1 5 】。 c o p s 是个基于注册的文档复制检测系统，它既可以在系统中注册文档又可以进行复 制检测，也就是说在注册文档之前，首先检测要注册的文档是否为剽窃文档。c o p s 原型 是以句子为单位，把文档分解成苦干的句子序列，然后散列每一个句子，生成对应的散 基于新闻版权的并行网页消重技术研究 列值。通过比较要注册文档和数据库中已有文档的散列值，得出要注册文档的相似性， 从而判断文档是否为剽窃文档。 它的缺点是造成了无关文档匹配的机会很大，因此在检测结果中出现了大量的假阳 性噪声，影响了检测结果的准确率。 虽然c o p s 系统存在一些问题，但是它为以后的数字文档复制检测系统奠定了基础， 后来的检测系统框架与c o p s 大同小异。c o p s 的系统结构如图2 1 所示： 图2 1 ：c o p s 系统模块 f i g 2 - 1m o d u l e si nc o p si m p l e m e n t a t i o n 2 、s c a m 原型系统 19 9 5 年，g a r c i a m o l i n a 等人提出了s c a m 原型系统【1 8 ，1 9 s c a m 改进t c o p s ，主要用于发现知识产权冲突。s c a m 原型系统借鉴了信息检索技 术中的向量空间模型，使用基于词频统计的方法来度量文档相似性。系统首先统计文档 中各个单词出现的次数，然后参照向量空间模型，提出了相关频率模型r f m ( r e l a t i v e f r e q u e n c ym o d e l ) ，用以度量文档相似性。向量空间模型一般采用点积或者余弦公式来 度量相似性，而相关频率模型其实是对余弦公式进行了改动，试图提高文档复制检测的 精度。后来g a r c i a m o l i n a 和s h i v a k u m a r 等人还在s c a m 的基础上提出了d s c a m 模型。 将检测范围从单个注册数据库扩展到分布式数据库上以及在w e b 上探测文本复制的方 法。 此外，s c a m 原型系统使用一个倒排索引结构来存储数据库中已有文档的文本块。 新文档注册到数据库中时，创建并保留关于文档文本块的索引。每个文本块的入口指向 1 2 广西太掌硕士掌位论文 基于新闻版权的并行网页消重型怜习拶巴 一些记录，每一个记录都有两个属性( d o c u m e n t ，f r e q u e n c y ) ，其中d o c 啪e n t 是一个数据库 中已有文档的唯一标志符，f r e q u e n c y 是给定的文本块在d o c u m e n t 文档中出现的次数( 即 频率) 3 、c h e c k 原型系统 1 9 9 7 年，香港理工大学的s i 等人建立了c h e c k 原型系统【2 0 1 ，c h e c k 采用统计关 键词的方法来度量文档相似性，首次把文档结构信息引入到文档相似性度量中。原型系 统需要解析每一篇文档，获得其结构特性，并存入注册数据库中。c h e c k 把一篇文档 按照其章、节、段落等组织成一棵文档树，树的根结点就是整篇文档，其他结点是文档 的一个片断，父结点内容恰好是其子结点内容之和。然后，运用信息检索技术中关键词 提取的方法【2 1 五4 】，根据词频提取整篇文档的关键词。由于c h e c k 原型只检测原文件， 而原文档中含有格式信息。所以，c h e c k 在提取关键词时还采用了一些启发式。比如， c h e c k 认为那些斜体和粗体的单词一般都是重要的单词，所以把这些单词都看作是关 键词，而无论其出现频率有多少。接下来，c h e c k 统计各个结点上出现的关键词，结 点上的每一个关键词都以其在该结点上的频率比重为相应权重。最后，由此构成的树就 成为该文档的结构特性。 c h e c k 在比较两篇文档时，按照深度优先比较两篇文档结构特性的相应结点。如 果父结点不匹配，那么子结点就不必比较。最后统计匹配结点比率，作为相似度依据。 c h e c k 根据两个结点关键词向量的相似度来判定结点是否匹配，如果关键词向量相似 度大于系统规定的阈值，则认为两个结点匹配，否则认为不匹配。 4 、m i ) r 原型系统 2 0 0 0 年，m o n o s t o r i 等人建立了m d r 原型系统【2 5 】。m d r 首先把候选文档构造成一 棵后缀树，然后运用匹配统计算法直接在被检测文档中寻找最大匹配字符串。m d r 的 后缀树需要很大的存储空间。 后来m o n o s t o r i 等人又提出用后缀向量存储后缀树。后缀向量是从后缀树导出的有 向无环图的一种存储方式。后缀向量中只保存结点信息，不保存边索引，边标识从字符 串中获取，所以极大地节省了空间。 5 、c d s d g 原型系统 2 0 0 3 年，西安交通大学的宋擒豹、沈钧毅等人提出7 c d s d g 原型系统f 2 6 1 。c d s d g 原型系统是为了解决数字商品非法复制和扩散问题而开发的一个基于注册的复制检测 广西大掌硕士掌位论文 基于新闻版权的并行网页诮重拇沐研究 原型系统。 c d s d g 的方法与c h e c k 方法非常类似。它也是把文档按照章、节、段等不同的粒 度组织成一棵结构树，然后与c h e c k 方法一样获得每个结点的关键词向量( c d s d g 称 为主题向量) 和相应的词频向量。但是，在匹配两个结点时，c d s d g 既需要度量两个结 点的语义重叠度，又需要度量结构重叠度。语义重叠度就是词频向量的相似度，不过， c d s d g 并没有采用点积或者余弦公式，而是采用了与s c a m 一样的度量公式， c d s d g 按照粒度从大到小的次序逐级比较结点，并且只有当语义重叠度和结构重 叠度均小于给定阐值时才认为结点匹配，进入下一级结点，当到达叶子结点时，采用基 于语句的穷举比较法，以确定是否真正发生了复制行为。 2 1 2 重复网页的定义及特点 一直以来，对于重复的定义都非常模糊，没有一个清晰的定义。一字不差可以理解 为重复，字面上意义相近也可以理解为重复。对于重复各人都有自己的定义。 文献【2 7 将内容重复归结为以下四个类型： 1 ) 如果2 篇文档内容和格式上毫无差别，则这种重复叫做f u l l - l a y o u td u p l i c a t e 版面内容完全重复。 2 ) 如果2 篇文档内容相同，但格式不同，叫做f u l l , c o n t e n td u p l i c a t e 内容完全重 复。 3 ) 如果2 篇文档部分重要内容相同，并且格式相同，则称为p a r t i a l 4 a y o u t d u p l i c a t e 局部版面重复。 4 ) 如果2 篇文档有部分重要内容相同，但是格式不同，则称为p a r t i a l c o n t e n t d u p l i c a t e s 局部内容重复。 c o n r a d 对于重复的定义是：如果两篇文章之间有超过8 0 的用词相同，而且长度 相差不超过正负2 0 ，则这两篇文章就是重复的。另外他认为现在对于网页查重的研 究忽视了对正文部分结构差异的研究，他还试图将重复的网页按照正文部分的结构分成 e x c e p t ，e l a b o r a t i o n , i n s e r t i o n ，f o c u s ，r e v i s i o n 五类。e x c e p t ：表示一对相似的网页正文部 分第一段是完全一样的，而e l a b o r a t i o n 则意味着正文的中间若干段是相似的。 p u g h ( 在g o o l e 工作) 对于重复的定义就要简单得多：如果两篇文章之间有超过r 个特 征相同，则它们就是相似的。 1 4 基于新闻版权的并行网页消重技术研究 网页在重复方面的特点，归纳血n v 1 2 6 1 ： ( 1 ) 转载率高。网页的重复主要来自转载，网页转载非常容易。由于用户兴趣的驱 动，网络信息流通中人们通过复制方式进行信息共享，经典的文章，以及新闻网页，很 容易引起人们的关注，尤其是热点新闻，比如十七大会议的相关新闻，新闻联播连续推 出四位新人等热点新闻，有时转载竟高达几十次，上百次之多。 ( 2 ) 噪声明显。转载的文章大都不会做比较大的修改，只是在文章的开头加入引文 信息进行说明。但就是这样的引文导致转载过来的网页与原文不一致，还存在其他一些 可能引入噪声的情况，如一般各个网站网页的生成环境和版面的风格不同，它都是按照 自己的要求生成相应的样式，转载的文本有时需要还h t m l 语言和x m l 语言内部格式的 转换，造成内部格式的不完全一致。另外，很多网站在网页中还插入了一些广告图片， 导航信息等，这些都导致了网页噪声的产生。 ( 3 ) 局部性明显。主要表现在转载内容的局部性和转载时间的局部性。转载内容的 局部性是指网站一般都是选择热点重大新闻进行转载，以增加网站的点击量，其他网页 转载的相对较少。转载时间的局部性是指转载的时间比较集中，都是在重大新闻出现的 几天转载，过了这段时间就很少再有网站转载了。 根据网页重复的特点，目前已经采用了很多方法进行网页去重，下面就介绍一下国 内外的研究现状。 2 2 国内外研究现状 2 2 1 国外的去重算法 国外的去重算法主要分为以下几大类： t f i d f 在网页查重中的应用 t f i d f 算法被广泛应用于自然语言处理的分类聚类算法中【3 l 】。t f 就是特征c 在文 档中的出现次数，i d r 贝t j 是该特征的逆文档频率，将它应用于查重，其正确率以及召回 率都较高，但是它的效率不理想，也比较难以确定特征的个数，这是它的缺点。目前国 内的一些网页去重策略有很多是融入了t f i d f 算法，并加以不同程度的改进。 d s c 和d s c s s 算法t 2 9 d s c ( d i g i t a ls y n t a c t i cc l u s t e r i n g ) 及其改进d s c - s s ( s u p e rs h i n g l e ) 两种算法是 基于新闻版权的并e i - 网贫消重技术研究 i 扫b r o d e r 在1 9 9 7 年提出的。d s c 将文章按r 1 个字一组分成一个s h i n g l e ，整篇文章就由w 个s h i n g l e 组成，来源于c o p s 原型系统。再根据一种过滤策略( 如每1 1 个s h i n g l e d 0 取一 个) ，过滤出其中的一些s h i n g l e ，由这些被选中的s h i n g l e 参加比较。由此可见，过滤 策略是影响算法效率的关键。d s c 所使用的过滤算法是每2 5 个s h i n g l e 中保留一个，但 是这种方法极大地损害了算法的精确性，很多完全不同的文档被判断为相似的文档；当 文档数目较多时，比较次数极大地损害了该算法的效率。它的改进d s c s s 则是使用 s u p e rs h i n g l e s ，即将几个s h i n g l e 合在一起形成一个s u p e rs h i n g l e s ，这样与其比较多个 s h i n g l e s ，还不如比较一个s u p e rs h i n g l e s ，减少了比较的次数。但是这种算法对于较为 短小的文档而言却是个灾难，在处理短小文档时正确率将大幅下降，因为短小的文档没 有很多的s h i n g l e s 。对于包含型( c o n t a i n m e n t ) 文档( 一篇文章完全包含另一篇文章的内 容) ，一个长的文档包含