（计算机应用技术专业论文）全文检索在“2008奥运多语言系统”中的应用研究与实现.pdf

摘要 摘要 全文检索是现代信息检索技术的一个非常重要的分支，它是处理非结构化数 据的强大工具，也是搜索引擎的核心技术之一本文对中文全文检索的有关技术 进行了较为深入的研究。在基于字表的全文索引方面，本文提出了一种改进的倒 排索引结构，同传统索引结构相比，更便于索引的构建、维护、更新。并根据其 特征，设计了优化的查询策略。分析比较的结果表明，改进的索引结构在获得较 高的动态性能的同时，还能有效地提高创建索引的速度。本文的重点放在了全文 检索技术的应用上，对如何利用新技术、改善检索系统的结构、提高检索系统的 性能和效率、加快检索速度、不断适应网络信息发展等方面做了重点研究。 全文检索是一种i o 密集型的应用，以往的全文检索系统的开发多在关系数 据库的基础上进行。本文针对全文数据库的特点，深入讨论此法弊端与不足，并 提出了在文件系统上构建的解决方案。由于目前全文检索系统的开发平台并不多 见，本文介绍了一种全文检索引擎工具包l u c e n e ，它功能强大，小巧精悍，便于 嵌入各种应用。近年在世界各地被广泛使用，诸如等公司都使用其核心代码。作 为一个开源软件，它为我们学习搜索引擎的核心技术提供了绝佳的机会，对其剖 析研究、进行二次开发，是一件很有意义的事情。 在应用方面，本文主要工作是奥运多语言系统中全文检索子系统的设计与实 现。就检索的效率和效果而言，基本达到了最初的设计目的。 关键词全文检索；单汉字标引；倒排文件；l u c e n e ；全文数据库 a b s t r a c t a b s t r a c t f u l l - t e x tr e t r i e v a li sa l li m p o r t a n ti n f o r m a t i o nr e t r i e v a lt e c h n o l o g y i ti sa p o w e r f u lt o o lf o rd e a l i n gw i t hn o n s t r u c t u r a ld a t a , a n di so n eo f t h ek e yt e c h n o l o g i e s o ft h es e a r c h e n g i n e t h i sp a p e rd e e p l yr e s e a r c h o nc h i n e s ef u l l - t e x t r e t r i e v a l t e c h n o l o g y i nt h ef i l e do ff u l l - t e x ti n d e xb a s e do nw o r di n v e r t e dt a b l e ，ai m p r o v e d w o r d - b a s e dc h i n e s ei n v e r t e di n d e xs t r u c t u r ei s p r o p o s e dw h i c hh a s ab e t t e r p e r f o r m a n c et h a nt r a d i t i o n a la p p r o a c h e s ，a n dc o n v e n i e n tf o rc o n s t r u c t i n g , m a i n t a i n i n g a n du p d a t i n gi n d e x a c c o r d i n gt oi t sc h a r a c t e r i s t i c , w ed e s i g ni t sc o r r e s p o n d i n g o p t i m i z e ds e a r c hm e t h o d a n a l y s i ss h o w st h a tb e t t e rd y n a m i cp e r f o r m a n c ea n dh i g h i n d e x i n gs p e e di sp o s s i b l eu s i n gt h i ss t r u c t u r e t h i sp a p e rp a y sm o r ea t t e n t i o ni n a p p l i c a t i o no ff u l l t e x tr e t r i e v a lt e c h n o l o g i e s h o wt ou s e n e wt e c h n i q u e , o p t i m i z et h e s t r u c t u r eo fr e t r i e v a ls y s t e m , i m p r o v ep e r f o r m a n c ea n de f f c i e n c y , q u i c k e ns e a r c hs p e e d a n da d a p tt h ed e v e l o p m e n to fc u r r e n tw e bi sa l s od i c u s s e di nt h i sp a p e r f u l l - t e x tr e t r i e v a li sa l li oi n t e n s i v ea p p l i c a t i o n i t sp r e v i o u sd e v e l o p m e n t sa l e c a r r i e do nt h eb a s i so fr e l a t i o nd a t a b a s e t h i sp a p e rd e e p l yd i s c u s s e st h ea b u s ea n d d e f i c i e n c yo ft h i sm o d ea c c o r d i n gt o i t sc h a r a c t e r i s t i c b e c a u s et h ed e v e l o p m e n t p l a t f o r mo ff u l l t e x tr e t r i e v a li s a b s e n tc u r r e n t l y ，l u c e n e ，af u l l - t e x ts e a r c he n 舀n e t o o l k i t ，i si n t r o d u c e di n t ot h ep a p e r i th a sp o w e r f u lp e r f o r m a n c ea n di t sb o d yi s c a b i n e t ，c a p a b l e a n dv i g o r o u s ，t h i sc o n v e n i e n tf o ri te m b e d d e da p p l i c a t i o n s a t p r e s e n t ，l u c e n ei se m p l o y e dw o r l da b r o a d ，s ot h a tm a n yp r o f e s s i o n a lc o m p a n i e ss u c h a sm ma l s ou s ei t sc o r ec o d e a sa no p e ns o u r c ec o d es o i l l u c e n eo f f e ra s u p e r e x c e l l e n tc h a n c et os t u d ys e a r c he n g i n ek e yt e c h n o l o g y i ti sw o r t h f u lt ot a k ea p a r s er e s e a r c ha n dc a r r ys e c o n dd e v e l o p m e n tt oi t i nt h ea p p l i c a t i o na s p e c t ，t h i sp a p e rw o r km o s t l yi nt h ed e s i g na n di m p l e m e n to f t h em u l t i - l a n g u a g es y s t e m a sf o rt h er e t r i e v a lr e s u l t s ，t h es y s t e ma c c o m p l i s hp r i m a l d e s i g nt a r g e to nt h ew h o l e k e yw o r d s f u l l t e x tr e t r i e v a l ；s i n g l ec h i n e s ec h a r a c t e ri n d e x i n g ；l u c e n e ； i n v e r t e df i l e ；f u l l t e x td a t a b a s e l i l 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：查! 壶日期：盈趋2 ：玉。廖 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：2 垒牡导师签名： 日期：迎仝! 至。，留 第1 章绪论 第1 章绪论 1 1 前言 万维网( w o r l dw i d ew e b ，w w w ) 是指在因特网上以超文本为基础形成的 信息网。万维网为用户提供了一个可以浏览的图形化界面，用户通过它可以查阅 i n t e m e t 上的信息资源。w w w 是通过互联网获取信息的一种应用，我们所浏览 的网站就是w w w 的具体表现形式，但其本身并不就是互联网，万维网只是互 联网的组成部分之一。互联网常用的服务包括：w w w 、e m a i l 、f t p 、u s e n e t 、i m 在盘 号手。 互联网近些年来在中国也得到了迅猛的发展，根据中国互联网络信息中心 ( c n n i c ) 在北京发布的第2 1 次中国互联网络发展状况统计报告显示，截止 到2 0 0 8 年1 月1 7 日，中国网民已经达到2 1 亿，接近美国的2 1 5 亿。与去年同 期相比，中国网民人数增加了2 6 0 0 万人，是历年来网民增长最多的一年，增长 率为2 3 4 。c n n i c 认为，1 0 的网民普及率将是互联网发展的高速拐点，突破 1 0 之后，中国互联网将迎来更快速的增长期。 报告同时显示，宽带上网的网民超过1 5 亿，占网民总数的7 5 9 。手机上 网达到1 7 0 0 万人，占网民数的8 。在中国5 9 4 0 万台上网计算机中，通过宽带 接入互联网的计算机数为4 1 2 0 万台，中国使用宽带上网的计算机数在全部上网 计算机中所占比例达6 9 4 。中国互联网步入高速增长的宽带时期。 w o r l dw i d ew e b 的发明人t i m o t h yb e m e r s l e e 曾预言，“将来，像出租车、 办公桌甚至地铁车厢都可能成为电脑屏幕，人们可以真正实现随时随地接入互联 网。 b e r n e r s l e e 为我们描绘出了这个神奇的未来世界：“如果你想预订一趟飞 行计划，那么你的带有射频功能的手机便会首先确认你的办公桌面是私密、安全 的，然后便可将航线图、计划就餐的餐馆图像以及其他旅行信息投射到桌面上供 你参考【。 实际上，无论我们怎么想象互联网的未来，无论人们把未来的互联网描绘得 多么天花乱坠，只有一点是至关重要的，那就是未来的互联网是为了让人们的社 会生活彼此联系得越来越紧密，是为了让人类的社会生活日益丰富和美好，除此 之外的任何所谓的未来都只能是虚无飘渺的。 b e r n e r s l e e 之所以和很多热衷于炒作的互联网预言家不同，就在于他深刻 地认识到了这一关键点。他说：“正是人类之间的沟通让我们组成了社会，而w 0 r l d w i d ew 曲的未来就是技术与社会的结合，是电脑和人的结合。” 未来的互联网应该成为我们日常生活中不可或缺的一个部分，是一个能够有 北京工业人学工学硕i j 学位论文 效提升我们生活质量的工具，而不是一个供我们空虚解闷、生产垃圾和邪恶的渊 - 数。 1 2 研究背景 根据中国互联网络信息中，t 二, ( c n n i c ) 最新的调查显示，当前在互联网上的三 大基础应用分别是：搜索引擎、电子邮件、即时通信。在三大基础应用中尤其以 搜索引擎的应用为主【2 1 。 互联网最基础的功能即提供信息。目前互联网上的信息已是海量，搜索引擎 则是网民在汪洋中搜寻信息的工具，是互联网上不可或缺的工具和基础应用之 一。目前2 1 亿网民中使用搜索引擎的比例是7 2 4 ，即已有1 5 2 亿人从搜索引 擎获益，半年净增加3 0 8 6 万人。位列网络应用中网络音乐、即时通信、网络影 视和网络新闻之后的第五位，高于电子邮件。 与其他国家相比，由于中国互联网仍旧是娱乐功能占主体，总体网民的搜索 引擎使用率偏低。在美国，搜索引擎使用率已经达到9 1 。在中国这样一个网 民快速增长和以年轻网民主导的国家，搜索引擎用户将会继续增长。 不同类型的网民使用搜索引擎的比例不同。搜索引擎用户与网民的网龄相关 性很强，网民上网历史越久，则搜索引擎使用率越高，2 0 0 0 年及以前上网的网 民搜索引擎使用率为8 9 1 ，2 0 0 7 年新增网民的使用率仅有4 8 7 。由于2 0 0 7 年中国新增网民很多，新增网民较低的搜索引擎使用率，拉低了总体网民的搜 索引擎使用率，目前7 2 4 的使用率略低于2 0 0 7 年6 月的7 4 8 。 此外，搜索引擎使用率与学历同样存在很强的相关性，学历越高，使用率越 高。初中以下学历的网民搜索引擎使用率为5 4 7 ，硕士及以上学历的网民搜索 引擎使用率则升至9 7 ，几乎人人都使用搜索引擎。 不同地域的网民使用搜索引擎的比例也不相同。上海和北京网民的使用率最 高，均超过8 0 。其他省市中，西部省份的搜索引擎使用率较低，尤其是西藏、 广西和青海。 不使用搜索引擎的网民中，年龄较小的青少年较多，且有8 成以上学历不超 过高中。从这些网民的职业来看，学生、工人和无业者是其中的重要组成部分。 这些人的网络活动也比较单调，对其他网络应用的使用率也低于搜索引擎用户。 随着时间的推移，非搜索引擎用户中的学生等有潜力的人群等将会成为搜索引擎 用户。 因此，从今天来看，我们看到了搜索引擎发生了巨大的变化。第一，它的影 响力空前的大，普及面如此广泛；第二，互联网上的用户对搜索引擎的依赖性越 来越强，某种意思上来说，很少有用户可以完全脱离搜索引擎而方便的使用互联 网；第三，搜索引擎搜索已经发生了一个潜移默化的本质性变化，它不再是一个 第1 币绪论 商业产品了，它已经成为一个半商业产品和半媒体的东西，也就是它已经承担了 相当大部分的社会责任【3 】。 从当前搜索引擎的发展趋势来看，主题搜索引擎目前为主流发展趋势之一。 主题搜索引擎，也称专业搜索引擎、专用搜索引擎、垂直搜索引擎、实时搜索引 擎等，非同于通用搜索引擎，是以构筑某一专题或学科领域的i n t o n e t 网络信息 资源库为目标，智能地在互联网上搜集符合这一专题或领域需要的信息资源，能 够为包括学科信息门户、专业信息机构、特定行业领域、公司信息中心、行业专 家等等在内的信息用户，提供整套的网络信息资源开发方案。是搜索引擎发展史 上的一块里程碑。主题搜索引擎保证了对某一领域信息的完全收录和及时更新， 避免了搜索时强大的“噪音 ，提高了查询效率。在提供专业信息方面有着其它 检索工具无可比拟的优势【4 1 。 1 3 论文的选题和应用意义 1 3 1 论文的选题 首都信息发展股份有限公司( 以下简称“首信公司) 是2 0 0 8 北京奥运会赞 助商，“2 0 0 8 奥运多语言综合信息服务系统( 以下简称“多语言系统 ) 是首信 公司向北京奥运会提供的自主开发的信息服务平台系统，该项目是国家自然科学 基金项目，并被评为“奥运十大科技攻关项目 之一，运用了当前信息系统开发 的多种主流技术。“多语言系统 在系统架构设计上，由多个子系统采用分布式 的方式集成，并提供服务。本课题基于子系统之一的“2 0 0 8 奥运综合数据库查 询系统中的搜索引擎模块，在应用当前主流开源搜索引擎技术的基础上，进行 二次整合，致力于打造具有前瞻性的多语言搜索技术。这个课题得到了“多语言 系统主题的资助，由首信公司技术支持中心提供了科研环境和设备。 1 3 2 应用意义 由于本课题应用的特殊性，非同于通用互联网搜索引擎，主要针对“2 0 0 8 奥运综合数据库查询系统 中的数据信息进行查询，查询范围局限于该系统内的 数据信息，由于搜索范围的大大减小，进行了限定，从而给研究工作中搜索范围 的难度问题提供了很好的解决方案，而不同于通用搜索引擎以整个互联网为抓取 范围，或以某个专业领域为范围，但是，正所谓此消彼长，搜索范围的减小的同 时给搜索的精度带来了更高的要求。 本课题的研究意义如下： 理论方面：研究现有i n t e m e t 搜索引擎的基本设计思想，及当前主流开 源搜索引擎工具的代码及工作原理，在其基础上进行二次整合，来提高搜索引擎 北京t 业大学t 学顾f ：学位论文 的查全率和查准率，在理论研究领域走在科技前沿。 实际应用：本课题最大的成功之处就是在“多语言系统中作为核心模 块之一，在奥运会期间，在授权用户进行关键信息查询获取时，提供了坚实的后 台技术支撑，为“2 0 0 8 奥运综合数据库查询系统( h t t p ：i b o o t h b e i j i n 9 2 0 0 8 c n ) 提供了专业的搜索引擎服务。 1 4 本文的组织结构 本文主要针对l u c e n e 和h e r i t r i x 的基本功能和扩展进行了研究，在已有的功 能上进行了整合，设计并实现了一个面向特定系统的搜索引擎。 首先，叙述了搜索引擎的发展背景及发展现状，回顾了搜索引擎的发展历史， 对搜索引擎的基本工作原理和技术设计进行了分析，旨在对搜索引擎有一个系统 的理解。 其次，由于全文检索作为搜索引擎的一个核心技术之一，对全文检索技术进 行了剖析，结合搜索引擎的工作原理和技术，宏观上进行了分析。 接着，对当前一些主流搜索引擎工具l u c e n e 等进行了概述，对其关键技术 进行了深入研究。 然后，基于以上关键技术，针对。2 0 0 8 奥运综合数据库查询系统 的特定 需求，进行全面整合，提出了该系统搜索模块的设计方案。包括系统设计思想、 技术策略、结构框架和开发环境等。 最后对本系统进行了实现，并对本系统的运行结果进行了展示。 本文总体分为五章，各部分的组织结构如下： 第一章介绍了选题背景，指出了本课题的研究意义。 第二章进行了搜索引擎的概述，对搜索引擎的基本工作原理进行了简要的阐 述，简要介绍了搜索引擎的排序和性能评优指标。 第三章对全文检索技术进行了研究，对全文检索系统的索引进行了研究。 第四章主要分析了开源搜索引擎包l u c e n e ，对其系统结构、数据类型、索 引格式进行深入分析，并比较了和传统数据库检索的异同。 第五章是基于以上技术对本系统的架构设计，描述了系统的基本工作流程， 并进行了实现。 第六章是总结和展望，总结了本文的工作和今后的发展方向。 第2 章搜索r j i 擎概述 第2 章搜索引擎概述 2 1 什么是搜索引擎 搜索引擎( s e a r c he n g i n e s ) 是对互联网上的信息资源进行搜集整理，然后供 你查询的系统，它包括信息搜集、信息整理和用户查询三部分 搜索引擎是一个为你提供信息“检索”服务的网站，它以一定的策略在互联网 中搜集、发现信息，对信息进行理解、提取、组织和处理，并为用户提供检索服 务，从而起到信息导航的目的。用户的查询途径主要包括自由词、全文检索、主 题词检索、分类检索及其它特殊信息的检索( 企业、人名、电话黄页等) 目前搜索引擎提供的导航服务已经成为互联网上非常重要的网络服务之一， 搜索引擎站点也被人们称为“网络门户 。搜索引擎技术因而成为计算机工业界 和学术界争相研究、开发的对纠卯。 2 2 搜索引擎的背景和发展 在互联网发展初期，网站相对较少，信息查找比较容易。然而伴随互联网爆 炸性的发展，普通网络用户想找到所需的资料简直如同大海捞针，这时为满足大 众信息检索需求的专业搜索网站便应运而生了。 早期的搜索引擎是把因特网中的资源服务器的地址收集起来，由其提供的资 源的类型不同而分成不同的目录，再一层层地进行分类。人们要找自己想要的信 息可按他们的分类一层层进入，就能最后到达目的地，找到自己想要的信息。这 其实是最原始的方式，只适用于因特网信息并不多的时候。随着因特网信息按几 何式增长，出现了真正意义上的搜索引擎，这些搜索引擎知道网站上每一页的开 始，随后搜索因特网上的所有超级链接，把代表超级链接的所有词汇放入一个数 据库，这就是现在搜索引擎的原型【6 】。 最早现代意义上的搜索引擎出现于1 9 9 4 年7 月，当时m i c h a e lm a u l d i n 将j o h n l e a v i t t 的蜘蛛程序接入到其索引程序中，创建了大家现在熟知的l y c o s 。同年4 月，斯坦福( s t a n f o r d ) 大学的两名博士生，d a v i df i l o 和美籍华人杨致远( g e r r y y a n g ) 共同创办了超级目录索引y a h o o ，并成功地使搜索引擎的概念深入人心， 从此搜索引擎进入了高速发展时期。伴随着互联网这十余年的发展，搜索引擎也 在经历着日新月异的变化，按照时间发展的趋势来看，搜索引擎可以分为以下几 个阶段： 1 9 9 5 目录式的搜索盛行。在一个简洁的主页上，在关键词输入框中输入要查 北京工业大学t 学硕l ：学位论文 找的内容，我们立刻会得到想要的相关信息，这就是我们现在常常使用的搜索引 擎。但是十几年前，在第一代的搜索引擎刚刚出现的时候，还不是这样，搜索几 乎都是清一色目录。说道目录式的搜索分类，大家自然会想到著名的y a h o o 的界 面，这种简明格式当时被相当多综合性的网站效仿【7 1 。这种搜索方式不仅需要人 工方式的内容管理和分类，而且相关的链接还要人工方式加入目录，在当时只有 几千个有效网站的状况下，这种方式还是非常实用和方便的。但是随着互联网内 容的激增，它的问题也显得越来越突出，这预示着新的搜索技术的机遇到来了。 1 9 9 6 新型搜索开始成熟。随着网络信息的飞速增长，单纯依靠人工分类整理 的目录式搜索已经远远不能满足人们查找信息的需要。当时，单单一家综合网站 的数据库里相关的信息，就可能储藏着近一亿的网页，对于如此庞大的网页数量， 人工根本无法处理的。另外，随着人们对网络信息的利用越来越多，对查找信息 的工具要求也越来越高。人们不再满足于在某一个专题网站上被动接受网站提供 的信息，需要把整个网络对自己有用的信息做一个有效的搜集与整理，这直接导 致了第二代搜索引擎的产生。这类搜索引擎的代表，现在我们都比较熟悉，在国 外是g o o g l e ，而在中文搜索领域是b a i d u 。虽然它们属于最成功的搜索引擎，但 并不是最早出现的，更早期出现的搜索引擎则是i n k t o m i 、a l t a v i s t a 和o v e r t u r e 等搜索技术，它们是必须要提到的。 1 9 9 9g o o g l e 强势阻击。虽然当前有很多拥有先进技术的互联网搜索技术的 公司，但是目前最被大家关注的搜索引擎g o o g l e ( w w w g o o g l e c o r n ) ，与其他公司 相比，它是一家成立非常晚的搜索引擎公司，但它被公认为是做得最成功的。 g o o g l e 目前被公认为全球最大的搜索引擎，它提供了简单易用的免费服务，用 户可以在瞬间返回相关的搜索结果。在访问g o o g l e 主页时，您可以使用多种语 言查找信息、查看新闻标题、搜索超过几十亿幅的图片，并能够细读全球最大的 u s c n c t 消息存档，其中提供的帖子也超过几十亿个，时间最早可以追溯到1 9 8 1 年。在使用界面方面g o o g l e 也有自己的优势，用户不必特意访问g o o g l e 主页， 也可以访问所有这些信息。使用g o o g l e 工具栏可以从网上任何一个位置进行 g o o g l e 搜索。即使身边没有计算机，您也可以通过w a p 和i - m o d e 手机等无线 平台使用。g o o s e 的实用性及便利性赢得了众多用户的青睐，它几乎完全是在 用户的交口称颂下成为全球最知名的品牌之一。作为一个企业，o o o g l e 通过提 供广告服务来获取收入，使广告客户能够刊登与特定网页内容相关的、重要而有 经济实效的在线广告。这不仅为您提供了实用的广告信息，同时也给刊登广告的 广告客户带来了好处瞒j 。 2 0 0 0 中文引擎开始崛起。虽然技术上并没有太多的改变，搜索引擎在各地的 本地化还是遇到了很多的问题。从第二代搜索引擎开始，特别是技术成熟的后期， 人们逐渐对搜索引擎的本地化和人性化的应用进行了更深入的讲究。搜索引擎是 个非常复杂的事情，互联网的用户需求也相当之复杂。而随着网络信息对普通人 筇2 币搜索0 l 挈慨述 生活的影响，人们越来越需要它，它的搜索速度、搜索内容、文件类型、准确性 等等都超出了单纯技术的范围，人们的“本土化”和“生活化”越来越受到关注和重 视。其实，搜索引擎的进化过程，就是一个时时满足海量信息时代人们对有效 信息需求的过程。将来搜索引擎的发展方向，一定是向着更人性化的方向发展。 现在的搜索引擎，从某种意义上说，还是一些文化素质比较高的人的工具。在中 国，人们利用搜索引擎的水平还不高，他们迫切需要这样的一个工具：简单实用、 不需要学习如何使用就可以帮助人们改善自己的生活质量。哪些公司能够尽快的 找到答案，就可能迅速走向成功。在这方面百度公司就是一个成功的案例。然而 作为搜索引擎领域的巨头g o o g l e 和雅虎当然毫不逊色，相继在中文搜索领域进 行深入探索研究，经数家调查机构的统计结果显示，都不约而同地把雅虎、 g o o g l e 、百度三家厂商列入了当前中国搜索引擎市场的三强。 2 0 0 4 竞争从特色开始。很多门户网站由于技术与资金的问题，将搜索业务外 包给几个搜索巨头，但是对于超级门户大头来说，他们有着自己的打算。如何打 破单一搜索门户所采用的竞价排名商业模式，赋予搜索引擎更大的互动性，各大 门口均采用了不同的手段。2 0 0 4 年8 月3 日搜狐公司推出搜狗( w w w s o g o u t o m ) ， 这是完全自主技术开发的全球首个第三代互动式中文搜索引擎。2 0 0 5 年4 月1 2 日，搜狐公司宣布收购国内著名地图引擎网站g 0 2 m a p ( w w w 9 0 2 m a p c o i n ) ，把 g 0 2 m a p 基于在线地图服务方面的领先技术应用于搜狗。2 0 0 5 年5 月2 6 日，搜 狗地图服务推出，标志着搜狗成为国内首家拥有地图服务的搜索引擎。2 0 0 4 年 1 2 月1 3 日，雅虎旗下的独立搜索门户“一搜”( y i s o u c o r n ) 对m p 3 搜索引擎进行全 球升级，正式推出了可检索全球1 5 0 0 万m p 3 音乐文档的搜索引擎，用户登录“一 搜”网站y i s o u c o m 即可以使用。2 0 0 5 年6 月3 0 日，备受外界关注和期待的新浪 搜索引擎“爱问”( w w w i a s k c o r n ) 终于正式亮相。这款耗时一年多完全自主研发的 搜索产品，采用了目前最为领先的智慧型互动搜索技术，将给原先算法致胜的网 络搜索市场带来前所未有的挑战。此外，也不能忽视m s n 搜索以及刚刚出现的 职业搜索“d e e pd o ”等特色搜索引擎可能带来的冲击，它们成功与否将取决于能否 找到市场空白区，并通过优良的技术与服务找到很好的盈利模式p j 。 然而由于搜索引擎的工作方式和因特网的快速发展，使其搜索的结果让人越 来越不满意。例如，搜索“电脑”这个词汇，就可能有数百万页的结果。这是由于 搜索引擎通过对网站的相关性来优化搜索结果，这种相关性又是由关键字在网站 的位置、网站的名称、标签等公式来决定的，这就是使搜索引擎搜索结果多而 杂的原因，而搜索引擎中的数据库因为因特网的发展变化也必然包含了死链接。 搜索十余载，风雨十余年，互联网的技术永远依赖于互联网的发展。怎样才 能使搜索引擎精确地为人们提供相关的信息应该是它以后发展的方向，而不是只 求综合服务。 北京t 业人学工学硕上学位论文 2 3 搜索引擎的工作原理 2 3 1 搜索引擎的基本工作流程 所谓“搜索引擎一，说到底是一个计算机应用软件系统，或者说是一个网络 应用软件系统。从网络用户的角度来看，它根据用户提交的类自然语言查询词或 者短语，返回一系列很可能与该查询相关的网页信息，供用户进一步判断和选取。 为了有效的达到这一点，它大致分为三个功能模块，或者三个子系统：即网页搜 集、预处理和查询服务。现代大规模高质量搜索引擎都采用如图2 1 所示的称之 为三段式的工作流程，在实践中这三个部分是相对独立的，它们的工作形成了搜 索引擎工作的三个阶段，通常分别由人工启动【1 0 】。 户 图2 - 1 搜索引擎三段式工作流程 f i g u r e2 - i 硼 l r e e - s t e ps e a r c h 饥g i n ew o r k f l o w 从上图可以看出，基本工作流程如下： ( 1 ) 从互联网上搜集网页信息 利用信息采集模块中的网络蜘蛛程序从互联网上以广度优先或深度优先的 方法自动采集有关的网页内容，并把采集过程中所发现的新的u r l 加入u r l 数 据库，不断重复这个过程，直到把所有指定范围的网页内容采集到网页数据库中 存储。 ( 2 ) 对采集到的网页信息进行预处理 由预处理模块对网页数据库中的网页信息进行分析和过滤，提取相关网页信 息，将非结构化的网页内容加工整理后得到结构化的文本文档，然后对其进行分 词并建立索引，将文档以便于检索的方式存储在索引数据库中。 ( 3 ) 通过查询接口向用户提供服务 当网络用户通过查询接口输入一定的关键词后，接口模块对关键词进行分 析，然后提交给索引数据库，查找出符合该关键词的所有相关网页，然后再根据 其相关度等评级数值进行排序，最后由查询模块将搜索结果的链接地址和页面内 容摘要等内容组织起来呈现给网络用户。 2 3 2 搜索引擎的网页搜索 搜索引擎作为一个特殊的软件系统，它所操作的数据不仅包括内容不可预测 第2 币搜索7 j l 警慨述 的用户查询，还要包括在数量上动态变化的海量网页，并且这些网页不会主动送 到系统来，而是需要由系统去抓取。 首先，我们考虑抓取的时机：事先还是即时。我们都有经验，在网络比较畅 通的情况下，从网上下载一篇网页大约需要1 秒钟左右，因此如果在用户查询的 时候即时去网上抓来成千上万的网页，一个个分析处理，和用户的查询匹配， 不可能满足搜索引擎的响应时间要求。不仅如此，这样做的系统效益也不高( 会 重复抓取太多的网页) ，面对大量的用户查询，不可能想象每来一个查询，系统 就到网上“搜索 一次【l l 】。 因此我们看到，大规模搜索引擎服务的基础应该是一批预先搜集好的网页 ( 直接或者间接) 。这一批网页如何维护? 可以有两种基本的考虑。 定期搜集，每次搜集替换上一次的内容，我们称之为“批量搜集”。由于每次 都是重新来一次，对于大规模搜索引擎来说，每次搜集的时间通常会花几周。而 由于这样做开销较大，通常两次搜集的间隔时间也不会很短( 例如早期天网的版 本大约每3 个月来一次，g o o g l e 在一段时间曾是每隔2 8 天来一次) 。这样做的 好处是系统实现比较简单，主要缺点是“时新性”( f r e s h n e s s ) 不高，还有重复搜 集所带来的额外带宽的消耗。 增量搜集，开始时搜集一批，往后只是搜集新出现的网页、搜集那些在上次 搜集后有过改变的网页、发现自从上次搜集后已经不再存在了的网页，并从库中 删除。由于除新闻网站外，许多网页的内容变化并不是很经常的，这样做每次 搜集的网页量不会很大。这样的系统表现出来的信息时新性就会比较高，主要缺 点是系统实现比较复杂，这种复杂还不仅在于搜集过程，而且还给将来的构建索 引过程带来困难。 在具体搜集过程中，如何抓取一篇篇的网页，也可以有不同的考虑。最常见 的一种是所谓“爬取”：将w e b 上的网页集合看成是一个有向图，搜集过程从给 定起始u r l 集合s ( 或者说“种子”) 开始，沿着网页中的链接，按照先深、先 宽、或者某种别的策略遍历，不停的从s 中移除u r l ，下载相应的网页，解析 出网页中的超链接u r l ，看是否已经被访问过，将未访问过的那些u r l 加入集 合s 。整个过程可以形象地想象为一个蜘蛛( s p i d e r ) 在蜘蛛网( w e b ) 上爬行 ( c r a w l ) 后面我们会看到，真正的系统其实是多个“蜘蛛”同时在爬。 还有一种方法是让网站拥有者主动向搜索引擎提交它们的网址( 为了宣传 自己，通常会有这种积极性) ，系统在一定时间内( 2 天到数月不等) 定向向那 些网站派出“蜘蛛”程序，扫描该网站的所有网页并将有关信息存入数据库中。大 型商业搜索引擎一般都提供这种功能【1 2 】。 总体来说，通用的搜索引擎网页搜集工作流程如图2 2 所示，整个过程是从 u r l 库( 初始时包含用户指定的起始种子u r l 集合，可以是1 个或多个) 获得 输入，解析u r l 中标明的w e b 服务器地址、建立连接、发送请求和接受数据， 北京t 业大学工学硕上学位论文 将获得的网页数据存储在原始网页库，并从其中提取出链接信息放入网页数据 库，同时将待抓取的u r l 放入u r l 库，保证整个过程的递归进行，直到u r l 库为空。 图- 2 w e b 信息搜集 f i g u r e2 - 2w e bi n f o r m a t i o n - g a t h e r i n g 2 3 3 搜索引擎的网页预处理 得到海量的原始网页集合，距离面向网络用户的检索服务之间还有相当的距 离。如何将亿万级的原始网页进行合理的组织安排，构建一个合理的数据结构， 是预处理系统的主要任务。现行最有效的数据结构是“倒排文件一( i n v e r s ef i l e ) ， 倒排文件是用文档中所含关键词作为索引，文档作为索引目标的一种结构( 类似 于普通书籍中，索引是关键词，书的页面是索引目标) 。预处理可分为四个部分： 关键词的提取，“镜像网页 ( 网页的内容完全相同，未加任何修改) 或“转载网 页 ( n e a r - r e p l i c a s ，主题内容基本相同但有可能有一些额外的编辑信息等，转载 网页也称为“近似镜像网页) 的消除，链接分析和网页重要程度的计算【l3 1 。 ( 1 ) 关键词的提取 随便找一篇网页的源文件( 例如在任何一个已打开的网页上右键选择源文 件) ，我们可以看到其中有很多复杂的h t m l 代码( 对于非专业人士而言) 。除 了我们通过浏览器可以看到正常的文字内容以为，最多的就属h t m l 标记。另 外，由于h t m l 文档产生来源的多样性，许多网页在内容上比较随意，不仅文 字不讲究规范、完整，而且还可能包含许多和主要内容无关的信息( 例如广告、 导航条、版权说明等) 。这些情况既给有效的信息查询带来了挑战，也带来了一 些新的机遇。搜索引擎为了支持查询服务，需要从网页源文件中提取出能够代表 当前网页内容的一些特征信息。从如今网络用户的认识和实践角度来看，所含的 关键词即为这种特征最好的代表。因此，作为预处理阶段的一个首要任务，就要 提取出网页源文件中的内容部分所含有的关键词。对于中文来说，就是根据一个 词典d ，用一个所谓的“切词”的方法( 严格来讲应该是一种程序算法) ，从网页 源码中切取出d 中含有的词语来。此后，一篇网页主要就由这么一组词来近似 代表了。一般，同一个词可能在一篇网页中多次出现。从效果和效率来考虑， 第2 帚搜索) i 警概述 不应该让所有的词都出现在网页表示中，要去掉诸如“的，“在 等没有内容指 示含义的词，如此以来，一篇网页有效的字符数量大约就被控制在2 0 0 个左右 1 1 4 1 o ( 2 ) 重复或转载网页的消除 与生俱来的数字化和网络化给网页的复制以及转载和修改再发表带来了便 利，因此我们看到w e b 上的信息存在大量的重复现象。根据某著名搜索引擎网 站的一次大规模统计分析表明，网页的重复率平均大约为4 。也就是说，当你通 过一个u r l 在网上看到一篇网页的时候，平均还有另外3 个不同的u r l 也给 出相同或者基本相似的内容这种现象对于广大的网民来说是有正面意义的，因 为有了更多的信息访问机会。但对于搜索引擎来说，则主要是负面的；它不仅在 搜集网页时要消耗机器时间和网络带宽资源，而且如果在查询结果中出现，无意 义地消耗了计算机显示屏资源，也会引来用户的抱怨，。这么多重复的，给我一 个就够了一。因此，消除内容重复或主题内容重复的网页是预处理阶段的一个重 要任务【1 5 1 。 ( 3 ) 链接分析 前面提到，大量的h t m l 标记既给网页的预处理造成了一些麻烦，也带来 了一些新的机遇。从信息检索的角度讲，如果系统面对的仅仅是内容的文字，我 们能依据的就是“共有词汇假设 ( s h a r e d b a g o f w o r d s ) ，即内容所包含的关键词 集合，最多加上词频( t e r mf r e q u e n c y 或t f ) 和词在文档集合中出现的文档频 率( d o c u m e n tf r e q u e n c y 或d f ) 之类的统计量。而t f 和d f 这样的频率信息 能在一定程度上指示词语在一篇文档中的相对重要性或者和某些内容的相关性， 这是有意义的。有了h t m l 标记后，情况还可能进一步改善，例如在同一篇文 档中， 和 之间的信息很可能就比在 和 之间的信息更重要【1 6 1 。 特别地，h t m l 文档中所含的指向其他文档的链接信息是人们近几年来特别关注 的对象，认为它们不仅给出了网页之间的关系，而且还对判断网页的内容有很重 要的作用。例如“北京工业大学学报一这几个字在北京工业大学的主页上是没有 的，因此一个仅靠内容文字分析的搜索引擎就不可能返回该主页作为结果，但是 北京工业大学主页上是用“工大学报作为链接信息指向了北京工业大学学报的 主页，因此在很好利用链接信息的搜索引擎中应该能返回北京工业大学学报的主 页。 ( 4 ) 网页重要度的计算 搜索引擎返回给用户的，是一个和用户查询相关的结果列表。列表中条目的 顺序是很重要的一个问题。由于面对各种各样的用户，加之查询的自然语言风格， 对同样的查询关键字返回相同的列表肯定是不能使所有提交同样查询关键字的 用户都满意的( 或者都达到最高的满意度) ，因此搜索引擎实际上追求的是一种 统计意义上的满意。人们认为g o o g l e 目前比多数搜索引擎好，是因为在多数情 北京t 业大学t 学硕i ：学位论文 况下前者返回的内容要更符合用户的需要，而不是所有情况下都如此。如何对查 询结果进行排序有很多因素需要考虑，这里只是概要解释在预处理阶段可能形成 的所谓“重要性 因素。顾名思义，既然是在预处理阶段形成的，就是和用户查 询无关的。如何讲一篇网页比另外一篇网页重要? 人们参照科技文献重要性的评 估方式，核心想法就是“被引用多的就是重要的一。“引用 这个概念恰好可以通 过h t m l 超链接在网页之间体现得非常好，作为g o o g l e 创立核心技术的 p a g e r a n k 就是这种思路的成功体现【1 7 】。除此以外，人们还注意到网页和文献的 不同特点，即一些网页主要是大量对外的链接，其本身基本没有一个明确的主题 内容，而另外有些网页则被大量的其他网页链接。从某种意义上讲，这形成了一 种对偶的关系，这种关系使得人们可以在网页上建立另外一种重要性指标 k l e i n b e r g , 1 9 9 8 。这些指标有的可以在预处理阶段计算，有的则要在查询阶段计 算，但都是作为在查询服务阶段最终形成结果排序的部分参数。 基于在网页预处理阶段的主要工作任务，网页预处理阶段的系统结构图如图 2 3 所示。 图2 3 网页预处理系统结构 f i g u r e2 - 3p a g ep r e - p r o c e s s i n gs y s t e ma r c h i t e c t u r e 首先为原始网页构建图2 3 中的索引网页库，采用相应的算法生成符合搜索 引擎要求的存储格式，在基于紧凑的数据格式和高效的检索能力的同时，尽量保 证数据的一致性，有了索引就可以为搜索引擎提供网页快照等功能。接下来针对 索引网页库进行网页划分，将每一篇网页转化为一组词的集合，此处涉及到了中 文分词技术，最后将网页到索引词的映射转化为索引词到网页的映射，形成倒排 文件( 包括倒排表和索引词表) ，同时将网页中包含的不重复的索引词汇聚成索 引词表。 由于搜索引擎面临着大量的用户检索需求( 几十几千点击秒) ，因