（计算机应用技术专业论文）校园网搜索引擎重构.pdf

摘要 摘要 随着计算机技术和网络技术的不断发展，校园网作为学校内部信息共享、 校际间信息交流的平台也得到了快速发展。校园网上信息量的增加，以及信息 的分布存储，给用户检索信息带来了困难。导致校园网上大量资源得不到充分 利用，造成了信息资源的浪费。校园网搜索引擎是一个对校园网内部信息资源 进行搜集整理，然后供用户查询的系统。它主要包含四项核心技术，搜索器技 术、中文分词技术、索引技术和检索技术。 本课题是在已有校园网搜索引擎的基础上，针对旧版本校园网搜索引擎出 现的问题，对其进行的重构。旧版本的主要问题如下：搜索器方面，对网页的 解析不够完备导致的搜全率过低，校园网中大量存在的异构文本( w o i m 文档) 未能实现抓取等问题；检索器方面，检索结果的网页只能简单的输出而没有考 虑排序等。因此，新版本重新设计了搜索器和检索器子系统，搜索器能够较好 的完成自动对网页的抓取和解析，并实现了对异构文本的获取；检索器方面设 计了新的相关度算法。算法基于t f i d f 思想，并添加了页面版式和网页层次等 多种因素。在网页排序时能较准确的反映网页权值，将检索结果排序后输出； 索引方面，为了适应新的网页排序算法，重新设计了索引的结构。 关键词：校园网；搜索引擎；网络蜘蛛；索引；网页排序 a b s t r a c t a b s t r a c t w i t ht h ed e v e l o p m e n to fc o m p u t e ra n dn e t w o r kt e c h n o l o g y , c a m p u sn e t w o r kh a s b e e nd e v e l o p e dr a p i d l ya sap l a t f o r mf o rt h ei n f o r m a t i o ns h a r i n ga n de x c h a n g i n g t h e i n c r e a s eo n l i n ei n f o r m a t i o no nt h ec a m p u sn e t w o r ka n dd i s t r i b u t e ds t o r a g ed i r e c t l y r e s u l t e dt h a ti ti sd i 伍c u l tf o ru s e r st or e t r i e v ei n f o r m a t i o n , a n di tl e a dt ot h el a r g e n u m b e ro fi n f o r m a t i o nr c s o u r c 意sw e r en o tu s e da n dt h ei n f o r m a t i o ni sw a s t e d c a m p u s n e t w o r ks e a r c he n g i n ei sas y s t e mt h a ti tg a t h e r st h ei n f o r m a t i o no nc a m p u s n e t w o r kr e s o 啊- c e s ，t h e nt h eu s e rc o u l dq u e r yf r o mi t i tm a i n l yi n c l u d e sf o u rc o r e t e c h n o l o g i e s ：s p i d e r , c h i n e s ew o r ds e g m e n t a t i o n , i n d e x i n ga n dr e t r i e v a l t 1 1 i st o p i cr e c o n s t r u c t st h ee x i s t i n gc a m p u sn e t w o r ks e a r c he n g i n e0 1 1t h eb a s i s o ft h eo l dv e r s i o n t h em a i nq u e s t i o n so ft h eo l da l ea sf o l l o w s t os p i d e r , i n a d e q u a t e a n a l y s i so ft h ew e b s i t el e dt ot h el o w l yt o t a lr a t e t h e r ei s ag r e a td e a lo f h e t e r o g e n e o u st e x t s ( d o e ，p a l ，e t c ) i nt h ec a m p u sn e t w o r k t h e s er c s o u r c e sh a v e n t b e e nc r a w l e d t oi n d e x i n g , t h ei n d e xr e s u l t so r a yb eo u t p u ts i m p l yw i t h o u t c o n s i d e r i n gs o r t i n g a g a i n s tt h e s ei s s u e s ，t h en e w v e r s i o nr e d e s i g n st h es p i d e ra n d r e t r i e v a ls u bs y s t e m t h en e w s p i d e rc a nb e t t e rc o m p l e t et h ec r a w la n d t h ea n a l y s i so f w e b p a g e sa u t o m a t i c a l l y a n di tr e a l i z e st oc r a w lh e t e r o g e n e o u st e x t s t h er e t r i e v a l d e s i g n san e ww e b s i t ec o r r e l a t i o na l g o r i t h m 1 1 1 ea l g o r i t h mb a s e so nt f i d f , a n d c o m b i n e sw e bp a g e sl a y o u t , l e v e l sa n do t h e rf a c t o r s i tc a nr e f l e c tt h ev a l u eo ft h e w e b s i t e s 五出m o r ea c c u r a t e l yw h e nt h ew e bp a g e sa r eb e i n gr a n k e d ，a n dt h e no u t p u t t h er e t r i e v a lr e s u l t so r d e r l y i no r d e rt oa d a p tt ot h en e ww e b s i t es o r t i n ga l g o r i t h m , t h e i n d e x i n ga l s or e d e s i g n sn e ws t r u c t u r e f i n a l l y , t h es y s t e mi si m p l e m e n t e da n dt e s t e d , a n dt h er e s u l ts h o w st h a tt h e 芦o p o s e dm e t h o di sp r o m i s i n g k e yw o r d s ：c a m p u sn e t ；s e a r c he n g i n e ；s p i d e r ；i n d e x ；p a g er a n k i n g 学位论文版权使用授权书 本人完全了解北京机械工业学院关于收集、保存、使用学位论文 的规定，同意如下各项内容：按照学校要求提交学位论文的印刷本和 电子版本；学校有权保存学位论文的印刷本和电子版，并采用影印、 缩印、扫描、数字化或其它手段保存论文；学校有权提供目录检索以 及提供本学位论文全文或者部分的阅览服务；学校有权按有关规定向 国家有关部门或者机构送交论文的复印件和电子版；在不以赢利为目 的的前提下，学校可以适当复制论文的部分或全部内容用于学术活 动。 学位论文作者签名： 声。扩年月声扩日 ( 注：非保密论文无需签字) 、 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 年月 日年月日 硕士学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 签名：劲恸 必u 疹年2 - 月2 扩日 第一章引言 1 1 课题背景 第一章引言 意大利比萨大学a n t o n i og u u i 和爱荷华州立大学a l e s s i os i g n o r i n i a l s o 共同 完成的一份最新的研究论文显示，截至2 0 0 5 年1 月份，全球网页数量已逾1 1 5 亿之多。人们在享受互联网带来的便利的同时，却面临着一个如何在如此海量 的内容中准确、快捷地找到自己所需要的信息的问题。 由此互联网搜索引擎应运而生，搜索引擎以一定的策略在互联网中搜集、 发现信息，对信息进行理解、提取、组织和处理，并为用户提供检索服务，从 而起到信息导航的目的。搜索引擎出现虽然只有1 0 年左右的历史，但在w 曲上 已经有了确定不移的地位据c n n i c 统计，它已经成为继电子邮件之后的第二 大w e b 应用。虽然它的基本工作原理已经相当稳定，但在其质量、性能和服务 方式等方面的提高空间依然很大，研究成果层出不穷，是每年w w w 学术年会 的重要论题之一t 。 随着大学校园网建设的蓬勃发展，校内资源日渐丰富，同样的问题也出现 在校园网中。通用搜索引擎如百度、谷歌( g o o g l e ) ( 2 】【3 】虽然都提供了大学搜索 的服务来实现对部分高校校园网范围内的网页搜索，但是其存在一些问题，如 更新周期过长、校园网内有些资源只允许校内m 访问导致的通用搜索引擎不能 抓取等，因此，设计高校信息资源的专业搜索引擎，对于高校信息资源的共享 以及提高信息资源的利用率就显得非常必要。 实验室已经设计开发了一套校园网搜索引擎系统，但是该校园网搜索引擎 系统存在一些问题。例如在搜索器方面，对网页的解析不够完全导致的搜全率 过低，同时校园网中大量存在的w o r d 文档未能实现抓取等问题；检索器方面， 检索结果的网页只能简单的输出而没有考虑排序等。因此，需要对校园网搜索 引擎进行重构，设计实现新版本的校园网搜索引擎。 1 2 研究状况 1 9 9 3 年，i n t e r n e t 上出现了最早的w e b 浏览器m o s a i c ，次年n e t s c a p e 推 第一章引言 出了n a v i g a t o r ，浏览器的发展促使w e b 得到迅速推广，同时也推动着搜索引擎 的发展。1 9 9 4 年初，i n t e r n e t 上出现了包括l y c o s 在内的第一批w 曲搜索引擎， 同年还成立了y a h o o ! ，后者成为了近年来最成功的商业目录。 目前，搜索引擎技术相关领域的学术研究得到了大学和科研机构的重视。 如s t a n f o r d 大学在其数字图书馆项目中开发了g o o g l e 搜索引擎，在w e b 信息的 高效搜索、文档的相关度评价、大规模索引等方面作了深入的研究，取得了很 好的成果。国内先后有北京大学、清华大学、国家智能研究中心等高校和研究 单位对搜索引擎技术开展研究，并开发出了几个较好的系统。 搜索引擎按其工作方式主要可分为三种【4 】【5 1 ，分别是全文搜索引擎( f u l lt e x t s e a r c he n g i n e ) 、目录索引类搜索引擎( s e a r c hi n d e x d i r e c t o r y ) 和元搜索引擎 ( m e t as e a r c he n g i n e ) 。 ( 1 ) 全文搜索引擎 全文搜索引擎是名副其实的搜索引擎，国外具代表性的有g o o g l e 、 f a s t a l l t h e w e b 、a l t a v i s t a 、i n k t o m i 、t e o m a 、w i s e n u t 等，国内著名的有百度 ( b a i d u ) 。它们都是通过从互联网上提取的各个网站的信息( 以网页文字为主) 而建立的数据库中，检索与用户查询条件匹配的相关记录，然后按一定的排列 顺序将结果返回给用户，因此他们是真正的搜索引擎。从搜索结果来源的角度， 全文搜索引擎又可细分为两种，一种是拥有自己的检索程序，俗称“蜘蛛一 ( s p i d e r ) 程序或“机器人一( r o b o t ) 程序，并自建网页数据库，搜索结果直接 从自身的数据库中调用，如上面提到的七家引擎；另一种则是租用其他引擎的 数据库，并按自定的格式排列搜索结果，如l y c o s 引擎。 ( 2 ) 目录索引 目录索引虽然有搜索功能，但在严格意义上算不上是真正的搜索引擎，仅 仅是按目录分类的网站链接列表而已。用户完全可以不用进行关键词 ( k e y w o r d s ) 查询，仅靠分类目录也可找到需要的信息。目录索引中最具代表 性的莫过于大名鼎鼎的y a h o o ! 。其他著名的还有o p e nd i r e c t o r yp r o j e c t ( d m o z ) 、i x ) o k s m a r t 、a b o u t 等。国内的搜狐、新浪搜索也都属于这一类。 ( 3 ) 元搜索引擎 元搜索引擎在接受用户查询请求时，同时在其他多个引擎上进行搜索，并 将结果返回给用户。著名的元搜索引擎有i n f o s p a c e 、d o g p i l e 、v i v i s i m o 等，中 文元搜索引擎中具代表性的有搜星搜索引擎。在搜索结果排列方面，有的直接 2 第一章引言 按来源引擎排列搜索结果，如d o g p i l e ，有的则按自定的规则将结果重新排列组 合，如v i v i s i m o 。 除上述三大类引擎外，还有以下几种非主流形式： 集合式搜索引擎：如h o t b o t 在2 0 0 2 年底推出的引擎。该引擎类似元搜索引 擎，但区别在于不是同时调用多个引擎进行搜索，而是由用户从提供的4 个引 擎当中选择，因此叫它“集合式搜索引擎更确切些。 门户搜索引擎：如a o ls e a r c h 、m s ns e a r c h 等虽然提供搜索服务，但自身 既没有分类目录也没有网页数据库，其搜索结果完全来自其他引擎。 免费链接列表( f r e ef o r a l ll i n k s ，简称f f a ) ：这类网站一般只简单地滚动 排列链接条目，少部分有简单的分类目录，不过规模比起y a h o o 等目录索引来 要小得多。 从出现第一个搜索引擎至今，搜索引擎技术已经获得了飞速的发展，现在 的搜索引擎功能越来越强大，提供的服务也越来越全面，它们的目标不仅仅是 提供单纯的查询功能，而是把自己发展成为用户首选的i n t e r n e t 入口站点。目前 的搜索引擎主要有以下几个主要特点吼 ( 1 ) 多样化和个性化的服务 现在绝大多数搜索引擎都是提供多样化的服务，以吸引更多的用户，商业 搜索引擎尤其注重这一点。以y a h o o ! 为例，用户可以从它的首页中查看新闻、 金融证券、天气预报等信息，还可以进行网上购物、拍卖、或者使用e m a i l 等服 务。可以说多样化和个性化的服务既满足了用户更多的需求，也为搜索引擎网 站带来了更多的利润。 ( 2 ) 强大的查询功能 与最早的搜索引擎相比，现在的搜索引擎在查询功能方面已有了很大的改 进。除了简单的a n d 、o r 、和n o t 逻辑外，不少搜索引擎还支持相似查询， 例如a l t av i s t a 、l y c o s 等支持短语查询，a l t av i s t a 的高级搜索功能支持n e a r 逻辑等。 ( 3 )目录和基于r o b o t 的搜索引擎相互结合 耳录和基于r o b o t 的搜索引擎都具有自己的特点，在当前的技术条件下，最 好的选择是将两种技术进行结合，同时为用户提供这两种类型的服务。以y a h o o ! 为例，用户可以进行分类网站查询也可以进行全部网页查询，这两种不同的查 3 第一章引言 询方式很好的满足了不同用户的需求。 全球领先的数据调查公司c o m s c o r e2 0 0 7 年1 0 月1 0 号发布了一份关于全 球排名前5 0 搜索引擎的使用状况调查报告【6 】。调查结果显示，7 5 亿年龄在1 5 岁以上的网民也就是全球9 5 的网民在2 0 0 7 年8 月份共使用搜索引擎6 1 0 亿次， 平均每人一个月使用搜索引擎超过8 0 次。 全球搜索引擎使用状况按照地区分类，拉丁美洲地区人均使用次数最高， 而中东非洲的人均使用次数最少( 见表1 1 ) 。 表1 1 全球各地区搜索引擎使用状况统计 按地区分类唯一用户( 千)搜索次数( 百万)人均搜索次数 全世界7 5 4 ，4 5 96 1 ，0 3 6，8 0 9 亚太2 5 7 ，9 5 22 0 ，2 9 57 8 7 欧洲 2 0 9 ，6 7 8 1 7 ，8 4 6 8 5 1 北美 2 0 6 ，2 7 81 5 ，9 7 67 7 4 拉丁美洲4 9 ，9 9 5 4 ，7 8 49 5 7 中东非洲3 0 ，5 5 62 ，1 3 46 9 8 全球搜索引擎使用状况按照搜索引擎服务提供商分类，g o o g l e 以超过6 0 的份额高居榜首；其次是y a h o o ! 紧随其后排名第二；百度虽然目前主要面向中 国用户提供服务，但是其排名已经超过面向全球提供服务的微软成为老三。t o p 1 0 中的其余搜索引擎详见表1 2 。 表1 2 全球搜索引擎使用次数排行前十位统计情况 搜索引擎 全球 g o o g l e y a h o o ! 百度 微软 n h n e b a y 时代华纳 搜索次数( 百万) 6 1 ，0 3 6 3 7 ，0 9 4 8 ，5 4 9 3 ，2 5 3 2 ，1 6 6 2 ，0 4 4 1 ，3 1 9 l ，2 1 2 4 洲嗽册蝴姒踹蹴砒 l，l ， -，l、，胁姗觎m”扒” 第一章引言 a s k 福克斯 l y c o s 7 4 3 6 8 3 4 4 1 1 2 2 1 1 2 o 7 2 从以上两个表中可以看出，虽然搜索引擎已经为用户提供了快捷和便利的 服务，但是应用仍然不够广泛，一方面全球人均每天搜索不足三次，另一方面， 百度作为中文搜索的领头羊，在使用中文上网的人数基数很大的情况下，份额 仅为5 3 3 。所以，搜索引擎技术，尤其是中文搜索的发展任重而道远。 1 3 论文结构 本文主要对搜索引擎的原理、结构、工作流程以及搜索引擎用到的主要数 据结构做了详细的分析和研究，针对旧版本校园网搜索引擎出现的问题和不足， 对搜索器和检索器技术重新进行了设计和实现，并对索引器做了一些修改来适 应新版本校园网搜索引擎的要求。内容安排如下： 第二章首先研究搜索引擎的基本组成、工作流程以及其关键技术；然后介 绍校园网搜索引擎与通用的搜索引擎的区别，并分析了校园网搜索引擎的基本 组成原理和工作流程；最后分析了旧版本校园网搜索引擎存在的问题并提出修 改方案，同时重新设计了子系统之间的共享接口。 第三章分析研究搜索引擎中的重要部分搜索器技术，对用到的相关协议、 搜索方法及搜索策略进行了详细分析，针对旧版本搜索器子系统出现的问题， 重新设计了搜索器相关技术和组件，并给出了相关实验及分析。 第四章介绍搜索引擎中的信息预处理部分一中文分词和索引技术，其中中 文分词部分借用旧版本的分词子系统，因此只按照分词步骤对词典机制、未登 录词识别和分词算法进行了介绍和分析；索引方面，为了适应新版本检索器中 的排序算法，对索引的结构做了一些修改。 第五章介绍信息查询服务，首先介绍了信息查询的过程；然后详细介绍网 页的排序算法，并在t f i d f 算法的基础上，结合页面版式和网页层次两方面， 设计了新的网页排序算法；最后介绍并设计了查询结果的显示。 第六章介绍校园网搜索引擎的软件实现，重点介绍实现过程中的蜘蛛程序 的关键技术和组件以及检索系统的实现。 最后为全文总结，并对需要进一步研究和解决的技术问题做了展望。 5 第二章校园网搜索引擎 第二章校园网搜索引擎 本文主要针对全文检索搜索引擎进行介绍，下文提到的搜索引擎如果没有 特殊说明也是指全文检索搜索引擎。 2 1 通用搜索引擎 2 1 1 搜索引擎介绍 搜索引擎【8 l ( s e a r c he n g i n e ) 实际上是个专用的网络服务器，它存有庞大的索 引数据库，收集了全世界成千上万网页的文字信息。为了收集这些信息，网络 蜘蛛通过给定的一些地址链接，利用h t t p ( 超文本传输协议) 等标准协议读取 相应文档，然后以文档中包括的所有未访问过的地址链接作为新的起点，继续 进行漫游，直到没有满足条件的新地址链接为止。然后为这些主页上的文字建 立索引并送回集中管理的索引数据库。索引信息包括文档的链接地址，每个文 档中词语出现的频率、位置等。 搜索引擎的技术基础是全文检索技术，从2 0 世纪6 0 年代，国外对全文检 索技术就开始有研究。全文检索通常指文本全文检索，包括信息的存储、组织、 表现、查询和存取等各个方面，其核心为文本信息的索引和检索，一般用于企 事业单位。随着互联网信息的发展，搜索引擎在全文检索技术上逐渐发展起来， 并得到了广泛的应用，但搜索引擎还是不同于全文检索。搜索引擎和常规意义 上的全文检索主要区别有以下几剧9 】： ( 1 ) 数据量 传统全文检索系统面向的是企业本身的数据或者和企业相关的数据，一般 索引库规模多在级，数据量大的也只有几百万条但互联网网页搜索需要处理几 十亿的网页，搜索引擎的策略都是采用服务器群集和分布式计算技术。 ( 2 ) 内容相关性 信息太多，查准和排序就特别重要，g o o g l e 等搜索引擎采用网页链接分析 技术，根据互联网上网页被链接次数作为重要性评判的依据但全文检索的数据 源中相互链接的程度并不高，不能作为判别重要性的依据，只能基于内容的相 6 第二章校园网搜索引擎 关性排序。 ( 3 ) 安全性 互联网搜索引擎的数据来源都是互联网上公开的信息，而且除了文本正文 以外，其它信息都不太重要但企业全文检索的数据源都是企业内部的信息，有 等级、权限等限制，对查询方式也有更严格的要求，因此其数据一般会安全和 集中地存放在数据仓库中以保证数据安全和管理的要求。 ( 4 ) 个性化和智能化 搜索引擎面向的是互联网访问者，由于其数据量和客户数量的限制，自然 语言处理技术、知识检索、知识挖掘等计算密集的智能计算技术很难应用，这 也是目前搜索引擎技术努力的方向，而全文检索数据量小、检索需求明确，在 智能化和个性可走得更远。 2 1 2 搜索引擎组成及工作流程 搜索引擎系统一般由蜘蛛( 搜索器) 、分词器、索引器、检索器几部分组成 【l o 】。蜘蛛负责网页信息的抓取工作，一般情况下分词器和索引器一起使用，它 们负责将抓取的网页内容进行分词处理并自动进行标引，建立索引数据库。检 索器根据用户查询条件检索索引数据库并对检索结果进行排序和集合运算，如 并集、交集运算，再提取网页简单摘要信息反馈给查询用户 现代大规模高质量搜索引擎一般采用如图2 1 所示的称之为三段式的工作 流程，即：网页搜集、预处理和查询服务【l 】。 图2 1 搜索引擎三段式工作流 搜索引擎组成中介绍的蜘蛛( 搜索器) 完成三段式工作流程中的网页搜集， 分词器和索引器完成预处理功能，查询服务由检索器完成。 g o o g l e 搜索引擎从功能上同样分为三大部分：网页爬行、标引入库和用户 查询。网页爬行主要负责网页的抓取，由u r l 服务器、搜索器、存储器、分析 器和u r l 解析器组成，搜索器是该部分的核心；标引入库主要负责对网页内容 进行分析，对文档进行标引并存储到数据库里，由标引器和分类器组成，该模 块涉及许多文件和数据，有关于桶的操作是该部分的核心；用户查询主要负责 7 第二章校园网搜索引擎 分析用户输入的检索表达式，匹配相关文档，把检索结果返回给用户，由查询 器和网页级别评定器组成，其中网页等级的计算是该部分的核心。 2 1 3 搜索引擎的关键技术介绍 信息收集： 网上信息收集和存储一般分为人工和自动两种方式【1 1 1 【1 2 】。人工方式采用传 统信息收集、分类、存储、组织和检索的方法。研究人员对网站进行调查筛选、 分类、存储。由专业人员手工建立关键字索引，再将索引信息存入计算机相应 的数据库中。自动方式通常是由搜索程序来完成的。搜索程序( 如：r o b o t 、s p i d e r ) 是一种自动运行的软件，其功能是搜索i n t e r n e t 上的网站和网页。这种软件定期 在i n t e r n e t 上漫游，通过网页之间的链接，顺序地搜索新的地址。当遇到新的网 页时，就给该页上的某些字或者全部字作上索引并把它加到搜索引擎数据库中， 由此，搜索引擎的数据库得以定时的更新。一般说来，人工方式收集信息的准 确性要优于搜索程序，但是其收集信息的效率及全面性远远低于搜索程序。信 息的存储则根据不同的分析结果和要求，针对提取的索引和查询的目的而进行 的。可以采用专用的，也可以采用通用的数据库。 信息预处理： 中文搜索引擎的预处理包括中文分词技术和索引技术。 中文搜索引擎和英文的搜索引擎最大的区别就是中文分词部分，这是因为 英文单词之间都是用空格隔开，能够非常清晰的辨别出需要搜索的关键字的意 义，而中文是以字为单位，字与字连接起来才能清楚地描述一个意思，因此在 中文搜索引擎中，中文分词占有很重要的地位，只有分词正确才能比较准确地 返回用户查询希望得到的结果f 1 3 1 。 ， 索引库的建立也是信息预处理阶段非常重要的技术，合理的索引机制能极 大的提升搜索引擎系统的性能。 提到索引，就使人联想到数据库系统。但它并不满足搜索引擎的特殊要求。 首先，搜索引擎面对的是海量数据。按照前面提供的数据，大型的商业搜索引擎一 般都索引几千万个网页，有些甚至到几个亿。如此大型的数据量，使得数据库系统 很难有效的管理。其次，搜索引擎使用的数据操作简单，一般而言，只需要增、删、 8 第二章校园网搜索引擎 改、查几个功能，而且数据都有特定的格式，可以针对这些应用设计出简单高效的 应用程序。而一般的数据库系统则支持大而全的功能，同时损失了速度和空间。 最后，搜索引擎面临大量的用户检索需求，这要求搜索引擎在检索程序的设计上 要分秒必争，尽可能的将大运算量的工作在索引建立时完成，使检索运算尽量的 少。一般的数据库系统很难承受如此大量的用户请求，而且在检索响应时间和检 索并发度上都不及专门设计的索引系统。 索引器的功能是处理分词所得到的信息，从中抽取出索引项，将半结构化 的数据转换成方便检索的结构化的数据，用于表示网页以及生成网页库的索引 表【1 4 1 。索引是检索与数据的接口，是加快检索的有效方式，因此索引的好坏直 接影响到整个搜索引擎性能的好坏。常用的文本索引形式有三类，分别是倒排 文件、后缀数组和签名档【1 4 1 。一个搜索引擎可以选用上述任何一种形式的索引 结构。后缀数组是后缀树的一种有效的空间实现，这种类型的缺点是构建过程 的开销较大，并且查询的结果不能以在文本中的位置顺序地提交；签名档是基 于散列变换的面向单词的索引结构，它以在索引上顺序检索为代价，这种技术 适应于不太大的文本，在大多数应用程序中，倒排索引的效果要比签名档好。 倒排索引广泛地用于支持高效地大网页集的检索。所谓倒排索引机制，是一种 面向词语的索引机制，其结构由词汇和出现情况两部分组成。对于每个词语， 都有一个列表来记录单词出现的网页及其它相关属性，利用它可以提高网络检 索速度。 目前，基于全文检索系统的倒排索引的创建分为基于词或字。以单个汉字 为单位建立索引的字表法是将原始网页中的每个字的位置信息记录在索引库 中；而以词语为单位建立索引的词表法则是以词为单位将其位置信息记录在索 引库中。单汉字索引技术不用对网页分词，具有高召回率，但是会返回很多无 用的信息，降低了精确率，除此以外，付出了检索速度的降低和索引存储空间 的增大的代价；词语索引需要对原始网页进行分词处理，因而适用特定领域中 内容相对固定的网页全文检索，其优点是对于大规模应用，索引库可以组织得 比较小，检索处理速度也比较快，但在分词中需要做一定的工作。本课题的索 引器是构建在基于词语的倒排索引结构，同时需要借助其它数据库来存放顺排 档数据。 在网络检索环境下，搜索引擎索引数据量和用户量都不断增加，从而使得 优化倒排索引的结构、改进检索算法、不断提高系统检索效率成为一个引人关 9 第二章校园网搜索引擎 注的研究课题。 搜索服务： 检索器是搜索引擎系统中最后一个环节，是最终和用户打交道的用户搜索 界面。搜索的处理过程是对用户的搜索请求进行满足的过程，通过w e b 页接受 用户输入的搜索字符串，对搜索字符串进行分词后得到查询关键词，搜索服务 器对应关键词字典，访问倒排档索引文件检索出所有符合检索条件的文档，并 对其进行并集运算和排序运算，最后得到最终的结果文档，再从各文档中提取 摘要信息写入用户反馈网页中。 2 2 校园网搜索引擎 2 2 1 校园网搜索引擎与通用搜索引擎的区别 校园网可以看作以学校为单位的内联n ( i n t r a n e t ) ，它与互联网( i n t c m c t ) 是同 质的。但是由于应用环境、网站构建以及链接结构方面的不同，对搜索引擎来 说，校园网与公用互联网有着多方面的区别。 ( 1 )搜索范围与数量 通用的搜索引擎需要对整个互联网( i n t o n e t ) 进行抓取并将搜索的结果处 理后为用户提供搜索；而校园网搜索引擎是基于校园网的，只需要对校园网中 的网页进行抓取，提供给用户查询的内容同样也都是属于校园网中的网页( 资 源) ，这就导致了处理的数据量差别巨大。 ( 2 )目标网站的分布与结构 互联网搜索引擎抓取的目标为所有存在的网站，网站的多样性导致了网站 结构的多样性；而校园网网站般集中在一个或几个口地址段内，网站之间的 链接稀疏，由于分别由不同机构和个人进行维护和管理，有些网站很难从其它 网站的链接到达，同时网站的重要性与网站规模不成正比，例如新闻和论坛类 网站的网页数量多并且链接较密，而教学和管理部门的网站则相反。大部分网 站由各院系的网络信息中心或网站管理员进行维护，网页的发布需要经过较严 格的审核，发布的内容具有权威性和真实性，区别于互联网的商业行为。同时 校园网网站往往不使用交换链接等方式以获得商业利益，使得网页之间的链接 1 0 第二章校园网搜索引擎 较少。 ( 3 )w o r d 等异构文本格式的网页比例高 互联网上常见的网页通常有静态网页( 文件后缀为h t m 、h t m l 、s h t m l 等) 、 动态网页( 文件后缀为a s p 、j s p 、p h p 等) 以及各种文档( 文件后缀为d o e 、p d f , p p t 等1 。我们把d o e 、p d f 、p p t 等类型的文件称为异构文本。校园网中通常包含 w o r d 格式的通知等以及图书馆、论文等各种学术资源，这些信息通常都是以异 构文本的形式发布的，这是校园网资源的显著特点。 ( 4 )用户群及查询习惯 通用搜索引擎的用户为全部的网民，所以查询往往没有特别明确的主题， 对同一个查询词，有几十或成百上千个相关的返回结果。搜索引擎可以通过链 接分析等技术把“权威 的网页排在靠前位置，得到令用户满意的查询结果。 而校园网的用户通常为在校师生，一般具有明确的查询预期，例如某个专业的 招生计划、某个教授的个人资料等。正确的搜索结果通常没有明显的特点，通 常不是被众多链接指向的“权威一网页。因此在排序算法中需要更多考虑相关 度的分析和比较。 2 2 2 校园网搜索引擎的基本原理 校园网搜索引擎采用浏览器服务器体系结构( b s ) 。它由四个子系统组成， 即搜索器、中文分词器、索引器和检索裂1 y i 1 6 1 。其中搜索器，中文分词器和索 引器三个子系统必须首先运行，为用户检索准备结构化的数据。 校园网搜索引擎的工作流程( 如图2 2 所示) ，分为两个阶段。 阶段一：数据准备。首先搜索器从校园网的主页开始，将网页信息( 包括 文本，图片等，目前只处理文本数据) 采集到数据库中；然后由中文分词器对 上一步采集到的文本进行分词，为索引器提供数据；接下来由索引器对分词信 息进行索引，为检索器提供结构化数据源。至此，一次数据准备结束。 校园网搜索引擎必须根据一定的时间规则进行数据准备，这样才能保证用 户检索到的信息是最新的。校园网搜索引擎在首次运行时将处理大量的数据， 但是在以后的运行中将进行增量式的数据处理，处理数据相对较少。 阶段二：数据查询。当数据准备好后，用户就可以通过用户接口进行查询， 当检索器接到用户的请求时，首先将查询内容进行分解，然后将关键词提交检 索，检索器使用索引器提供的接口对准备好的数据进行检索，最后将结果返回 第二章校园网搜索引擎 给用户。 网页 q t - 壹淘用户 雾囊黧：辩媾 豁酾 鬓辩秘 j一 搜索器 中文自动分词 t - l i 蔟引 i 卜 l i i i i 图2 2 校园网搜索引擎的工作流程 胃l 胃l 孵1 臌2 藤l 髓l ：l ： 索引 检 索 器 瞳 _ 2 2 3 旧版本校园网搜索引擎存在的问题及改进方案 经过分析研究，发现旧版本的校园网搜索引擎系统存在一些问题。例如在 搜索器方面，存在对网页的解析不够完备而导致的搜全率过低，校园网中大量 存在的w o r d 文档未能实现抓取等问题；检索器方面，检索结果的网页只能简 单的输出而没有考虑排序等。因此，在新版本的校园网搜索引擎中需要重新设 计实现搜索器子系统和检索器子系统，需要重新设计的地方主要包括：重新设 计网络蜘蛛程序与搜索器接口，其中为了提高效率新版本设计两种队列类来适 应不同的需求( 等待队列与其余队列的操作不同) ，同时设计d n s 缓存，避免 了与服务器连接时频繁的向d n s 服务器请求解析域名导致的拒绝服务，重新设 计解析模块以提高对网页中u r l 的提取能力，增加对异构文件( w o l m 文档) 的解析功能等；检索器方面设计了基于t f i d f 算法并综合考虑页面版式和网页 层次因素的新算法，在网页排序时能较准确的反映了网页的权值，实现检索结 果的排序输出；同时为了适应新的排序算法，需要重新设计索引结构以提供算 1 2 第二章校园网搜索引擎 法需要的数据。 2 2 4 新版校园网搜索引擎系统的接口设计 系统接口采用数据库方式实现数据共享。数据库名为：s ed a t a 。表2 1 是系统共享表结构的定义。 说明： l 、本表是整个系统的共享表，通过d o , c i d 实现表间互连。由搜索子系统进 行数据插入。 2 、通过u p d a t e f l a g 可以实现数据的增量扩充。预定义三个状态： b e i n d e x e d ：b e m o d 巧i e d ：b e s e g m e n t e d ： 表2 1a d d r c o d e 表的结构图 序号字段名 字段类型 是否为空 是否为主键 ld o c i dd 兀e g e r否 是 2a d d r e s s v a r c h a r 2 ( 2 0 0 ) 否 否 3 u p d a t e f l a g 巧r i e g e r否 否 状态图变化如图2 3 所示： i n e w d o c f 上搜索器 i b e m o d i f i e d 中文分词 r i b e s e g m e n t e 索引器 r b e 口d e x e d 图2 3u p d a t e f l a g 状态变化图 1 3 第二章校园网搜索引擎 2 3 本章小结 本章第一部分首先介绍了通用搜索引擎的相关知识，然后对搜索引擎的组 成及工作流程做了简要陈述，最后从宏观上介绍了搜索引擎的三项关键技术。 第二部分从校园网搜索引擎与通用的搜索引擎的区别入手，讨论了建立校 园网搜索引擎的必要性，然后介绍了校园网搜索引擎的基本原理和工作流程， 最后分析了旧版本校园网搜索引擎存在的问题并提出修改方案，同时重新设计 了子系统之间的共享接口。 在此后的三章中，将按三段式的工作流程分别对网页搜集、抓取信息预处 理和网页信息的查询服务进行分析、研究和设计 1 4 第三章网页搜集 3 1 超文本传输协议 第三章网页搜集 h ，r r p ( h y p e rt e x tt r a n s f e rp r o t o c 0 1 ) 是超文本传输协议【1 7 】的缩写，它用于 传送w w w 方式的数据。h t r p 协议采用了请求响应模型。客户端向服务器发 送一个请求，请求头包含请求的方法、u r i 、协议版本、以及包含请求修饰符、 客户信息和内容的类似于m i m e 的消息结构。服务器以一个状态行作为响应， 相应的内容包括消息协议的版本，成功或者错误编码加上包含服务器信息、实 体元信息以及可能的实体内容。h t t p 是建立在t c p i p 之上的协议，同时也是 一种套接字协议，事实上w e b 就是建立在h t t p 之上的协议。要从w e b 上抓取 网页，也就是通过h t i p 协议与w e b 服务器之间进行数据通信，所以在研究网 页抓取技术之前要对用到的h t t p 协议做一个简要介绍。 1 h t t p 请求行 一个请求由请求行、可选个数的请求首标和一个空行组成，使用p o s t 方法 时还允许有一些附加数据。请求行格式如下： 请求方法u r ih t r p 版本号 请求方法是一个单词，通常使用的h t r p l 0 中使用g e t 、h e a d 与p o s t 这几种请求方法。不过现在越来越多的服务器开始支持h t t p l 1 的p u t 、 d e l e t e 、o p t i o n s 、t r a c e 等方法。统一资源标识u r i c u n i f o r mr e s o u r c e i d e n t i f i e r ) 只是所请求的u r i ，剥去了写一部分、主机名( 如w w w g o o g l e c o r n ) 、 端口号( 如h t t p ：w w w g o o g l e c a ) m ：8 0 8 0 中的“8 0 8 0 ) 。 下面详细介绍三种标准的h t f p l 0 请求方法g e t 、h e a d 和p o s t 。 ( 1 )g e t g e t 方法就是以实体方式得到由请求u r i 所指定资源的信息。如果请求u r l 只是一个数据产生过程，那么最终要在回应实体中返回的是由该处理过程的结 果所指向的资源，而不是返回该处理过程的描述文字，除非那段文字恰好是处 理的输出。 如果请求消息包含i f - m o d i f i e d s n e e 标题域，g e t 方法的语法就变成“条件 g e t 一，即“( c o n d i t i o n a lg e t ) 。条件g e t 方法可以对指定资源进行判断，如 1 5 第三章网页搜集 果它在i f - m o d i f i e d - s i n c e 标题域中的指定日期后发生了更新，才启动传输，否则 不传输。这种条件g e t 允许被缓存的实体在不必经过多次请求或不必要的数据 传输就能进行刷新，从而有助于降低网络负载。 ( 2 ) h e a d h e a d 方法与g e t 几乎一样，区别在于，h e a d 方法不让服务器在回应中 返回任何实体。对h e a d 请求的回应部分来说，它的h t t p 标题中包含的元信 息与通过g e t 请求所得到的是相同的。通过使用这种方法，不必传输整个实体 主体，就可以得到请求u r i 所指定资源的元信息。该方法通常用来测试超链接 的合法性、可访问性及最近更新。与条件g e t 不同，不存在所谓盱条件h e a d 一， 即一c o n d i t i o n a lh e a d 什。即使在h e a d 请求中指定i f o m o d i f l e d - s i n c e 标题域，它 也会被忽略。 ( 3 )p o s t p o s t 方法用来向目的服务器发出请求，要求它接受被附在请求后的实体， 并把它当作请求队列( r e q u e s t - l i n e ) 中请求u r i 所指定资源的附加新子项。p o s t 被设计成用统一的方法实现下列功能： 对现有资源的注释( a n n o t a t i o no f e x i s t i n gr e s o u r c e s ) ； 向电子公告栏、新闻组，邮件列表或类似讨论组发送消息； 提交数据块，如将表格的结果提交给数据处理过程； 通过附加操作来扩展数据库。 p o s t 方法的实际功能由服务器来决定，而且通常依赖于请求u r i 。在p o s t 过程中，实体是u r i 的从属部分，就好象文件从属于包含它的目录、新闻组文 件从属于