（计算机应用技术专业论文）搜索引擎中网页排序算法的研究与实现.pdf

产 0 c ! l a s s i f i e di n d e x ： u d c ： ad i s s e r t a t i o nf o rt h ed e g r e eo f m e n g r e s e a r c ha n d i m p l e m e n t a t i o no fp a g er a n k a l g o r i t h m so ns e a r c he n g i n e c a n d i d a t e s u p e r v i s o r a c a d e m i cd e g r e ea p p l i e df o r s p e c i a l i t y d a t eo fs u b m i s s i o n d a t eo f0 r a le x a m i n a t i o n u n i v e r s i t y ：w a n gy o n g w e i ：p r o f z h a n gw e n y i ：m a s t e ro fe n g i n e e r i n g ：c o m p u t e ra p p l i e dt e c h n o l o g y ：m a r c h ，2 0 1 0 ：m a r c h ，2 0 1 0 ：h a r b i ne n g i n e e r i n gu n i v e r s i t y 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中已注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 、 作者( 签字) ：专9 争铲 日期： i9 年；月) 日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( d 在授予学位后即可旅授予学位1 2 个月后 口解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：渐 日期： oj o 年月，7 日 导师( 签字) ：银又蕻 o o 年3 月， 日 哈尔滨i ：科人学硕十学付论文 摘要 随着互联网的飞速发展，互联网上的文档( 网页) 的增长速度也非常之 快。根据有关资料显示，互联网上的资源在每一年的时间内就会增加一倍之 多。搜索引擎就是在这样的大背景下应运而生的，它有助于用户在大量的信 息资源库里获取信息。因此搜索引擎成为了人们搜集信息资源的一个重要手 段。用户在依靠搜索引擎能够提供丰富的信息资源的同时，也对搜索引擎提 供的服务质量有了更高的要求。返回结果直接影响到一个搜索引擎的效率和 受欢迎程度。返回结果的核心技术之一就是网页排序技术。 搜索引擎技术在最近几年发展很快，最具代表性的就是g o o g l e 公司，它 的迅猛发展也激起了其他同行们的研究热情，然而利用搜索引擎返回的查询 结果的数量有时也相当之大，用户不可能把所有摘要都浏览一遍。一些数据 统计表明，返回结果列表的前三页是用户最常浏览的，当然，浏览第一页的 次数是最高的，因此一个搜索引擎的优劣与返回结果的合理与否有着密切的 关系。所以人们对网页排序算法的研究在逐渐的深入。 本文首先介绍了搜索引擎的工作原理以及发展过程。主要研究了各大知 名搜索引擎的排序算法，分析其影响排序结果的因素。比较各排序算法的优 缺点和适合使用该算法的情况。p a g e r a n k 算法和h i t s 算法以及词频位置加权 算法是研究的重点。针对向量模型现有的不足做了改进，主要是利用文档主 题词和查询词之间的向量夹角余弦值，改进后的模型，虽然增加了一些运算 量，但能够更精确的计算文档与查询词之间的相似度。 本文针对词频位置加权算法的缺点，分析了其产生这种缺点的原因。以 该算法的思想为核心，结合逆文本频率指数以及改进后的向量模型，设计出 文档权值计算公式。该公式计算过程与查询词有效的结合在一起。经过系统 实现和测评，证明该算法易实现，而且排序结果更准确、效率更高。 关键词：排序算法；词频位置加权算法；搜索引擎；向量模型 哈尔滨f ：科人学硕十学何论文 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to ft h ei n t e m e t ，t h ed o c u m e n t so rw e bp a g e so n t h ei n t e r a c tg r o wv e r yf a s t a c c o r d i n gt os o m er e l a t e di n f o r m a t i o n ，i n t e r n e t r e s o u r c e si n c r e a s em o r et h a nd o u b l e de v e r yy e a r i nt h i sb a c k d r o pt h es e a r c h e n g i n ec o m ei n t ob e i n gw h i c hh e l p su s e r st oa c c e s si n f o r m a t i o nf r o mal o to f i n f o r m a t i o nr e s o u r c el i b r a r y t h e r e f o r e ，i ti sa ni m p o r t a n tm e a n sf o rp e o p l et o c o l l e c ti n f o r m a t i o nr e s o u r c e sb yu s i n gt h es e a r c he n g i n e w h i l er e l y i n go nt h e s e a r c he n g i n e sw e a l t ho fi n f o r m a t i o nr e s o u r c e s ，u s e r sa l s op u tf o r w a r dh i g h e r r e q u i r e m e n t so n t h eq u a l i t yo fs e r v i c ep r o v i d e db yt h es e a r c he n g i n e t h er e s u l to f t h es e a r c he n g i n ed i r e c t l ya f f e c t si t se f f i c i e n c ya n dp o p u l a r i t y o n eo ft h ec o r e t e c h n o l o g i e si sh o w t os o r tt h er e s u l t sp a g e s t h et e c h n o l o g yo ft h es e a r c he n g i n eh a sd e v e l o p e dr a p i d l yi nr e c e n ty e a r s t h em o s tr e p r e s e n t a t i v ec o m p a n yi sg o o g l e ，a n di t sr a p i dd e v e l o p m e n th a sa l s o m i r r e du po t h e rc o l l e a g u e se n t h u s i a s mf o rt h e i rs t u d y b u tt h es e a r c he n g i n e r e t u r n ss om a n yq u e r yr e s u l t ss o m e t i m e st h a tu s e r sc a l l tr e a da l lt h es u m m a r i e s s o m es t a t i s t i c ss h o wt h a tt h ef i r s tt h r e ep a g e so ft h er e s u l t s l i s ta r em o s t f r e q u e n t l yb r o w s e db yu s e r o fc o u r s e ，t h ef i r s tp a g e sf r e q u e n c yi st h eh i g h e s t ， a n dt h e r ei sac l o s er e l a t i o n s h i pb e t w e e nt h es e a r c he n g i n e sq u a l i t ya n di t s r e s u l t s r e a s o n a b i l i t y s op e o p l e ss t u d yo nt h ep a g er a n ka l g o r i t h mi sg r a d u a l l y i n - d e p t h a tt h ef i r s t ，t h i sp a p e ri n t r o d u c e st h ew o r k i n gp r i n c i p l eo fs e a r c he n g i n e s ，a s w e l la st h ed e v e l o p m e n tp r o c e s s ，a n dt h e nm a i n l ym a k e sas t u d yo nt h er a n k i n g a l g o r i t h mo fs o m ew e l l - k n o w ns e a r c he n g i n e s ，a n a l y z e st h ei m p a c tf a c t o ro ft h e r e s u l t ss o r t t h ep a p e rc o m p a r e st h ea d v a n t a g e sa n dd i s a d v a n t a g e so fs e v e r a l s o r t i n ga l g o r i t h m sa n dt h ea l g o r i t h m ss u i t a b l es i t u a t i o n t h i ss t u d ya l s of o c u s e s o nt h ep a g e r a n ka l g o r i t h m ，h i t sa l g o r i t h ma n df r e q u e n c yp o s i t i o nw e i g h i n g a l g o r i t h m u s i n g t h ec o s i n ev a l u eo ft h ev e c t o ra n g l eb e t w e e nd o c u m e n t k e y w o r d sa n dq u e r yw o r d s ，t h ee x i s t i n gv e c t o rm o d e li si m p r o v e di nt h i sp a p e r 哈尔滨i ：稗人学硕十学何论文 a l t h o u g ht h ei m p r o v e dm o d e ln e e d sm o r ec o m p u t a t i o n ，t h es i m i l a r i t yb e t w e e n t h ed o c u m e n ta n dq u e r yw o r d sc a nb em o r e p r e c i s e l yc a l c u l a t e d t h i sp a p e ra n a l y z e st h er e a s o n sf o rt h es h o r t c o m i n g so ff r e q u e n c yp o s i t i o n w e i g h i n ga l g o r i t h m t h e no nt h ec o r ei d e ao ft h ea l g o r i t h mt h ep a p e rd e s i g n sa f o r m u l af o rc a l c u l a t i n gt h ed o c u m e n tw e i g h tv a l u eb yc o m b i n i n gw i t ht h ei n v e r s e t e x tf r e q u e n c yi n d e xa n dt h ei m p r o v e dv e c t o rm o d e l t h ep r o c e s so ft h ef o r m u l a s c a l c u l a t i o ni s e f f e c t i v e l yi n t e g r a t e d w i t ht h e q u e r y w o r d s t h e s y s t e m i m p l e m e n t a t i o na n de v a l u a t i o np r o v e st h a tt h i sa l g o r i t h mi se a s yt oa c c o m p l i s h a n dt os o r tt h er e s u l t sa n di sm o r e a c c u r a t e l ya n de f f i c i e n t l y k e y w o r d s ：s o r t i n ga l g o r i t h m ；w o r d sf r e q u e n c yp o s i t i o nw e i g h i n ga l g o r i t h m ； s e a r c he n g i n e ；v e c t o rm o d e l 哈尔滨i ：科人学硕十学付论文 目录 第l 章绪论1 1 1 课题研究背景l 1 2 国内外发展现状2 1 3 本文主要工作4 1 4 论文研究内容及结构4 第2 章搜索引擎介绍6 2 1 搜索引擎简介6 2 2 搜索引擎发展过程7 2 3 搜索引擎类别8 2 4 搜索引擎基本构成1 0 2 5 搜索引擎效率指标1 2 2 6 搜索引擎技术研究方向1 2 2 7 本章小结1 3 第3 章经典排序算法研究1 5 3 1 排序方法l5 3 1 1 p a g e r a n k 算法1 6 3 1 2h i t s 算法18 3 1 3两种链接分析算法的比较l9 3 1 4h i l l l p 算法21 3 1 5 s a l s a 算法2 2 3 1 6 a l e x a 的网站排名算法2 2 3 1 7d i r e c th i t 算法2 4 3 1 8l u c e n e 文档排序算法2 5 哈尔滨t w 人号! 硕十学何论文 3 1 9 词频位置加权排序计算方法2 6 3 2 本章小结2 8 第4 章利用词频位置加权算法实现网页排序2 9 4 1 中文分词技术2 9 4 2 信息检索3 0 4 2 1概率模型31 4 2 2 布尔模型3 2 4 2 3向量模型3 3 4 2 4 查准率和查全率3 4 4 3 逆文本频率指数的应用3 5 4 4 向量模型的改进与应用3 7 4 5 系统设计与实现4 1 4 5 1爬取网页4 2 4 5 2文档处理4 3 4 5 3建立文档索引4 3 4 5 4 文档权值计算4 5 4 5 5查询处理4 6 4 5 6 返回列表4 7 4 6 本章小结4 7 第5 章结果与分析4 8 5 1 系统实现环境4 8 5 2 改进算法测评4 8 5 3 改进后向量模型测评4 9 5 4o t i c 属性曲线4 9 5 5 查询处理5 0 5 6 本章小结5 2 结1 沦5 3 哈尔演l ： l | ! 人学硕十学位论文 参考文献5 4 攻读硕士学位期间发表的论文和取得的科研成果5 7 致谢5 8 哈尔滨i j 种人学硕十学何论文 1 1 课题研究背景 第1 章绪论 随着计算机的普及以及信息工程的同益发展，从网上获取信息已经成为 人们的同常生活和工作一个重要途径，互联网如今已成为一个资源不断丰富 的平台，整个互联网逐渐成为一个信息量超大的资源存储空间。因此怎样有效 而又快捷的从海量数据中获取所需的信息就成为一件困难的事情，搜索引擎 的出现正是为了解决“信息丰富，获取困难”的问题的一种信息检索服务。 搜索引擎被称为是一个信息处理和获取的黑盒子，通过一定的规则在互联网 中爬取信息资源以及对信息进行处理和提取，对外提供接口方便用户查询， 从而起到指导用户获取信息的作用，主要由采集信息、组织并处理信息和查 询接口三部分组成。搜索引擎对于用户来说就是一个为其提供信息搜索功能 的查询工具。搜索引擎所具有的研究价值、实用价值以及商业价值是其在当 今信息时代获得成功的重要因素。搜索引擎技术涉及到的领域很多，如：信 息检索、数据挖掘、数据库、自然语言理解、中文分词等领域的前沿技术和 理论，具有复杂性和艰巨性。同时有大量的用户在使用搜索引擎，由此产生了 一系列商业链具有广阔的经济前景【一l 。 大概在1 9 9 4 年出现了第一代搜索引擎。然而这些搜索引擎的索引数据库 资源数量很少而且更新周期很长。并且其响应时间也是用户很难接受的，所 以用户数量很少。其使用的技术没有创新只是照搬已有的技术理论，其技术 的局限性也成为其发展的先天缺陷。当时的“蜘蛛程序 工作效率也非常之 低，不能满足人们对信息的需求。 随着技术的发展，分布式被应用到了搜索引擎中提高了其服务的质量， 主要是索引库的数量和响应时间以及文档更新速度。 1 9 9 8 年之后搜索引擎的发展出现了比较繁荣的阶段，排序算法、“蜘蛛 程序”都发展较快。 如今随着搜索引擎技术的飞速发展以及一些大型公司取得的成功，关于 搜索引擎的技术也成为人们研究的焦点。而排序算法是最热点的研究技术之 哈尔滨r 1 秤人导：硕十学付论文 一。 现有的排序算法主要是超链接和词频加权算法，它们都有很多地方需要 改善，如超链接算法的主题漂移问题以及词频加权算法的防作弊等问题。本 文针对词频加权算法存在的问题推导出了一种新的排序算法。通过实验证明 了该算法的效率和准确率都有一定的提高。 1 2 国内外发展现状 随着互联网时代的来临，计算机技术的发展速度极快，与此同时信息检 索技术也发展得非常迅猛，搜索效率将越来越高，搜索功能也越来越强大。 国外的一些著名公司已经成为该领域的先行者。下面介绍几个国际已成名搜 索引擎公司的发展现状以及排序算法的研究成果。美国的谷歌搜索引擎公司。 o p e n s o u r c e d i r e c t o r 、l o o k s m a r t 以及y a h o o 收录了其前页的搜索结果。谷歌 对网页间的链接非常注重，如果一个网站被许多具有权威的网站链接，该网 站也会被认为质量好而且排名会比较靠前。p a g e r a n k 是谷歌公司的创始人之 一佩奇( p a g e ) 根据一个项目研究分析得出一种影响业界的排序算法。雅虎 公司是被一致公认的最著名的搜索引擎之一( 更具体的说是分类目录搜索) ， 是通过谷歌获取的网页查询结果。存储在它的分类目录中的网站数据库，它 的查询结果以分类目录的方式显示给用户。虽然a l t a v i s t a 的发展时间比较长、 比较古老，现在仍然在搜索引擎领域中占有其一席之地，它拥有免费登陆网 站和收费登陆网站两种途径。m s ns e a r c h 由l o o k s m a r t 支持并为其提供数据 服务，i n k t o m i 提供其第二级查询结果。m s n 的最上级搜索结果是由o v e r t u r e 提供的，为m s n 成功的优化了搜索服务，所以必须需要详细考虑l o o k s m a r t 和i n k t o m i 的排名需求因素。在某些情形下d i r e c t h i t 的检索结果也会表现在 该搜索引擎上。n e t s c a p e s e a r c h 的检索结果也来自于谷歌公司。i n k t o m i 和其 他公司不同，它是唯一一个在其网站上不提供检索服务的搜索引擎，该搜索 引擎的真正目的是为其他搜索引擎提供资源，比如o v e r t u r e 、h o b o t 和m s n 等的资源均来自i n k t o m i 。它对于用户相当于二级检索。它推出的 i n k t o m i p r i o r i t v r s u b m i t 是被其他网站推广较为流行而且节省财力的方法【2 】。 如果提起国内搜索引擎技术应用现状就必须要提百度。美国的门户网站 2 哈尔滨i 稃人导：硕十学付论文 多是靠搜索引擎技术发展起来的，然而幽内搜索引擎技术的发展却一直举步 维艰，这种局面直到2 0 0 0 年下半年才有所改变。成立不久的百度公司迅速地 占据了c h i n a r e n 、硅谷动力、t o m 、s o h o 、s i n a 、广州视窗、2 1c n 、2 6 3 等门户网站的全文搜索引擎支持，成为了中文检索市场中的亮点。 百度取得的成绩对中文搜索的推动极大，不仅为门户网站提供了质量高 价格低的搜索服务，使国内互联网用户有更好的搜索平台，同时，百度的成 功也激发了创业者的灵感，推动国内中文搜索引擎进入百家争鸣的良好局面。 在过去的一年中，中文搜索引擎的发展势头之好成为了互联网行业的一个闪 光点。 在以往的网站分类目录检索方面，网易、搜狐、新浪各有千秋。良好的 技术实力是自身新闻网站的特点，新浪推行综合搜索服务，解决了用户分类 检索的困扰，只要键入想搜索的查询词，就会获得站点、链接、社会、生活 等频率使用较高的信息，结构非常清晰，在速度和质量方面都很优异，为用 户提供了丰富的信息供其参考。 易易寻公司把大部分时间花在了多媒体搜索引擎的研发上，由于图像搜 索引擎会给互联网用户带来极大的便利，它成功的研发了中文图像搜索引擎。 网易则拥有其网络信息优势并激发团队的战斗力，使开放式目录得以成 型。成为计算机业界的技术人才的理想雇主，大家群献群策形成了良性循环。 网易还在进一步开发搜索引擎的潜在能力，提供了利用手机短信发出检索结 果的功能。而搜狐的主要精力是整理网站的分类目录，形成有合理分类的分 类目录网蚶引。 天网搜索引擎是由北大计算机系网络实验室设计研发的，它收藏了大量 教育网内信息，这样，教育网内的大量有用资源被合理的利用起来，f t p 搜 索部分是它的一大特色，可供使用的资源极其丰富。通过年初的进一步开发 和测试，响应时间减少了很多。 c i a 信息参考及时新闻和网络资源付费获取计划是由o p e n f i n d ( 网擎) 推出的，它的理念是寻找新价值。终端客户花费很少就可以得到指定关键字 的最新更新资源，这是搜索引擎价值的另一方面体现。曾经，o p e n f i n d 是一 个很受欢迎的中文全文检索系统，而好景不长，互联网用户纷纷倾向其他后 来起家的搜索引擎，一度有消息人士说它有淡出搜索引擎行业的猜测，然而 3 哈尔滨广稃人。半：硕十导：付论文 猜测是没有依据的，它依然在花费大量精力在其开发上，现在，某些技术与 强大的百度已经很接近。 国内外已经开始接受搜索引擎这样功能强大的客户端软件，像雅虎这样 国际知名的网站也开始走搜索引擎路线，在其网站首页提供了搜索功能。提 供给访问者使用。而且，一些餐饮和能源公司的网站也同样跟着潮流提供检 索服务。据调查，美国的绝大多数企业都在其网站中提供该业务。在国内这 方面的发展也同样很快，在一些公司中这样的竞争意识也在慢慢形成。 1 3 本文主要工作 ( 1 ) 介绍搜索引擎的国内外发展现状以及基本工作原理和系统结构； ( 2 ) 详细分析了现今各知名搜索引擎的排序策略，并分析影响搜索引擎 排序的各方面要素。分析经典排序算法的优点和不足，主要是p a g e r a n k 、h i t s 以及词频位置加权算法，以及算法的演绎过程： ( 3 ) 介绍信息检索中的一些经典模型，并对向量模型进行改进以及逆文 本频率指数在信息检索中的应用。基于词频位置加权算法，结合改进后的向 量模型以及逆文本频率指数，得出本文的文档权值计算公式。通过系统实现 和测评，对结果进行分析。 1 4 论文研究内容及结构 本文对搜索引擎的系统结构、基本组成进行了系统的、初步的、全面的 研究。在此基础上主要深入研究了经典排序算法的优点和不足。并通过对向 量模型的改进和词频加权算法总结出一个适合本系统的文档权重计算公式。 论文共分五章，各章节的组织结构和内容如下： 第l 章主要介绍了课题来源及国内外的研究成果及发展现状，并给出了 本文的研究内容及论文的结构。 第2 章介绍搜索引擎的基本概念，包括搜索引擎的发展过程、类别及基 本组成原理等内容。 第3 章介绍了经典的排序算法，并进行了分析和概括。包括p a g e r a n k 排序算法、h i t s 排序算法和词频位置排序算法等内容，并对它们的优缺点进 4 哈尔滨。邳人学硕十学何论文 行了比较。 第4 章介绍了本文排序算法的由来和系统的设计与实现，包括向量空间 模型的改进、逆文本频率指数的应用、系统实现采用的框架、结构、蜘蛛程 序”、建立文档索引、查询处理等内容。 第5 章对本文设计的排序算法以及改进后的向量模型给出了结果与分 析。 哈尔滨i 。平人学硕十学何论文 第2 章搜索引擎介绍 2 1 搜索引擎简介 近年来互联网的发展非常迅速，互联网上的信息已海量存在，到2 0 0 9 年3 月份为止，全世界网站总数已超过1 8 亿。互联网j 下己幂数级的增长速 度在快速发展。1 9 9 4 年起搜索引擎技术在逐渐发展壮大。它是信息时代快速 发展的产物，它通过获取网上的信息资源并对其进行处理向用户提供信息检 索服务，方便用户获取信息f 4 】。 搜索引擎首先他是一套体系结构复杂、涉及知识领域广、通过编程实现 的系统，利用特定的方法和数据结构采用“蜘蛛程序在互联网上爬取信息， 并且对收集到的资源利用每个搜索引擎特有的策略进行建立文档索引和处理 后，用户可以在客户端使用其信息检索服务，按照一定的排序规则将返回的 结果形成排序列表。 以一个访问者的身份来看待，在客户端只能看到输入框和检索按钮，它 就像一个黑盒子，输入查询词之后，用户是不知道后台是如何运行的。搜索 引擎会根据查询词运行该系统，搜索引擎利用后台存储的数据通过一系列的 操作运行得出结果并提交给用户。搜索引擎就像一个只有输入和输出的检索 信息的工具，用户要做的事情是输入查询词得到的是与查询词相关的信息。 如果用户想了解一些汽车的相关信息，用户可以在输入框中输入查询词“汽 车 即可，搜索引擎会在极短的时间内将数据库旱存储的相关信息提供给用 户。 2 0 0 7 年7 月份，中国互联网络信息中心在北京发布了一次中国互联网发 展状况统计调查报告，报告中的数据说明利用信息检索系统、点击网页、收 发邮件是互联网用户使用频率最高的三个网络服务，三者的选择比例分别为 利用信息检索系统6 7 3 ，点击网页6 5 6 ，收发邮件6 3 2 ，从数据可以看 出以上三项已经成为人们不可或缺的网络功能1 3 l 。由于搜索引擎特有的功能， 它为用户解决了获取信息难的问题，它引起了人们的极大兴趣。成为人们工 作和学习中不可或缺的一项工具。搜索引擎的出现，改变了中国乃至世界互 6 哈尔滨i ：稃人学硕十学位论文 联网用户的网络行为习惯。 2 2 搜索引擎发展过程 1 9 9 0 年以前在互联网上搜索信息是做不到的事情。1 9 9 0 年推出的 a r c h i e ( a r c h i ef a q ) 是所有搜索引擎的前辈，是由m o n t r e a l 的麦吉尔大学学生 a l a ne m t a g e 、p e t e rd e u t s c h 、b i l lw h e e l a n 研发并取得成功。 1 9 9 4 年产生了第一个兼具浏览和检索功能的分类目录e i n e tg a l a x y ( t r a d e w a v eg a l a x y ) 。网站搜索是它的功能之一，同时t e l n e t 和g o p h e r 也是 它所提供的检索服务。同年，来自斯坦福大学的两名博士生，美籍华人杨致 远和d a v i df i l o 合作成立了y a h o o 公司。公司规模越做越大，网站存储数量 不断增加，简易的数据库检索模型已经初步形成。由于y a h o o 收集数据的方 法比较特别，采用人工录入，因此y a h o o 搜索不是纯粹意义上的信息检索系 统，实际上它维护一个目录供其他用户查询。链接地址是“蜘蛛程序判断 的依据，然而链接地址可供参考的信息非常有限，许多内容是不能靠链接地 址做出评判的，这样，后台数据的质量直接影响了搜索的结果。而y a h o o 存 储的目录，通过附加一些简要的介绍明显的提高了搜索效率1 5 l 。 另一个需要提及的重要的搜索引擎是i n f o s e e k ，公司官方宣布的成立时 间是1 9 9 4 年1 月，可是它的搜索引擎进入市场已经是年底了。刚开始，l n f o s e e k 搜索引擎影响力很有限，它引入雅虎的理念，在技术上并没有进行创新。让 人意想不到的是，它取得了很好的业绩获得了用户的一致好评，这些令那些 质疑它是否是第一个搜索引擎已经失去了争辩的意义。i n f o s e e k 提供了友好 的用户接口、另外其它附加的功能令它取得了很好的声誉。1 9 9 5 年年底的一 次变革使它更加强势，那就是与n e t s c a p e 的合作。安装有n e t s c a p e 浏览器的 用户均可使用l n f o s e e k 提供的检索服务，抢占了y a h o o 的部分市场。 1 9 9 5 年，出现了一种元搜索引擎( am e t as e a r c he n g i n er o u n d u p ) 是以 新形式出现的。用户提出一次请求会产生多方响应，元搜索引擎与一些独立 的搜索引擎合作，元搜索引擎做简单的处理后提交给与之合作的搜索引擎， 将搜索结果集中返回给元搜索引擎，再经过处理后将最终查询结果返回给客 户端。 7 哈尔滨l ：稃人导：硕十学何论文 1 9 9 7 年f a s t ( a l l t h e w e b ) 公司成立了，由挪威科技大学负责研究丌发的， 并于1 9 9 9 年5 月，推出了a l l t h e w e b ，并拥有其知识产权。f a s t 创立志向非 常宏伟，最快最大是其搜索引擎追求的目标，潜心几年进行研究，成果显著。 f a s t 可自动分类是其文档搜索的一项重要功能，并且支持动画视频和p d f 格 式的文档检索，f a s t 的高级搜索功能极其强大，不仅支持多语言搜索，新闻 搜索、图像搜索、f t p 、和m p 3 检索也同样支持。 谷歌是斯坦福大学的一个小项目名叫b a c k r u b ，但1 9 9 8 年l o 月之后便 产生了革命性的转变。1 9 9 5 年博士生拉里佩奇开始专心研究搜索引擎技术， 经过两年多时间的研究，他注册了一个域名- g o o g l e c o r n ，同年1 2 月，g o o g l e 公司在佩奇和布林的共同参与下正式成立了。 国家“九五 重点科技攻关项目“北大天网”是中文编码和分布式中英 文信息发现的研究结晶，北大分布式系统研究室与计算机系网络负责研发， 在1 9 9 7 年1 0 月2 9 日正式在c e r n e t 上向公众开放搜索功能。于2 0 0 0 年春 季成立了该项目的研发课题团队，利用教育网优势收录了大量的网页，同时 其邱检索功能非常强大。该项目的研究经费来自国家的一些重点研发项目。 取得了一定的成功。 毕业于北京大学的两位业内人士，获得过超链分析专利、拥有在i n f o s e e k 工作的宝贵经历、资深工程师李彦宏和校友友徐勇合作在北京创立了百度 ( b a i d u ) 公司。成立时间是2 0 0 0 年初。紧接着百度公司推出了其自主研制 的产品b a i d u c o m 搜索引擎b e t a 版，在这之前百度专门为其它门户网站如新 浪、搜狐、t o m 等提供搜索引擎服务，它的正式产品b a i d u 搜索引擎是在公 司成立将近两年之后发布的。中文搜索是其产品的主要功能。当然，还提供 了其它有特点的辅助服务，如网页快照、输入条提示、f l a s h 搜索等。产品推 出后不久，公司实施了一项计划，该计划使产品得到不断的完善，甚至比较 优秀s 】。 2 3 搜索引擎类别 由于搜索引擎技术的不断发展和用户的需求不断增多，一些不同于传统 类型的搜索引擎也相继出现了，关于这些方面的研究也在逐渐加深。学术界 8 哈尔滨i ：w 人。孚? 硕十学何论文 出现了越来越多与搜索引擎有关的新名词，如智能搜索引擎、个性化搜索引 擎、垂直搜索引擎等【7 】。 虽然各种搜索引擎的应用领域和表现形式有所不同，但要是按照搜索引 擎的工作原理来划分类别的话，可以把搜索引擎分成两类。 通过技术手段来实现的信息检索系统，谷歌公司就是一个典型的例子， 它处理信息的过程都是通过程序自动进行的，先是利用“蜘蛛程序”在互联 网上获取信息并存入数据库中，为了提高查询效率需要建立文档索引数掘库。 然而“蜘蛛程序”的工作是周期性的，也就是说互联网上新出现的信息可能 没有被及时存入数据库中。用户检索到的是在数据库中存放的并且处理好的 信息资源。一些规模较大的搜索引擎公司存入了数量相当大的网页，可以为 用户提供丰富的资源。 通过人工录入的方式实现的信息检索系统，雅虎就是其中的代表。这类 搜索引擎并没有“蜘蛛程序 ，它的数据来源是其它网站主动提供的。其它网 站向其提交该网站的关键字和一些特征词，按照一定的类别存储到数据库中， 再经过人工处理之后，这些数据便可以被用户检索。相比于第一类搜索引擎 返回的大量结果，这类搜索引擎具有针对性更强、信息更集中的特点。方便 用户逐级浏览。 真正意义上的搜索引擎是可以通过程序在互联网上获取信息并能自动处 理信息的检索系统，目前，许多搜索引擎都具备上述的两类功能，所以并没 有对其进行严格的划分。如果划分也是根据经营理念的不同。单从概念上划 分是没有实际意义的。 多元搜索引擎和集成搜索引擎的操作方式与上述两种均不相同，在此做 简单的介绍。它们是由上述两类搜索引擎通过一些技术的改变而形成的。但 是它们的技术原理和提供的服务大体是相同的。多元搜索引擎并不建立自己 的文档索引库，用户向多元搜索引擎提交查询请求时，它调用其它独立的搜 索引擎并按照自己的策略来选择信息从而形成查询结果返回给客户端。但是， 其技术发展的还很不成熟，只是结果会比较丰匐s 】。虽然此类搜索引擎存在 的数量比较多，但受到人们的认可程度还不够高。在搜索引擎竞争同益激烈 的今天，它需要完善很多才能取得成功。独立的搜索引擎更受人们的欢迎， 取得的优势非常明显。 9 哈尔滨。r 种人学硕十学何论文 2 4 搜索引擎基本构成 搜索引擎是通过互联网建立一个整理好的网页索引数据库，实际上检索 的是预先整理好的该索引库中的信息资源。按照现在的定义，一些大型而且 比较成熟的搜索引擎，一般指的是存储了互联网成千上亿个网页信息，而且 能够将网页中的一些重要的词语( 即主题词) 与文档建立索引关系，实现建 立索引数据库并对全文进行索引的搜索引擎。如果用户想要查询一些查询词 的相关信息的时候，在数据库中的页面内容中包含了这些查询词的网页都将 被视为处理的对象。搜索引擎会有一套自己的排序算法，经过复杂计算后( 一 般时间较短) ，这些网页或文档按照权重的大小形成排序结果列表提供给用户 参考s l 。 搜索引擎工作的基本步骤，一般分三个步骤：利用“蜘蛛程序 从互联 网上抓取网页、根据网页建立索引库、根据索引数据库处理用户请求。 图2 1 描述了其基本结构： 口婶习 雁叫 p 、 一一二一甄 jl 锄 ： 堕 爿 酚( 卜一 图2 1搜，索引擎系统结构图 ( 1 ) 获取信息 获取信息的一个主要工具是“蜘蛛程序 ，它能够从互联网上根据链接信 l o 岛警圄 哈，j ；滨f 、2 人导：硕十字：何论文 息和其他相关信息收集网贞，它能够按照预先设定好的规则访问互联网，以 一个网页作为入口，进入到其它链出页面进行爬取访问。每次都做同样的操 作，直到程序结束为止，爬取到的网页提交给后台数据库。 ( 2 ) 处理信息 获得网页后，是信息处理阶段，利用搜索引擎自带的系统程序处理这些 获得的信息。包括：获取网页的相关信息( 如网页链接地址、编辑方式、分 析页面内容、更新时间、主题词所处的位置、与数据库中网页的关联、文档 长度等) ，利用事先设定好的的相关度计算方法进行进行有目的的运算，如果 该算法是与链接有关，要事先计算好该网页的初始权重，计算之后这些主题 词、初始权重与文档内容建立索引。 ( 3 ) 排序列表 用户启动搜索引擎搜索功能并输入查询词后，遍历索引数据库，找与到 查询词相关的任何信息，接着提取出与这些项目相关的文档。再利用公式计 再次计算文档的最终权值，权值的大小是排序前后的重要依据，该因素会对 排序结果产生最直接的影响。接下来的处理相对简单，将之前生成的文档摘 要和链接地址直接在浏览器中显示提交给客户端。 搜索引擎的信息资源虽然只来自互联网，可是每个搜索引擎的执行效率 和侧重点不同，这样在网页选取上也各有所好，根据网页的特点产生了不同 的排序策略。一个规模较大的搜索引擎存储的网页索引数量至少有几千万甚 至几十亿，数据量极其巨大，是一般服务器无法存储的。然而，互联网的信 息浩瀚如海，不可能把所有的信息都能获取到( 至少现在的技术是做不到的) ， 能得到总网页的4 0 已经做到了极致。但是，搜索引擎不止一家，他们根据 自身的喜好，爬取尽量多的网页，这样能够与其它搜索引擎互相弥补对方没 有爬取到的网页。这也是不同搜索引擎存在的一个因素。 客户端输入框是搜索引擎提供给用户使用的接口，它的用途是输入用户 查询的句子、返回查询的相关内容、供用户参考并做出分析等。最重要的目 的是为用户使用搜索引擎提供方便。客户端输入框也会有一些不同，分为简 易和复杂，简易客户端只提供输入文本框和查询按钮，比较复杂的客户端接 口可以对查询提出条件。返回结果生成后，系统将结果以列表的形式提交给 客户端，每一项主要包括摘要、文档标题、链接地址等信息，排序的依据是 l l 哈尔滨r 科人学硕+ 学何论文 相关度的大小。 2 5 搜索引擎效率