（计算机应用技术专业论文）中文重复网页的检测算法研究.pdf

2 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：屠癣 日期驯。牟m 日 ， 。 i 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 日期：珈f d 年o 耳 e t 期：加，口r 力 ，n十，f、) 业孔雾 薅 名名签签人师本导 北京邮电大学硕士学位论文 中文重复网页的检测算法研究 中文重复网页的检测算法研究 摘要 随着互联网的日益普及和迅猛发展，网络上的信息量呈现爆炸式 的增长，搜索引擎成为人们获取信息的主要方式，而且越来越受到重 视。重复网页检测一直以来都是搜索引擎研究的重点。本文就如何提 高中文重复网页的检测算法效率进行研究。 通过比较目前国内外重复网页检测的若干方法，本人发现基于内 容的重复网页检测算法有较好的效果，而且加入链接和链接信息并没 有明显改善算法性能，于是着手研究基于内容的检测算法。 d s c 重复网页检测算法是典型的基于内容的重复网页检测算法， 并且被广泛应用。该算法基于网页语法提取网页特征，实验发现该算 法不适用于短小文档的检测。g o o g l e 对d s c 算法的试验评估发现在 该算法中加入词频信息会提高算法效率。本文结合了词频统计和自然 语言理解等策略，在计算词条权重时考虑了词频，倒置文档频率，位 置等内容信息，各种信息按一定比例用统计的方法得到关键词权值； 另外本文将向量空间模型应用到网页相似度计算中来，将网页进行解 析预处理，提取出网页纯文本，然后进行网页中文分词，统计词条权 值，提取网页特征向量得到网页文本向量表示后计算这些特征向量的 余弦系数便得到网页相似度值。 本文也对改进算法进行实验，分析实验结果发现本文的改进中文 重复网页检测算法较之前的d s c 算法在网页查重的准确率上有所改 釜 口。 最后本人提出了若干需要后续进一步的地方。 关键词：重复网页检测网页相似度计算向量空间模型d s c 算法 t f i d f 词语位置 北京邮电大学硕士学位论文 中文重复网页的枪测算法研究 i i r e s a e r c h0 n t h ea l g o r i t h mf o r c h i n e s ed u p u c a r e dw e b p a g e sd e t e c n 0 n a b s t r a c t w i t ht h ew i d es p r e a da n dr a p i dg r o w t ho ft h ei n t e r n e t ，t h e i n f o r m a t i o no nt h ei n t e r n e ti sa l s og r o w i n ge x p l o s i v e l y a sar e s u l tt h e s e a r c he n g i n ei sb e c o m i n ga ni m p o r t a n tt o o lf o rp e o p l et og a i nw h a tt h e y w a n te x a c t l ya n dt h e r e f o r ei ti sp a i dm o r ea n dm o r ea t t e n t i o n h o wt o d e t e c tt h ed u p l i c a t e dw e bp a g e si sa l w a y st h eh o ts p o ta n dk e yp o i n t ，t h u s ir e s e a r c ho nh o wt oi m p r o v ea n di n c r e a s et h ee f f i c i e n c yo ft h ea l g o r i t h m a n dm a k ei tp e r f o r m a n c eb e t t e r b yc o m p a r i n gt h ec u r r e n tk i n d so fw a y st od e t e c td u p l i c a t e dw e b p a g e si d r e wt h ec o n c l u s i o nt h a tt h em e t h o db a s e do nc o n t e n tc a n p e r f o r m a n c eb e t t e r , a n di tw o u l dn o tb ei m p r o v e do b v i o u s l ya d d i n gt h e l i n ko rt h ea n c h o r - w i n d o w ，s oif o c u so nt h ew e b - c o n t e n td e t e c t i o n a l g o r i t h m d i g i t a ls y n t a c t i cc l u s t e r i n ga l g o r i t h m i sat y p i c a lw e b - c o n t e n t d e t e c t i o nm e t h o dt h a ti sw i d e l yu s e d i te x t r a c t sf e a t u r eo fw e bp a g e s b a s e do ng r a m m a r t h er e s u l ts h o w st h a ti ti sn o ts u i t a b l ef o rd e t e c t i n g s h o r tw e bp a g e s g o o g l ed i ds o m ee x p e r i m e n t sa n de v a l u a t e dt h a ti t s h o u l dp e r f o r m a n c eb e t t e rt a k i n gf r e q u e n c yi n t oc o n s i d e r a t i o n ia p p l i e d s e v e r a l s t r a t e g i e si n c l u d i n g s t a t i s t i c a l f r e q u e n c y , n a t u r a ll a n g u a g e u n d e r s t a n d i n za n do n t h e h to fk e y w o r di nt heprovedso o n1 w e i g h t o ik eo r oi nm el m p r o v e o u a l g o r i t h mw a sc o m p u t e du s i n gt f , i d f , t h ew o r dp o s i t i o na c c o r d i n g t oa c e r t a i np r o p o r t i o n b e s i d e sia p p l i e dv s mt oa t t a i nt h es i m i l a r i t yo fw e b p a g e s t h ep r o c e s sw a s e x e c u t e da sf o l l o w s ：f i r s t l yip a r s e r e dt h eh t m l w e bp a g e sa n dt h e nt h ep u r ew e bt e x t sw e r ep r o c e s s e du s i n gc h i n e s e w o r ds e g m e n t a t i o n t h u st h ew e bp a g e sc o u l db er e p r e s e n t e di nv s m a s av e c t o ru s i n gt h es t a t i s t i c a lw e i g h to fk e y w o r da n dt h e nic o u l dg e tt h e i i i 北京邮电大学硕士学位论文 中文重复网页的检测算法研究 m u m a l s i m i l a r i t ya n dj u d g e dw h e t h e rt h e yw e r et h ed u p l i c a t e do rn o t t h ee x p e r i m e n t sw e r ea l s od o n el a t e r ic o m p a r e dt h er e s u l t sa n d f o u n dt h a tt h ei m p r o v e dd u p l i c a t e dw e b p a g e sd e t e c t i o na l g o r i t h mc o u l d p e r f o r m a n c eb e t t e r a tl a s tia l s op r o p o s e ds o m eo t h e ra s p e c t sw o r t hf u r t h e rr e s e a r c ha n d e x p l a i n e dw h a ts h o u l dd o k e y w o r d s ：d u p l i c a t e dw e bp a g e sd e t e c t i o n ，t h es i m i l a r i t yo fw e b p a g e s ，d s ca l g o r i t h m ，t i d f ，t h ep o s i t i o no fw o r d s i v 北京邮电大学硕士学位论文中文重复网页的检测算法研究 目录 第章弓i 言1 1 1 互联网发展现状1 1 2 搜索引擎简介1 1 2 1 搜索引擎简介2 1 2 2 提高搜索引擎检索效率的几种策略4 1 3 网页去重的应用前景5 1 4 本文的主要内容和组织6 第二章重复网页检测算法研究现状。8 2 1 重复网页检测概述8 2 2 重复网页检测算法研究现状9 2 2 1 基于内容的重复网页检测9 2 2 2 基于链接的重复网页检测1 3 2 2 3 基于链接信息的重复网页检测1 3 2 2 4 几种重复网页检测方法的比较1 4 2 _ 3 重复网页检钡i 相关技术。1 4 2 _ 3 1 网页解析1 4 2 3 2 网页文本分词。1 4 2 3 3 网页文本表示及特征选择1 5 2 3 4 网页相似度比较1 8 2 4 爿匠章，j 、结1 9 第三章中文重复网页的改进检测算法研究一。2 0 3 1d s c 算法模型2 0 3 2 改进中文重复网页检测算法总体设计2 l 3 3 改进中文重复网页检测算法详细设计2 3 3 4 本章小结。2 5 第四章实验设计及结果分析2 6 4 1 实验环境2 6 4 2 实验步骤。2 6 4 2 1 网页解析及纯文本提取2 6 4 2 2 网页文本的中文分词2 8 4 2 3 网页向量空间表示及相似度计算3 1 4 3 实验结果分析3 2 4 4 本章小结3 6 第五章总结和展望。3 7 5 1 本文总结。3 7 5 2 未来工作展望3 7 复参爿争文南| c 3 9 附录实验核心代码4 2 j 瞢【谢5 5 攻读学位期间发表的学术论文目录5 6 v 北京邮电大学硕士学位论文中文重复网页的检测算法研究 v i 北京邮电大学硕士学位论文中文重复网页的检测 1 1 互联网发展现状 第一章引言 互联网起源于美国的a r p an e t ，这是在1 9 6 9 年由美国国防部组建的实验研 究网，主要用于军方的通讯。在a r p an e t 的发展过程中，出现了t c p 口模型和 协议，b e r k e l e y l 拘u n i x 更是促进了t c m p 模型和协议的推广。随着a r p an e t 的 发展，人们看到了a r p an e t 的民用前景，于是在1 9 8 6 年，由美国国家科学基金 会资助建立了以a r p an e t 技术为基础的学术性计算机网络n s fn e t ，服务于教育 和科研。n s fn e t 由主干网，地区网和校园网组成。随着信息时代的到来，商业 信息占据着随着互联网的主要流量，商业网络己经取代了n s fn e t 的地位，运行， 管理和维护着互联网，并将互联网向全球社会成员开放。也使得互联网在现代人 们的生活中占据着越来越重要的地位。总之，互联网的发展过程就是从实验到学 术，从学术发展到商业应用，最后从商业应用发展到消费应用。 近年来互联网技术和规模已经空前发展，并且成为获取信息的主要渠道之 一。根据h t t p ：w w w n e t c r a f l c o r n s u r v e y 的统计，在2 0 0 1 年2 月共统计到2 8 ，6 6 9 ， 9 3 9 个网站的记录；截止到2 0 0 5 年4 月，世界上共统计到6 2 ，2 8 6 ，4 5 1 个网站 记录而且还在以每月数以百万计的数量增长。同时，这些网站所提提供的信息 也要以t ( 1 t = 1 0 0 0 g ) 来计算。 面对着网络上如此之多的海量信息，如果不知道自己所需信息的具体链接， 要从中获得自己所需要的信息是花费很大的精力得的。因此，受信息检索技术的 启发，人们把检索技术引入到互联网络中来，来帮助人们提高从互联网上寻找自 己所需要的资料的效率。 信息检索泛指用户从包含各种信息的文档集中找到所需要的信息或知识的 过程。传统的信息检索主要是针对单一语种的文档集实现，一般使用用户最为熟 悉的语种作为查询语言。而为了自动获得互联网上的大量信息，人们发明了搜索 引擎来完成这项工作。搜索引擎以一定的策略在互联网中搜集，发现信息，对信 息进行理解，抽取，组织和处理，并为用户提供检索服务，从而达到信息导航的 目的。目前搜索引擎已经成为人们获取信息的主要手段。 1 2 搜索引擎简介 北京邮电大学硕士学位论文中文重复网页的检测算法研究 1 2 1 搜索引擎简介 搜索引擎的工作原理大致可以分为：搜集信息；整理信息；接受查询。搜索 引擎通过网络蜘蛛的自动机器人程序连接每个网页的超链接自动地搜集信息；接 下来搜索引擎不仅要保存这些信息，还要将它们按照一定的规则进行编排，建立 索引；接受用户查询以后搜索引擎便检查索引，在极短时间内找到用户需要的资 料，并返回给用户。 搜索引擎技术按信息标引的方式【1 l 可以分为目录式搜索引擎，机器人搜索引 擎，元搜索引擎和跨语言搜索引擎。 目录式搜索引擎是由分类专家将网络信息按主题分成若干个大类，每个大类 再分成若干个小类，依次细分，形成了一个可浏览式等级主题索引式搜索引擎， 一般的搜索引擎分类体系有五六层，有的甚至十几层。目录式搜索引擎主要通过 人工发现信息，依靠编目员的知识进行甄别和分类。由于目录式搜索引擎的信息 分类和信息搜集有人的参与，因此其搜索的准确度是相当高的，但由于人工信息 搜集速度较慢，不能及时地对网上信息进行实际监控，其查全率并不是很好。 机器人搜索引擎是目前最普遍的搜索引擎，g o o g l e ，b a i d u 都属于这种类型。 该引擎使用多线程并发搜索技术，主要完成文档访问代理、路径选择引擎和访问 控制引擎。基于机器人搜索引擎的w e b 页搜索模块主要由u r l j 报务器、爬行器、 存储器、u r l 解析器四大功能部件和资源库、锚库、链接库三大数据资源构成， 另外还要借助标引器的一个辅助功能。具体过程是u r l j 艮务器发送要去抓取的 u r l ，爬行器根据u r l 抓取w e b 页并送给存储器，存储器压缩w e b 页并存入数 据资源库，然后由标引器分析每个w e b 页的所有链接并把相关的重要信息存储 在锚库文件中。u r l j 辑析器读锚库文件并解析u r l ，然后依次转成d o c i d 。再把 锚库中文本变成顺排索引，送入索引库。本文主要针对现在流行的机器人搜索引 擎进行相关研究。 2 图1 - 1 机器人搜索引擎 机器人搜索引擎框架如上图。通常将其分成三大模块：信息采集、信息处理、 信息查询。该类搜索引擎的优点是信息量大，更新及时，并且毋需人工干预；缺 点是返回信息过多，有很多无关信息，用户必须从结果中筛选。 ” 元搜索引擎，也叫集搜索引擎，是在统一的用户查询界面与信息反馈的形式 下，共享多个搜索引擎的资源库为用户提供信息服务的系统。元搜索引擎是对搜 索引擎进行搜索的搜索引擎。元搜索与一般搜索引擎的最大不同在于它可以没有 自己的资源库和机器人，它充当一个中间代理的角色，接受用户的查询请求将请 求翻译成相应搜索引擎的查询语法。在向各个搜索引擎发送查询请求并获得反馈 之后，首先进行综合相关度排序，然后将整理抽取之后的查询结果返回给用户。 这类搜索引擎的优点是返回信息量大；缺点是不能够充分使用原搜索的引擎的功 能，用户需要做更多的筛选。 跨语言综合搜索引擎是在一般的搜索引擎基础上加了两个功能：不同语言提 问之间的翻译和不同搜索引擎检索结果的集成。跨语言检索系统的检索功能，可 以利用现有的检索系统来实现，也可以重新构造新的检索系统或检索功能模块来 实现。 3 北京邮电大学硕士学位论文 中文重复网页的检测算法研究 1 2 2 提高搜索引擎检索效率的几种策略 由于互联网上的资料浩如烟海，现有的搜索引擎爬行的仅仅是互联网上网页 的一部分，但是尽管如此，如果我们在现有的搜索引擎上比如g o o g l e ，b a i d u 输 入关键词“人工智能 进行搜索，两者都会返回多达几十万项结果，而要在如此 之多的结果中找到自己所需要的资料，仍然需要花费用户很多的时间来从结果中 筛选，检索的效率仍然不高。因此国内外有很多学者进行了如何提高搜索引擎的 检索效率的研究，目前主要有如下几个途径来提高搜索引擎的检索效率：基于网 页去重的改进策略：基于词频统计的改进策略；基于网页分类的改进策略；基于 自动文摘的改进策略；基于知识表示的改进策略；基于自然语言理解的改进策略 等。 由于商业利益的驱使，各大网站都会争相报道所发生的一些重大事件，或者 有的网站没有自己的记者和消息来源，因此使得有的新闻会被不同的网站转载。 据统计，有的新闻的转载可达几十次之多这种转载造成了搜索引擎网页数据库 中的数据大量重复，降低了用户的查询效率。基于网页去重的改进策略是指可以 在后台处理时，对内容基本相同但来自于不同链接的信息合并，去除冗余，提高 检索速度和精度。 搜索引擎由于缺乏知识处理能力和自然语言理解能力，对信息的检索仅仅采 取机械的关键词匹配来实现。而文档的作者一般对于文中的关键信息都会重点强 调，所以关键信息会频繁出现。因此基于词频统计的改进策略可以考虑对检索到 的信息中出现的关键词进行统计，然后按关键词多少( 或频率) 的顺序呈现给用 户。 网页分类是将检索到的关键词的u r l ，文档等信息按内容分类，并按类别属 性分别选择。这样可以引导用户尽快找到所需，有较高的查准率。基于网页分类 的改进策略是一种结合主题检索和关键信息检索二者优势的方法，即可以使用户 方便地查找到某一大类信息，克服搜索范围小的不足，又可以得到较为全面而充 分的搜索结果，克服没有主题指南那样清晰的层次结构的弊端。 基于自动文摘的改进策略是根据用户提出的搜索要求，可以对检索到的所有 文档信息及网页，抽取能够高度概括其内容的摘要信息，而不是目前所做的随意 抽取包含关键词的句子，使用户对得到的结果一目了然。 基于知识表示的改进策略在处理用户采用的“知识表示 的检索尤其对于具 有表达差异的关键词检索时，可以对输入的关键词给出它的其它描述方式，如输 入“计算机”，则也应该检索出“电脑”等。在建立词典时，将具有同义关系但 不同表述方式的关键信息按某种策略链接在一起。 基于自然语言理解的改进策略是对互联网中绝大多数用自然语言表达的文 4 北京邮电大学硕士学位论文中文重复网页的检测算法研究 本数据使用机器词典，知识库，规则，统计方法等手段进行句法分析，语义分析 和推理等，使得信息检索与自然语言处理技术相结合，具有广阔的应用前景。尤 其是近年来基于统计模型的方法在自然语言处理领域的广泛应用，以及以大规模 真实文本为处理对象，更加强了信息检索与自然语言结合的趋势。 本文主要结合词频统计和自然语言理解等策略对如何提高搜索引擎的信息 检索效率进行研究。 1 3 网页去重的应用前景 由于互联网上的信息经常被相互转载，即互联网上的信息具有很高的重复 率，搜索引擎经常检索出具有相同信息的重复网页，这样不但浪费查询者许多时 间，影响了用户体验，而且浪费了大量磁盘空间。 如果能够准确找出重复网页并从数据库中去掉，就能够节省一部分存储空 间，进而可以利用这部分空间来存放更多的有效网页内容，同时提高了w e b 检索 的质量。再者通过对搜集信息的分析，预先发现重复网页，今后的网页搜集过程 就可以避开这些网页，从而提高有效网页的搜集速度：有研究表明重复网页随着 时间级别不发生太大变化，因此这种从重复页面集合中选择部分页面进行索引是 有效的。另外，如果某个网页的镜像度较高，也就预示着该网页相对重要，在搜， 集网页时应赋予它较高的优先级，而当搜索引擎系统在响应用户的检索请求并对 输出结果排序时，应该赋予它较高的权值，这些信息对提高检索质量都是非常有 用的信息。假设有用户点击了一个死链接，可以将用户引导到一个相同页面，这样 从另一方面可以增加用户的检索体验。 近似重复网页发现技术就是通过技术手段快速全面发现这些重复信息的手 段如何快速准确地发现这些内容上相似的网页已经成为提高搜索引擎服务质量 的关键技术之一。发现重复或者近似网页对于搜索引擎有很多好处： 首先，如果我们能够找出这些重复网页并从数据库中去掉，就能够节省一部 分存储空间，进而可以利用这部分空间来存放更多的有效网页内容，同时也提高 了w e b 检索的质量。 其次，如果我们能够通过对以往搜集信息的分析，预先发现重复网页，在今 后的网页搜集过程中就可以避开这些网页，从而提高有效网页的搜集速度。有研 究表明重复网页随着时间级别不发生太大变化，所以这种从重复页面集合中选择 部分页面进行索引是有效的。 另外，如果某个网页的镜像度较高，也就预示着该网页相对重要，在搜集网 页时应赋予它较高的优先级，而当搜索引擎系统在响应用户的检索请求并对输出 结果排序时，应该赋予它较高的权值。 5 北京邮电大学硕士学位论文中文重复网页的检测算法研究 从另外一个角度看，如果用户点击了一个死链接，那么可以将用户引导到一 个相同页面，这样可以有效的增加用户的检索体验因而近似镜像网页的及时发 现有利于改善搜索引擎系统的服务质量。因此去除重复网页是一项非常有意义 的工作的。 1 4 本文的主要内容和组织 如何提高搜索引擎检索效率的方法是本文的切入点，而网页去重是比较重要 的途径。因此论文主要研究现在流行的机器人搜索引擎下的重复网页检测算法。 另外通过研究如何提高搜索引擎的检索效率的若干策略得到了启发，目前主要的 策略有基于网页去重的改进策略；基于词频统计的改进策略；基于网页分类的改 进策略；基于自动文摘的改进策略；基于知识表示的改进策略；基于自然语言理 解的改进策略等。本文结合了词频统计和自然语言理解等策略，并将其应用到重 复网页检测中来。 b r o d c r 等人提出的d s c 基于内容的网页去重算法现在被普遍应用。该算法 基于网页语法提取网页特征，实验发现该算法不适用于短小文档的检测。g o o g l e 对d s c 算法的试验评估发现在该算法中加入词频信息会提高算法效率。本文结 合了词频统计和自然语言理解等策略，对d s c 算法进行改进，在计算词条权重 时考虑了词频，倒置文档频率，位置等内容信息，各种信息按一定比例用统计的 方法得到关键词权值；另外本文也将向量空间模型应用到网页相似度计算中来。 本文也设计了实验方案，使用常用评估指标评估该算法。最后讨论了后续工作的 方向。 本文的组织结构共分为五章。 第一章是本文的前言部分，主要介绍搜索引擎和重复网页检测的相关背景， 主要包括搜索引擎的发展现状以及提高检索效率的若干策略，接着介绍重复网页 检测的必要性和应用前景，最后描述了本文的总体组织结构。 第二章详细阐述了重复网页检测算法的研究现状及相关技术。研究发现基于 内容的重复网页检测算法效果优于基于链接和链接信息的检测算法，而且加入链 接和链接信息对基于内容的方法改善不是特别明显。因此本文主要研究基于内容 的重复网页检测算法。 第三章提出并详细说明了改进d s c 算法的设计。d s c 算法是被普遍采用的 基于内容的重复网页检测算法，该算法基于网页语法提取网页特征，实验发现该 算法不适用于短小文档的检测。g o o g l e 对d s c 算法的试验评估发现在该算法中 加入词频信息会提高算法效率。本文结合了词频统计和自然语言理解等策略，在 6 7 北京邮电大学硕士学位论文 中文重复网页的检测算法研究 第二章重复网页检测算法研究现状 2 1 重复网页检测概述 近年来互联网技术和规模已经空前发展，并且成为获取信息的主要渠道之 一。根据h t t p ：w w w n e t c r a f t c o r n s u r v e y 的统计，在2 0 0 1 年2 月共统计到2 8 ，6 6 9 ， 9 3 9 个网站的记录；截止到2 0 0 5 年4 月，世界上共统计到6 2 ，2 8 6 ，4 5 1 个网站 记录而且还在以每月数以百万计的数量增长。同时，这些网站所提提供的信息 也要以t ( i t = i o o o g ) 来计算。这些海量信息中存在着大量的重复网页。据d e n n i s f e t t e r l y 4 j 等人的研究表明2 9 2 的网页彼此非常相似，其中2 2 2 贝j j 完全相同。 如果搜索引擎在爬行网页的时候不进行重复网页的处理，那么势必会造成搜 索引擎的网页数据库中的数据大量的重复，这样在搜索引擎对自己的网页数据库 进行一些操作，如查询，插入，删除等，增加了一些不必要的负担和处理，从而 需要进行数据压缩。因此搜索引擎在使用爬行器爬行网页的时候，有必要将爬行 到的网页与自己网页数据库中以后的网页内容进行比较，如果内容相同的话，那 么对重复的网页进行去重处理，否则，再进行相应的处理之后再加入到自己的网 页数据库中去。这样节省了网页数据库的存储空间，并且在对网页数据库进行操 作的时候，也节省了一些时间。 一般来说网页重复有如下特点【z 1 ： ( 1 ) 重复率高。 网页的重复主要来自各个网站的网页转载。网页转载非常容易。由于用户对 网页内容兴趣的驱动，网络信息流通中人们通过复制方式进行信息共享，经典的 文章，以及新闻网页，很容易引起人们的关注，有时转载竟高达几十次之多。 ( 2 ) 存在噪声。 转载时一般都原样照搬，保持文本内容和结构的一致，并尊重版权，在开头 加入了引文信息。可是引文会导致复制的文本与原文不完全一致，本文把这种造 成转载文章与原文不同的情况称为网页噪声。还有一些其他情况引入噪声，如一 般各个网站网页的生成环境和版面的风格不同，转载的文本有时还需要h t m l i 吾 言和x m l 语言内部格式的转换，造成内部格式的不完全一致。另外，插人的广 告图片也是噪声的主要来源。 ( 3 ) 局部性明显。 局部性主要表现在转载内容的局部性和转载时间的局部性。前者是指转载的 内容主要偏向于人们关注的热点且权威网页，其他网页转载的相对较少。后者是 指转载的时间比较集中，大都在一两天内进行转载，十天以后再转载则很少。 文献【3 j 将重复网页归结为以下四个类型：如果网页文档内容和格式上毫无差 8 如果两个网页的摘要信息完全一样则被认为是重复网页； m d 5 ( 疗( 互) ) = m d 5 ( c d 以( 乙) ) 式( 2 2 ) 如果两个网页前个关键词拼成的字符串一样就被认为是重复网页； m d 5 ( c o n ( t f ) ) = m d 5 ( c o n ( t j ) ) ( 鞴卜 如果两个网页前个关键词拼接成的字符串一样且两网页关键词权重向量 之间的余弦值小于某一阈值则被认为是重复网页； 9 北京邮电大学硕士学位论文中文重复网页的检测算法研究 m d 5 ( c o n ( s o r t ( t f ) ) ) = m d 5 ( c o n ( s o r t ( t j ) ) ) ( 鞴卜 烈2 4 ) 如果两个网页前个关键词排序后拼接成的字符串一样且两网页关键词权 重向量之间的余弦值小于某一阈值则被认为是重复网页； m d 5 ( c o n ( s o r t ( t i ) ) ) = m d 5 ( c o n ( s o r t ( t i ) ) ) 式( 2 5 ) 如果两个网页前个关键词排序拼成的字符串一样就被认为是重复网页。 算法2 和5 都只是要求近似镜像网页的黼特征项相同，没有考虑到这些特 征项构成向量的夹角大小。算法3 和4 则分别在算法2 和5 的基础上分别考虑了两个 网页特征向量的相似度。但向量相似度的计算并没有使用夹角余弦值来定义，因 为它只度量了两个向量的夹角大小，而没有考虑向量的长度。认为只有当两个向 量的夹角小，同时其长度相差也小时，二者才是相似的。针对这一点提出了判断 两个向量相似度的另一种方法，即算法3 和4 的第二个条件： ( 鞴) 一， 可以看出s i m 能够同时兼顾向量的夹角和长度两个因素。当两个网页内容 毫不相关时( 即它们的关键词集合没有交集) ，彤与彬垂直，s i m 的值为1 。当 两个网页内容相同时，s i m 为o 。当两个网页相似而不相同时，s i m 的值介于o 和1 之间，s i m 的值成为判断两个网页相似度的标准。另外，类似于算法5 是对 算法2 的条件放松，算法4 也是对算法3 的放松。 后四种算法都对向量空间模型理论作了较大的简化。首先，我们只从网页中 出现的所有关键词组成的m 个特征向量提取了槲删，这把理论模型的限 制放松了。之所以可以这样做是因为： ( 1 ) 特征向量的渐分量绝对值大，基本能确定特征向量的方向。取较少的 关键词能减少算法的复杂度，尽管有可能降低其准确度。 ( 2 ) 重复网页的制作人对网页稍加改动变成相似网页时，不能改变其基本意思。 而网页的基本意思一般通过其中出现的高频词来反映。后面的( m - n ) 个词出现的 次数为1 或2 。相对而言，这些词的出现是不稳定的，当使用这些词来判断相似网 页时，反而会漏掉一大批相似网页。 但是m d 5 签名算法有极高的敏感性，作用对象稍有不同就会给结果带来很 大的差异，并且不可能从签名差异的大小来判断原签名对象差异的大小。同时算 法只是从? 蚧关键词中选取了j 个做检测，这样的话就有可能出现这样的情况： 1 0 北京邮电大学硕士学位论文中文重复网页的检测算法研究 位置在附近的词在排序上出现的微小变动，如第j 个词与第n + 1 个词位置互换 了，本来是两篇相似度很高的文章，可能会被算法漏掉。 ( 2 ) 基于特征码的重复网页检测1 1 7 j 在一般的检索系统中，需要对关键词进行索引以便查询，而关键词可能在多 篇相关的网页中出现，因此检索时会把所有相关的网页检索出来。为了只检索出 完全相同的网页，需要对网页的特征建立索引，这个特征可以保证对于不同的网 页是完全不同的，一般称这个特征为网页的特征码。把所有的特征码索引起来建 立的检索系统，就能够使检索的结果是完全相同的网页。可见网页特征码的确定 是解决问题的关键。网页特征码必须能把完全相同的网页和不同或相似的网页区 分开，一般的关键词技术是不能做到这点的。 基于特征码的方法的关键是在网页中取一个固定长的词串作为网页的特征 码显得很重要。但由于正文相同的网页中导航信息、版权信息可能不同，由于这 些信息的干扰很难从网页的开始或中间的某个固定的位置来抽取特征码。通过对 网页的分析发现在导航信息中较少的出现标点符号，尤其是句号几乎不会出现， 另外导航信息多出现在h t m l 语言中的超链接标记中。利用这两个特点，在提取特 征码时可以尽量把导航信息等干扰信息去处掉，再把句号作为一个提取的位置， r 分别在句号两边提取；长的词串构成网页的一个特征码。之所以要在句号的两边 z rrr 分别取长竺的词串，是因为在长兰一1 和= j 处的字很难构成一个词，因此更能保 2zz 证特征码的唯一性。下面是几个特征码的例子：“百七十二人其中很多是”“的 社会效果但是大陆报，“率几十倍这表明法律。 这种方法利用标点符号多数出现在网页文本中的特点，以句号两边各五个汉 字作为特征码来唯一的标识网页。因为特征码的精确匹配可以与先进的检索系统 联系起来，去重效率较高，不失为一种好方法。然而，该方法也存在不足：特征 码的精确匹配不能抵抗网页转载时产生的噪声；没有利用网页文本结构信息，会 发生把长度不同，甚至悬殊的文本看成相同网页的情况；作为产生特征码的标志 的句号有时不会在网页文本中出现，或只出现在文章末尾，有时在版权信息和超 链接中出现，这些都会导致特征码的产生错误。 ( 3 ) 基于关键词位置序列的重复网页检测 要使用种算法先需要考虑的是基本关键词如何获取，以便使用关键词列表判 断文章是否重复。常用的方法是针对已知文档样本进行频度扫描。当对各个方面 的文档进行分词和词汇频度计算后，常常可以获得高频词、中频词和低频词三种 词汇段的数据。由于关键词的提取在搜索引擎系统中由相应的模块完成，因此报 文经过处理后会产生相应的关键词列表，列表中包含关键词、出现位置、频度等 信息。该算法重点针对当两篇文档完全相同时可以获得相同的关键词命中序列， 北京邮电大学硕士学位论文 中文重复网页的检测算法研究 因此属于严格意义上的报文重复。 但是从算法的准确率而言，有两种情况需要避免。一种是两篇文档关键词三 元组的信息相同但实际内容不同的情况，这样会造成算法的误判。另外一种情况， 即关键词二元组没有匹配，但文档内容基本相同，仅仅是文档的内容次序发生了 变化，这就改变了关键词二元组的次序，造成了文档的不匹配。 ( 5 ) 基于特征句抽取的重复网页检测【8 l 国内哈尔滨工业大学信息检索研究中心针对重复网页检测的解决方案是通 过提取网页特征句的方法来实现的。 具体研究方案是：首先抽取出网页特征词，然后根据该特征词第一次出现的 位置确定该篇网页文档的特征句，再将整篇文本的最长公共子序列的比较转换为 两个句子的最长公共子序列的比较。为了抽取出每个网页文本的特征词，考虑了 每个词语的词频信息、位置信息、是否在标题中出现以及其它一些特殊的标识性 信息。最后综合考虑了上述的四个选项，分别赋予不同的比例，计算得到特征词 的权值。经实验测得，四个特征项按1 ：1 ：1 ：1 的比例分配比较合适。实验证明该方 法对于中英文的网页去重都有不错的效果，对于跨语言的去重也有一定的效果， 且兼顾了准确率和速度的要求。 首先定义了以下几个重要的概念： 定义l ：子序y l j ( s u b s e q u e n c e ) ：x = 似，b ，d ，b ，c ，b ) ，e = 徊，c ，d ，j e l ) 删 子序列，w ；，d ，彳) 则不删子序列。 定义2 ：公共子序y i j ( c o m m o ns u b s e q u e n c e ) ：z 是序歹岖与啪公共子序列，如 果z 是朋勺子序列也是y 的子序列。 定义3 ：最长公共子序列( l o n g e s tc o m m o ns u b s e q u e n c e ) ：乞 乙，z 2 ，z 。 是序列x 与y 的所有公共子序列集合，则序列x 与y 的最长公共子序列就是 m a x l e n g t h ( z i ) 所代表的子序列乞。 根据以上的初步定义，我们把两篇网页是否重复的问题转化为求两篇网页的 最长公共子序列的问题。根据语言直觉当两篇网页的最长公共子序列的长度大于 等于这两篇网页中较长的文本的长度的9 5 时则认为这两篇网页重复的概率很 大。 通过算法设计理论可以知道：最长公共子序列问题具有优化子结构，即它的 子问题具有重叠性，可以通过动态规划的算法来解决。但是该算法的时间复杂度 和空间复杂度较高，均为o ( m n ) ，其中m 和万分别是两篇网页文本的长度。 ( 6 ) 基于全文分段签名的重复网页检! i 贝! j 9 j 北京邮电大学硕士学位论文 中文重复网页的检测算法研究 这类算法采用的是一种对全文分段签名的算法，这种算法把一篇网页按一定 原则分成m 段( 如晰作为一段，或利用文本的自然段等等) ，然后对每一段进 行签名( 即计算指纹) ，由此每一篇文档就可以用m 个签名后的指纹来表示。对于 两篇文档，当它们的m 个签名中有价相同时( 堤系统定义的阈值) ，就认为它们 是重复的。 该算法使用对 - - 元组排序的方法避免了对所有网 页作两两比较，使算法复杂度有所降低。但是，该算法的空间复杂度和时间复杂 度仍然是相当大的，若应用于海量的搜索引擎系统( 通常包含上亿个w e b 页面) ， 仍然难以取得理想的效果。 ( 7 ) 基于模板消噪的重复网页检测 模板因素给网页去重算法的准确性有很大的影响。由于大量的近似镜像网页 并不是对原始网页的简单拷贝，而是将要转载的内容放在新的模板中再提供服 务。因此模板中的内容就会干扰算法程序对近似镜像网页的判断，从而导致错误 的检测结果。常见的错误结果有以下两种情况：( 1 ) 相同的主题内容由于放在了 不同的模板中( 噪音内容不同) 导致应该被消掉，但实际上被近似镜像网页检测程 序判断为非镜像网页而保留；( 2 ) 不同的内容由于放在了相同的模板中导致不 应该被消掉，但实际上被重复网页检测程序判断为镜像网页而消掉。基于模板噪 音消除的近似镜像网页检测就是先对网页进行净化，去掉网页的模板噪音内容， 进而提取出网页的正文，然后再结合其他重复网页检测方法对网页的正文进行去 重的方法。 2 2 2 基于链接的重复网页检测 这里的链接指的是网页的入链。我们可以用所有连向网页u 的网页标识，例 如u r l , 作为网页u 的特征项。如果两篇网页具有相近的特征项，我们就可以说 两个网页是重复的。 研究显示【加】基于链接的重复网页检测方法的缺点是那些只有少量入链的网 页只有很少的引用数据，它们一般不会出现在查询中，也不可能显示在查询结果 中。这样，那些还没有被其他网页链接的新网页就不可能在重复网页检测结果中 显示了。 2 2 3 基于链接信息的重复网页检测 链接信息是指出现或邻近于指向网页u 的链接中的文字，即常见的链接信息 窗口( a n c h o r - w i n d o w ) 。实际上很多网络信息提取任务都使用了