（计算机应用技术专业论文）基于结构和主题的web信息检索研究.pdf

大连理1 人学硕士学位论文摘要随着i n t e m e t 技术的突飞猛进，w c b 信息量爆炸性增长，人们越来越习惯使用搜索引擎查找所关心的信息了。但浩瀚的信息资源却给搜索引擎的发展提出了新的挑战。如何有效、快捷、准确地将查询结果返回给用户，提高w e b 信息检索效果，已变成一项迫切而有意义的研究课题和热点。本文主要是围绕h t m l 和x m l 两种文档的结构特征和主题内容两方面的因素考虑，对当前的w e b 信息检索技术进行研究，包括技术较为成熟的h t m l 文档检索与刚刚起步的x m l 文档检索。首先，本文对w e b 信息检索进行了概述，并简单介绍了搜索引擎的工作原理、检索模型、研究热点、组成结构、分类及评价标准。在h t m l 文档检索研究中，由于当前检索方法的精度不高，本文利用网页| 日j 链接关系和锚文本，综合考虑文档结构和内容，对现有网页排序算法进行合理改进。实验结果表明，该算法可以在一定程度上提高文档检索的准确率和召回率。其次，检索结果以列表形式返回给用户，给用户的浏览造成很大困难。为了方便用户浏览和节省查阅时间，本文使用一种基于链接扩展的方法实现检索结果的自动分类，使其以类别目录方式加以显示。实验结果表明，该方法可在一定程度上提高网页自动分类精度，并在s e w m 2 0 0 7 中文网页分类中狭得较好结果。此外，本文还在传统h t m l 检索理论的基础上，对x m l 文档检索进行研究，根据x m l 文档结构特征，提出了一种基于融合策略和主题分类的x m l 检索再次排序的改进方法。实验结果证明，该方法能够提高检索系统的综合评价指标，并在i n e x 2 0 0 7 任务评测中获得较好结果。w e b 信息检索不仅具有较高的研究价值，也有广阔的应用前景。本文针对当前w e b信息检索技术做了进一步的研究与探讨，并解决了些现存的问题，但后期还需要完善与深入研究。关键词：搜索引擎；链接分析；锚文本；网页分类；x m l 检索大连理i ：人学硕十学位论文s t u d yo fw e bi rb a s e do ns t r u c t u r ea n ds u b j e c ta b s t r a c tw i t ht h er a p i dd e v e l o p m e n to fi n t e r n e tt e c h n o l o g y , t h eq u a n t i t yo fw e bp a g e so nt h ei n t e m e ti n c r e a s e se x p o n e n t i a l l y o n ep o p u l a rm o h o dt og e tt h er e l e v a n ti n f o r m a t i o nf r o mt h em a s si n f o r m a t i o ns t o r a g ei su s i n gs e a r c he n g i n e b u tag r e a tm a n yd i f 矗c u r i e sa r eb r o u g h tt ot h ed e v e l o p m e n to fs e a r c he n g i n eb e c a u s et h ei n f o r m a t i o no nt h ei n t e m e ti st o ov a s t h o wt od e a lw i t ht h e s eg r e a tc a p a c i t i e so n l i n ea n dr e t u l t lm o r er e l e v a n ti n f o r m a t i o nf o rau s e rq u i c k l yh a sb e c o m ea na r g e n ta n dm e a n i n g f u lh o ts p o tf o rd i s c u s s i o n t h i sp a p e rm a i n l ys t u d i e sc u r r e n tw e bi rt e c h n o l o g yb a s e do ns t r u c t u r ef e a t u r ea n dt o p i ci n f o r m a t i o no fb o t hh t m la n dx m ld o c u m e n t s t h ef o r m e rd e v e l o p e sm a t u r e l ya n dt h el a t t e ri sd e v e l o p i n gc u r r e n t l y f i r s t l y , t h ed e v e l o p m e n to fi n f o r m a t i o nr e t r i e v a l ( i r ) t e c h n o l o g yi si n t r o d u c e dr e g a r d i n gb r i e f l y a n dp r i n c i p l eo fo p e r a t i o n ，r e s e a r c hh o ts p o t ，c a t e g o r i z a t i o na n de v a l u a t i o no fs e a r c he n g i n ew h i c ha p p l yi rt e c h n o l o g yt ow c bs u c c s s f u l l ya r ef o l l o w e d b e c a u s eo ft h el o wp r e c i s i o no fc u r r e n ti n f o r m a t i o nr e t r i e v a lm e t h o d si nh t m li rd o m a i n ，t h i sp a p e rp r o p o s e sa na l g o r i t h mw h i c he x p l o i t sh y p e r l i n kb e t w e e nw e bp a g e sa n da n c h o rt e x t st or e r a n kr e t r i e v a lr e s u l t sw i t hc o n s i d e r a t i o no fw e bs t r u c t u r ei n f o r m a t i o nt oi m p r o v ec u r r e n tr a n k i n gm e t h o d s t h ee x p e r i m e n t a lr e s u l th a sp r o v e dt h a tt h en e wa l g o r i t h mh a sm u c hh i g h e l -p r e c i s i o na n dr e c a l l s e c o n d l y , ag r e a tm a n yr e t r i e v a lr e s u l t sw h i c ha r es h o w e db yr a n k e dl i s ta r eo b s t r u c t i v ef o ru s e r st ob r o w s e t h i sp a p e rp r o p o s e sam e t h o do fa u t o m a t i c a l l yc l a s s i f y i n gr e s u l t st od i f f e r e n tc a t e g o r i e su s i n ge x t e n d e dh y p e r l i n ka l g o r i t h m i nt h i sw a y ，u s e r sc a nb r o w s er e t r i e v a lr e s u l t sa c c o r d i n gt ot h es u b j e c tw h i c ht h e ya r ei n t e r e s t e di n t h ee x p e r i m e n t a lr e s u l t sh a v ep r o v e dt h i sa l g o r i t h mc a ni m p r o v et h eq u a l i t yo fw e bp a g e sc a t e g o r i z a t i o na n dp e r f o r mb e n e ri ns e w m 2 0 0 7c h i n e s ew e bp a g e sc a t e g o r z a t i o ne v a l u a t i o n a l s o ，t h i sp a p e rs t u d i e so nx m li rb a s e do nt r a d i t i o n a lh t m li rt h e o r y a n di tp r o p o s e sar a n k i n gm 就h o dc o n s i d e r i n gx m ld o c u m e n ts t r u c t u r ec h a r a c t e r i s t i ca n du s e r s q u e r ys u b j e c tb yu s i n gc o m b i n gs t r a t e g ya n dt o p i cc a t e g o r i z a t i o n i tp r o v e dt h i sm e t h o dc a ni m p r o v ex m li rq u a l i t ya n dp e r f o r mb e r e rt h a no t h e rr e s u l t si ni n e x 2 0 0 7 t h i sp a p e rd o e sf u r t h e rs t u d ya n dd i s c u s s i o no nc u r r e n tw e bi ra n da l s os o l v es o m ee x i s t i n gp r o b l e m s i nf u t u r e ，f u r t h e rr e s e a r c ha n di m p r o v e m e n tn e e dt ob ed o n e k e yw o r d s ：s e a r c he n g i n e ；“n ka n a l y s i s ；a n c h o rt e x t ；h y p e r t e x tc a t e g o r i z a t i o n ；x m lr e t r i e v a li i i 独创性说明作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得大连理工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。作者签名：司墨墨日期：超谆l 胡羔羔日人连理工大学硕士研究生学位论文大连理工大学学位论文版权使用授权书本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子版，允许论文被查阕和借阕。本人授权大连理工大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论文。作者签名导师签名塑2 年垒月j 皇同大连理j 二人学硕士学位论文1绪论1 1 研究背景随着互联网技术的快速发展，w e b 信息与日俱增，呈现指数增长趋势。一方面，互联网包含了从技术资料、商业信息到新闻报道、娱乐信息等多种类别和形式的信息，是一个极具价值的信息源。要充分有效利用w e b 的海量信息，使其真正成为便于检索和利用的知识。另一方面，由于互联网具有开放性、动态性和异构性的特点，作为一个全球分布式的网络，它资源分布分散，且没有统一的管理和结构，使得人们很难准确、快捷地获取所需的信息。面对浩瀚的信息海洋，人们觉得力不从心，往往花费了很多时间却所获甚少。如何从海量信息中有效检索到用户关心的信息，成为当前研究的重要课题和热点。在w e b 出现之前，信息检索技术( i n f o r m a t i o nr e t r i e v a l ，i r ) 就已经出现了，它主要应用于图书馆学，帮助科研人员查阅书籍。经过几十年的深入研究，m 技术日渐成熟，积累了丰富的理论，随着w c b 的诞生及快速发展，将传统i r 技术应用到w e bi r 中也是大势所趋，符合实际需求。但是w e b 具有自身独有的特点，例如含有大规模的海量信息，w c b 网站及页面的异构性，动态性等。掘统计，w e b 上不同的静态公丌网页的数量在2 0 0 1 年3 月幽内约有1 5 9 亿个，截至2 0 0 5 年1 月份，全球网页数量已逾1 1 5 亿之多。而传统i r 的检索对象是数量有限的馆减图书或者科技期刊文献，近年来则比较流行光盘数据全文检索。w c bi r 与传统i r 在检索数量上相差甚多，所以不能只是简单将经典i r 技术应用到w c b 瓜中。w e b 上的页面来源于不同的国家，覆盖不同的语言、民族、学科领域等。不同的网站和页面具有不同的组织结构，风格各异。w e b 结构的异构性使w e b 取变得更加困难。此外，w 曲页面一般都是半结构化文档，与传统的文本不同，w e b 页面通常使用h t m l 编写，而h t m l 具有丰富的标签和链接信息，不同的标签代表网页作者不同的表达意图，页面问的链接结构更是将整个互联网构成了一个巨大的网络结构图。w e b 的动态性导致互联网中许多的页面一段时间之后将被删除，并且随着时间推进，网络更新速度也随之加快，网页在互联网上的平均生存周期越来越短。w e b 上述特点给传统i r 技术提出了挑战，因此w e b 瓜技术必须依据w e b 的独有特征，结合传统i r 技术并改进以适应广大互联网用户的需求。为了提供更好的信息检索服务，结合传统i r 技术和w c b 新特征，搜索引擎( s e a r c he n g i n e ) 应运而生。搜索引擎的产生与发展对于推动互联网的进一步发展具有相当的意义。基于结构和主题的w e b 信息检索研究随着互联网应用的深入与广泛，基于h t m l 语言的网页结构逐渐暴露出许多缺陷与不足，例如h t m l 语言标签数量的增多导致语言复杂性，并且标签不能根据实际需要用户自己制定，缺少灵活性等。由于h t m l 这种半结构化语言自身的缺点，人们开始将一种新的标记语言一) ( 1 订l 应用到互联网中。随着w e b 2 0 的提出与发展，x m l 信息在互联网上的存储量越来越大，x m l 文档也被认为是未来w e b 文档的主流。如何进行有效的x m l 检索也只渐成为一项新的研究热点课题，并具有广阔的发展静景，很多问题还有待进一步的研究与解决。1 2 研究现状信息检索的研究历史悠久，早在2 0 世纪5 0 年代，信息检索就作为一个研究热点领域而诞生了。当信息检索领域在索引模型等许多方面取得了许多突破性的科研成果时，人们开始将其成功应用于互联网上。基于互联网广泛的应用与w e b 快速增长，搜索引擎应运而生。在此期间，很多专家和研究学者在信息检索领域方面提出了很多的检索方法，例如s a l t o n 提出了向量空i 、日j 模型算法i l 】并成功应用到s m a r t 系统【2 1 。该模型利用某种权重计算方法将每个文档表示成向量，并采用查询向量与文档向量的点积为相似度，用来判别文档与查询是否相关。而概率模型则是基于概率排序规则，即如果文档按照与查询的概率相关性的大小排序，那么排在前面的文档是最有可能被检索的文档。概率模型反映的是文档产生查询串的概率大小，利用这种模型计算复杂度较大，与向量空间模型类似，关键词之间是假设相互独立的，并且在没有获得样本文档之前，即没有相关的文档之前，无法估计词条的相关性。基于内容的信息检索是一种传统的信息检索方法，它的很多理论都是由小型的、静态的、同构型文档集推导出来。然而互联网所具有的开放性、动态性和异构性给信息检索领域带来了新的挑战。近几年许多研究学者开始利用w 曲页面的结构特性，提出了基于超链分析的方法，作为基于内容检索方法的补充。其中较为经典是p a g e r a n k 算法，该算法已经成功应用到著名的搜索引擎g o o g l e 中。除此之外，还有h i t s 、s a l a s 等算法。基于超链分析的检索方法虽然可以提高检索的查全率，但是研究学者认为结合多技术和方法的融合检索比单一检索方法更能有效地提高检索系统的性能【3 4 l 。搜索引擎作为新一代信息检索方式，成功地将传统成熟的信息检索技术应用到w e b当中，利用当代先进的网络技术，能够在较短的时间内获取互联网信息。它根据定的规则建立索引来组织数据库，并通过友好界面供用户查询，最后将结果加以呈现。大o e 3 1 1 1 大学硕士学位论文自2 0 世纪9 0 年代至今，搜索引擎技术伴随着互联网的发展备受瞩目。当代搜索引擎己成为一个新的研究、开发领域，它已经涵盖信息检索、人工智能、计算机网络、数据挖掘、自然语言处理等多领域的理论和技术。此外，搜索引擎具有很大的经济价值，为商业发展所必需。作为一中具有综合性的时代产物，搜索引擎已经引起了世界各国计算机科学界和信息产业界的高度关注，目前的研究与开发仍然十分的活跃，并出现了很多值得注意的动向，具有良好的发展前景。到目前为止，搜索引擎大体上主要经历了三个阶段的高速发展。第一阶段是搜索引擎的发展初级阶段，时日j 约在1 9 9 6 年前后。当时，搜索引擎索引网页数量一般少于1 ，0 0 0 ，0 0 0 个网页，并且很少更新索引和搜索新网页，采用较为成熟的信息检索和网络、数掘库技术，仅仅使用原有的技术实现互联网新的应用，代表是l y c o s 、a l t a v i s t a 等。随着a l t a v i s t a 的革命性进步，以采集网页多，查询功能快而全，成为初期搜索引擎的代表。初期的搜索引擎系统都逐步演变成为门户网站。中期的搜索引擎专著搜索技术，较快的检索速度，良好的服务，几乎为所有的大型门户网站提供检索功能。这个阶段的特点是：查询信息非常大，准确率成为评价搜索引擎的指标，技术涵盖面比较广，几乎涉及所有已有技术，例如分析用户对结果的点击等。但本身却无太多的突破，这是中期搜索引擎与后期的主要不同之处。自1 9 9 8 年到现在，是搜索引擎的发展空前繁荣阶段。这一阶段的搜索引擎索引规模达到1 0 亿网页以上，例如百度、g o o g l e 等。由于信息量巨大，查询结果数目之多，如何评价结果与查询的相关性成为研究重点。目前搜索引擎种类繁多，如百度、g o o g l e 等，都是当日仃最流行的网络信息检索工具。2 0 0 7 年6 月，全球互联网用户数量已达1 1 5 亿，预计年底将会达到1 3 5 亿。截至到2 0 0 7年截至9 月，中国互联网用户达到1 7 2 亿。据权威机构调查表明，9 6 5 的网名使用过搜索引擎，6 8 3 的网民经常使用搜索引擎。在信息爆发时代的今天，网民已经习惯地使用搜索引擎来找他们感兴趣的东西，同时对搜索引擎的功能要求也越来越高。然而，当前的搜索引擎还存在很多的不足与缺陷，具有一定的局限性。据最新调查结果显示，在中国搜索引擎用户不满意的因素中，搜索结果排序欠佳、搜索结果太杂乱这两项的比例分别是4 3 和3 7 。互联网存在大量的无关、分散的信息，人们判定检索结果时，需要花费大量的时间和精力，才能获得很少的重要相关信息。如何改善搜索引擎的检索效果已经变成一个重要而困难的问题摆在人们的面l 。在信息检索领域中，当前多数的搜索引擎通常都是以线性列表的形式为用户返回搜索结果。由于搜索结果往往是成千上万的，这使得用户可能要花费很长时间才能找到自己需要的信息。很多情况下，用户浏览前面几页仍然得不到满意答案。此外，对于普通基于结构和主题的w e b 信息检索研究互联网用户而言，专业的搜索技巧他们无法掌握，他们仅仅希望使用短而精悍的几个查询词串代表所要查找的信息，将上述简单词串输入搜索引擎后，所需查询信息便可以获得。有资料表明，7 2 4 的w e b 查询仅仅包含1 或2 个单词，总平均长度为2 3 5 个。查询词汇分布相对分散，1 0 亿个查询中几乎有一半以上只出现了一次。此外，由于用户查询习惯等原因，他们往往只是浏览几页就停止，更换查询词或者尝试其他搜索引擎工具。据统计，8 5 2 的请求用户只查看一页结果，平均只看前1 3 9 页检索结果。对于搜索引擎而言，用户的需求就是第一位。如何尽量做到在搜索输出结果前面几个就能给出用户一个满意答案，是所有搜索引擎的目标。研究信息检索中的查询结果排序方法，给用户提供合理查询结果显示，对提高检索的准确率和查询效果，提供更优秀的搜索服务，减少查找时间，方便用户使用等方面至关重要。随着互联网网络应用的广泛性与深入，x m l 越来越多地被应用到互联网中。随着x m l 信息量的增大，人们开始研究x m l 检索技术。近几年，国外对x m l 文档的检索技术研究非常的热，主要有包括x m l 解析方式、x m l 查询技术和x m l 存储等方面的研究。另外，将传统的信息技术进行改进并将其应用到x m l 检索中也是该领域的研究内容。目i j ，x m l 检索缺乏标准的评价机制，过程比较复杂，技术尚未成熟，所以研究x m l 检索技术具有广阔的发展i ；i 景。1 3 课题的研究内容来源课题主要来自于每年的s e w m 竞赛和i n e x ( i n i t i a t i v ef o rt h ee v a l u a t i o no fx m lr e t r i e v a l ，x m l 检索评测) 。s e w m 竞赛即全国搜索引擎和网上信息挖掘( s y m p o s i u mo fs e a r c he n g i f i ea n dw e bm i n i n g ) ，s e w m 是智能信息处理里面的一个很重要的方面，也是网络信息应用领域的重要活动，其目的是：促进国内外相关领域科研人员的学术和工作交流，研讨本领域的最新技术进展和发展趋势，以推动搜索引擎和w e b 挖掘技术在中国的发展。s e w m 会议由中国计算机学会互联网专业委员会主办。会议已经举办五届，分别于2 0 0 3 年3 月由北京大学、2 0 0 4 年11 月由华南理工大学承办、2 0 0 5 年9 月由清华大学承办、2 0 0 6年7 月由山东大学承办、2 0 0 7 年3 月由海南大学承办。i n e x 是致力于x m l 信息检索与评价研究的国际性论坛，每年都有来自全球各地的专家学者参加其组织的研究活动和学术会议。它是在d e l o sn e t w o r ko f e x c e l l e n c eo nd i g i t a ll i b r a r i e s 和i e e e 的支持下，由德国d u i s b e r gu n i v e r s i t y 的n o r b e r tf u h r 教授和英国q u e e nm a r y ，u n i v e r s i t yo f l o n d o n 的m o u n i l a l m a s 教授负责发起的。自2 0 0 2 年起经过五年的发展，i n e x 已经成为最著名的x m l 检索与评价组织。大连理工大学硕士学位论文1 4 本文组织结构全文一共分为五章。第一章绪论，介绍了论文研究的背景和现状，概述了当前搜索引擎技术发展的情况，并介绍了本文的主要研究内容和课题来源及论文的组织结构。第二章分析了搜索引擎的产生背景及发展，介绍了搜索引擎的基本结构、检索模型、研究热点，以及以不同方式对搜索引擎进行的分类描述。最后，给出搜索引擎性能指标。第三章介绍了基于结构和内容的超链接分析算法研究及改进。超链接分析算法可被用于评估网页质量，获得更合理的网页与查询相关度排序结果。它直接影响到搜索引擎最后的结果，对于提高搜索引擎的性能指标起非常重要的作用。它是w e b 信息检索的一项重要研究，已被广泛地应用于搜索引擎其他相关技术中。首先，本章介绍了两种经典链接分析算法：p a g e r a n k 算法和h i t s 算法，并对二者的优缺点进行深入的比较。接着，本章提出一种基于p a g e r a i l l 【与锚文本的排序算法，对原有的搜索引擎排序算法进行改进，并给出详细的实验结果与分析讨论。第四章主要介绍了基于主题分类的检索结果表现技术研究。由于搜索引擎输出大量用户不太关心的查询结果，传统的以列表方式输出查询结果使用户浪费大量时间。本章利用一种机器学习方式实现检索结果的自动分类，将输出结果以分门别类的方式输出，然后用户可以按照查询意图进行浏览各个属于不同类别的结果，从而更迅速的查询到相关信息。在分类实现过程中，本文提出基于链接扩展和锚文本的网页主题分类算法，用于改进传统网页分类方式，并给出详细的实验结果与分析讨论。第五章主要介绍了一种基于融合策略和主题分类的x m l 检索排序算法。由于h t m l 语占的缺陷和x m l 语言的优势，随着w e b 的进一步发展，x m l 将成为未来w e b 文档的主流。因此，针对x m l 文档的检索技术的研究具有重要的理论意义和较强的实用价值。本章首先介绍了x m l 的基本概念、基本理论及相关技术，然后将经过改进后的传统信息检索技术应用到x m l 文档检索中，提出一种基于融合策略和主题分类的x m l 检索排序方法，用于改进原始排序算法。最后是详细的实验过程及结果与分析。最后是全文的总结与展望。通过分析流程和算法发现，还存在很多不足，需要继续改进的地方，并提出了下一步工作的重点与展望。基于结构和主题的w e b 信息检索研究2 搜索引擎概述随着i n t e r n e t 的出现和快速发展，全球数字化和信息化的步伐日益加快，互联网的发展趋势和应用范围也受到越来越多的关注。互联网是开放和自由的，人们可以随意在任意时间和任意地点发布信息，导致互联网上的信息量越来越丰富。互联网技术开放性的特点为用户获取信息提供了很大的便利，但同样也使用户查找所需信息越来越困难，犹如大海捞针。这主要是因为互联网发布的数据信息大都是无结构或者半结构化的文档，随着网页数量的增多，对检索技术的要求也越来越高。为了帮助用户能够在互联网上更准确、快速、全面地找到自己关心的信息，新一代信息获取技术搜索引擎应运而生，并得到了飞速的发展。目前，搜索引擎已经成为在互联网上仅次于电子邮件的第二大网络应用。2 1 搜索引擎工作原理搜索引擎主要由四部分组成：网络爬虫( s p i d e r ) 、索引器、检索器和用户接口，其基本框架图如图2 1 所示。图2 1w e b 搜索引擎架构图f i g 2 1w e bs e a r c he n g i n ea r c h i t e c t u r e网络爬虫是搜索引擎中很重要的一个组成部分，主要完成的任务是：按照既定的策略以某种遍历算法自动搜索互联网上的相关网页信息，并随着时间的推移，更新已建立的索引，抓取新产生的网页。网络爬虫是一种能够利用网页间的超链接递归地访问新网页的软件程序，从而获得用户检索过程中所必需的原始数据信息。6大连理j ：人学硕士学位论文网络爬虫的工作原理可被具体描述为：网络爬虫以事先选定的一个或一组u r l 为种子节点，从而展开对相应的互联网网页的访问。当其中一个u r l 未曾爬去过，网络爬虫将其从所属站点爬取，并将该网页所含信息建立索引；如果该u r l 己被抓取但网页内容有所不同时，网络爬虫会抓取相关网页并更新已经建立的索引：如果该u r l 已被抓取但内容相同，则被舍弃。抓取后的网页中的超链接也将被网络爬虫保存，用来访问新的网页。随着新网页被抓取，新的超链接又将被发现，如此不断进行下去，从而实现对大范围内互联网信息的收集。索引器的功能是分析网络爬虫所抓取的网页内容，将网页内容表示为一种便于检索的形式，并存储在索引库中。索引表一般使用某种形式的倒排表，倒排表中的每项包含一组指针，指向相应的网页。索引器算法的好坏直接影响搜索引擎的性能，一个好的索引器应该易于实现和维护，检索速度快，占用空间少。检索器的功能是根据用户的查询，在索引库中快速检索出相关文档，将文档与查询进行相关性评估，对将要输出的结果进行排序，并能够实现某种用户相关反馈机制。检索器常用的信息检索模型有布尔模型、向量空间模型、概率模型等。w e b 搜索引擎的用户接口主要任务是接收用户的输入查询，并在检索器检索结束之后，将最终的查询结果返回给用户。其中，它包括查询接口和响应接口，查询接口主要用于用户输入，复杂的查询接口还可以执行词组的模糊组合、通配符操作、布尔查询操作等。查询结果通过响应接口反馈给用户。响应接口通常会用多个页面显示查询结果，每个页面是一个包含若干个结果的列表。在这个列表中，每条都包括了相应文档的描述。典型的信息包括：资源定位符的地址、索引的日期等。2 2 经典检索模型由于用户在进行信息检索时，希望获得与其需求密切相关的检索结果，因此信息检索系统需要解决的中心问题是：基于用户的需求，对文档集中的所有文档做出是否与查询相关的判断【5 】。这是信息检索的核心，通常通过一个相关性评价的数据模型来实现。数据模型通常会给出文档的表示方式、检索的表示方式以及检索与文档的匹配过程。信息检索技术自产生，发展至今，出现过很多不同的检索模型，其中经典的模型是布尔模型、矢量模型和概率模型【6 】。2 2 1 布尔模型布尔模型非常简单，是一种基于集合理论和布尔代数的检索模型，是其他检索模型的基础。在设计信息检索系统时，它是用得最普遍的模型，尤其是在商用信息检索系统中 ”。在布尔模型中，每个文档通过一个关键词集合来表示，所有关键词都预先保存在基于结构和主题的w e b 信息检索研究一个词典中。在查询串与文档相匹配的过程中，主要看该文档中的词条是否满足查询的条件。布尔模型认为一个查询关键词要么在文档中出现，要么不出现，所以布尔模型的关键词权重只有两个值：l 和0 。其中1 代表该关键词在文档中出现过，反之不出现情况则用0 表示。很多情况下，用户可以使用部分逻辑运算符来限定查询，例如：如果希望文档中同时出现多个关键词，则可以使用“与”来连接各个关键词，但是使用这种逻辑运算，会导致查询到的文档数目较少，随着关键词越来越多，查询结果将呈现减少趋势；但如果使用“或”运算符连接各个关键词，则会导致查询返回文档数目过多，反而会影响检索模型的准确率，让用户花费大量的时间和精力去筛选相关结果。因此为了提高检索模型查询的精度，用户可以在查询过程中尽量将查询的需求描述清楚，并尽力选择合适的关键词来描述所需信息，从而减少查询结果中文档数量。由于布尔模型比较简单，因此在应用过程中容易出现不足，它主要有以下三个方面的缺点【引。( 1 ) 对于一个信息获取系统的初学者来说，由于很难掌握布尔操作符的使用方法，因此很难将一个查询公式化。( 2 ) 不能够在查询串中说明关键词的相对重要性，即在布尔模型中，查询串中的关键词是被对等看待的。( 3 ) 在布尔模型中匹配函数由布尔逻辑的基本法则确定。所检索出的文档或者与查询相关，或者与查询无关，很难将文档按照与查询串相关性来排序。布尔模型具有表达形式化和实现过程较为简单化的优点，并且实现过程中计算代价相对较少；虽然在查询中布尔操作符对初学者来说有点麻烦，但是较其他模型中的查询语言更容易表达；该模型适合于那些明确知道自己想要查找什么信息的用户【9 】。2 2 2 向量空间模型向量空间模型是实际应用最多的检索模型t 1 0 l ，一直以来都是信息检索领域最为经典的模型。本文实验设计过程中就是采用该检索模型。在向量空间模型中，如果检索系统一共选取n 个关键词作为特征，则每个文档会被表示成n 维向量，其中向量中每一维的数值，即关键词权重，代表该关键词在文档中的重要程度。权重越大则代表该关键词对该文档重要性越大。应用向量空间模型的检索系统时，查询串也被表示成竹维向量，只不过查询向量中的权重表示对应关键词对于用户来说的重要程度。计算文档向量中的特征权重有很多方法，一般都是基于词条在文档中出现的频率，其中较为经典的权重计算公式是t f * i d f 公式。t f * i d f 公式的一个变形，其数学表示形式如公式( 2 1 )所示。8人连理工大学硕士学位论文a i k 。( 2 1 )其中，4 。代表词f 的权重，名表示词i 在文档k 中的出现的频率，为集合中文档的总数，m 为经过预处理后保留的词的个数，n t 为词i 在文档集合中出现的总个数。检索过程中，确定文档向量和查询串向量后，还需要计算文档与查询串的相似度。目前的信息检索理论中，出现过多种计算相似度的方法，其中较为常用并且效果较好的是计算两个向量间的标准化点积，将结果作为评价查询串与文档相关程度的标准，如公式( 2 2 ) 所示。s i m i l a r i t y ( g ，d ) =g jx d( 2 2 )由于单个文档仅仅与某个主题相关，而选择的关键词是基于文档集合，文档长度和含有的关键词数量一定，往往导致最后获得的文档向量中含有较多的0 。所以，在实际存储过程中，针对向量空间模型的稀疏性，人们往往采用一定的策略，从而减少存储空间，计算过程中也可以减少内存耗费，提高效率。很多实际应用实验结果表明，向量空问模型比布尔逻辑模型能够得到更加j 下确的结果，应用效果较好。因为向量空间模型主要具有以下优点。( 1 ) 向量空间模型使得对查询向量中关键词权重的赋值成为可能。( 2 ) 利用计算得到的相似度可以对获取的文档按照相关度排序。除了上述优点以外，向量空间模型也有一定的缺点。( 1 ) 在向量空间模型中，关键词是被假设为相互独立的，但实际上每个文档的关键词之间能存在着一定的联系，例如文档内具有相似意义的词条间的关系，实际应用中假设关键词相互独立会忽略词条白j 的语义关联。( 2 ) 查询构建过程中，不能像布尔模型一样使用关键词之间的逻辑关系。2 2 3 概率模型概率模型是基于以下理论：给定一个用户的查询串和集合中的文档，概率模型来估计用户查询串与文档相关的概率。概率模型假设这种概率只决定于查询串和文档。更进9 一基于结构和主题的w e b 信息检索研究一步说，该模型假定存在一个所有文档的集合，即相对于查询串的结果文档子集，这种理想的集合中的文档是被预测与查询是相关的。如果文档按照与查询的概率相关性的大小排序，那么排在前面的文档是最有可能被检索的文档。概率模型的优点是采用严格的数学理论为依据，为人们提供了一种数学理论基础来进行匹配，采用相关性反馈原理，可开发出理论上更为坚实的方法。概率论模型要明显优于布尔模型，但是比向量模型略差【i l 】，具有以下缺点。( 1 ) 计算复杂度大。( 2 ) 增加了存储和计算资源的开销，且参数估计难度较大。( 3 ) 与向量模型一样，关键词之间是假设相互独立的。( 4 ) 在没有获得样本文档之前，即没有相关的文档之前，无法估计词条的相关性。2 3 搜索引擎研究热点当需要在互联网上查找某一方面信息时，通常是借助搜索引擎如百度、g o o g l e 等。据权威机构调查表明，9 6 5 的网名使用过搜索引擎，6 8 3 的网民经常使用搜索引擎。通过这种查询方式，人们能够被提供快捷方便的服务，但随着网络资源的日益膨胀，用户往往会得到搜索引擎返回的成千上万甚至百万的检索结果，而且检索结果“质量”不是很高，主要表现为：页面内容质量低排在前面、不同主题的结果混杂，多个镜像文件被检索、网页欺骗、去重效果差、相关与不相关结果都返回等。由于现有的搜索引擎检索结果有上述种种缺陷，所以搜索引擎仍是网络检索的研究热点，当前主要的研究热点为以下几个方面。( 1 ) 能充分表达用户查询要求的查询语言。现有的搜索引擎的查询语言甚至比成熟的商业性的情报检索系统的查询语言还要简单。当然这是由搜索引擎所处的网络环境所决定的。一套能充分表达用户要求但又不增加网络负载的查询语言是搜索引擎给用户的第一个良好的印象。( 2 ) 索引数据库的组织和管理。搜索引擎的索引数据库是网络信息的一个轨迹，并要随着网络信息的变化而变化。因此它除了数据增加以外还需要有数据的删除和修改功能。如何对大容量的、非结构化的信息进行增加、删除、更改操作也是一个值得研究的问题。( 3 ) 信息的自动加工。在传统的情报检索中，数据源基本上是人工加工且有标准的用词，查全率和查准率都比较高。而搜索引擎对网上收集到的信息一般是采用自动n r 。因此，如何对信息进行准确的分类和标引是搜索引擎要研究的主要问题。一l o：赶连理i ：大学硕士学位论文( 4 ) 提高检索的查准率。网上的信息相当丰富，现在搜索引擎的问题不再是能找到多少结果，而是找到了太多的结果，且很多结果不一定与用户要求非常相关。因此提高查准率是搜索引擎查找效率的主要体现。( 5 ) w 曲信息的发掘。网络更新速度如此之快，需要迅速发现和收集网上新加入的信息和被删除的信息。搜索引擎对网络研究人员来说仍然是一个值得研究的课题。2 4 搜索引擎分类当i i 搜索引擎的种类很多，按照数据采集、分类索引的方法和服务提供方式的不同，搜索引擎系统可以分为三大类【1 2 l ：目录式搜索引擎、机器式搜索引擎、元搜索引擎。2 4 1 目录式搜索引擎目录式搜索引擎( 13 】( 也称分类式搜索引擎) 主要通过人工发现信息，由编辑人员根据信息资源的内容按定的主题进行分类组织，并形成信息摘要，将信息置于事先确定的分类框架中，组织成一层一层的分类目录，目录下面有更具体的子目录。信息的类别也由大n d , 、由粗到细，整个搜索引擎形成了一个层次型的类别目录。用户可以逐层浏览，选择不同的主题对网络信息进行过滤，所选择的主题类别越小，信息的相关性就越高，用户就越有可能找到自己所需要的信息。这类搜索引擎的性能主要取决于对所获取网页的人工归类或自动分类算法的精确度如何。目爿乏式搜索引擎的代表有：y a h o o 、o p e n 、l y c o s 等。目录式搜索引擎的突出特点是具有比较好的信息质量，但由于采用手工进行w e b 页面信息的获取和维护，所以信息覆盖率低，信息实时更新不够及时，目录维护耗费的人力资源大。为了解决目录式搜索引擎存在的问题，人们引入了人工智能技术，用机器人代替手工去发现、加工、整理信息，这样就出现了机器人搜索引擎。2 4 2 机器搜索引擎机器人搜索引擎不需要人工收集信息，而是由一个被称作“机器人”的计算机程序在网络上不停地爬行和搜索，依据一定的网络协议在i n t e m e t 中自动获取网页信息，并通过对网页内容和特征的分析，采用一定的策略组织信息建立自己的索引数据库，为用户提供查询服务。g o o g l e 、百度、天网等就是这类检索系统的典型代表。由于单个搜索引擎的覆盖范围往往不会太广，为了找到自己所需要的信息，用户常常需要使用多个搜索引擎，以期望找到更多、更全、更准确的信息。但由于不同的搜索引擎在其查询语法以及接口界面上往往不同，需要用户重新学习和适应不同的检索方法，这给用户使用多个搜索引擎带来了极大的不便。为了解决上述问题，研究人员开发了元搜索引擎。元搜基于结构和主题的w e b 信息检索研究索引擎统一了不同搜索引擎的查询接口，由统一的元搜索引擎接口对用户提交的查询请求进行处理，分别将其转换为符合底层搜索引擎查询语法要求的子查询，同时向多个搜索引擎提交查询的结果，由底层搜索引擎在各自的索引数据库中进行查询。在各个搜索引擎返回检索结果后，元搜索引擎将子查询结果进行汇总、去重、重新排序等处理，最后向用户返回最终的检索结果1 1 4 1 。2 4 3 元搜索引擎元搜索引擎系统一般都没有自己的索引数据库，而是以一个代理的角色，利用其它搜索引擎的数据库来进行服务。在层次上，元搜索引擎要比机器人搜索引擎和目录式搜索引擎要高。元搜索引擎系统的底层搜索引擎可以是机器人搜索引擎，也可以是目录式搜索引擎。元搜索引擎的优点是返回结果的信息量更大、更全，其查全率较高，解决了单个搜索引擎覆盖范围相对狭窄的局限，缺点是不能够充分利用下层搜索引擎的排序功能，用户需要做更多的筛选。本文对上述三种类型的搜索引擎在各个方面的性能进行比较，其比较结果如表2 1所示。表2 1 三种搜索引擎性能比较t a b 2 1p e r f o r m a n c ec o m p a r i s o no f t h r e ep r i m a r ys e a r c he n g i n e s除了上述分类方法以外，按照搜索引擎的检索内容、服务对象的不同，搜索引擎又可以分为两大类：综合性搜索引擎和专业搜索引擎。j o g 理_ z 大学硕士学位论文大部分搜索引擎都是综合性的搜索引擎。它们面向全体互联网用户，如g o o g l e 、百度等都属于这一种。它们本身从一开始就设计为面向所有潜在的用户，其数据库容量非常大，收集了各方面、各学科、各行业数以千万、甚至以亿计算的网页内容。专业性的搜索引擎也称垂直搜索引擎或者主题搜索引擎。它是为了专门收录某一行业、某一主题和某一领域的信息而建立，这种搜索引擎专注于自己的特长和核心技术，保证了对该领域信息的完全收录与及时更新，在提供专业信息方面有着大型综合引擎无法比拟的优势，成为搜索引擎发展的一个新趋势。它的服务对象通常是专业领域的研究通用中英文专业搜索引擎技术的研究及应用人员。众所周知，每个专业领域都有专有的词汇和用语，专业性搜索引擎使用与之相应的索引技术和检索语言，从而使在特定专业范围内的检索效果优于综合性搜索引擎，它对网上科技信息的有效利用、最新科技成果的共享提供有力工具。按照检索方式的不同，搜索引擎系统可以分为两大类1 1 2 1 ：全文检索搜索引擎和目录搜索引擎。i j 者索引网站的全部页面，能够对网站的每篇文章的每个词进行搜索。全文检索搜索引擎所检索到的结果，是与用户所提交的关键词相关的页面的地址和页面的简单介绍；后者与全文搜索引擎不同，并不索引网站上