（管理科学与工程专业论文）搜索引擎技术改进及其行业发展对策研究.pdf

搜索引擎技术改进及行业发展对策研究 摘要 互联网最基础的功能是提供信息。目前互联网上的信息已是海量，搜索引 擎是网民在信息海洋中搜寻信息的助手，是互联网上不可或缺的工具和基础应 用之一。在中国这样一个网民快速增长的国家，加快搜索引擎技术进步和推动 其行业的快速发展，具有十分重要的现实意义。 本文在对搜索引擎技术以及其行业发展深入调研的基础上，分析了搜索引 擎行业发展概况，搜索引擎当前的技术特点，以及搜索引擎行业面临的优势。 同时，指出了搜索引擎技术和行业发展中存在的主要问题。 在此基础上，本文提出了改进搜索引擎技术的两项方案：基于小波和图像 特征倒排图像搜索和基于用户浏览反馈的个性化结果排序方案。同时，本文也 提出了推动搜索引擎行业发展的若干条对策建议：加快发展垂直搜索引擎，发 展移动搜索，积极发展搜索引擎上下游产业，加强搜索引擎人才队伍建设，加 大国家对搜索引擎行业扶持力度，加快搜索引擎行业立法等。 本文在综合分析搜索引擎技术及其行业发展现状、拥有的优势及存在的问 题基础上，提出了具有针对性的技术改进方案和行业发展对策建议，这对推动 搜索引擎行业健康、持续的发展具有一定的实际意义和参考价值。 关键词：搜索引擎；图像搜索；个性化 r e s e a r c ho nt h et e c h n i c a li m p r o v e m e n t sa n dt h ei n d u s t r y d e v e l o p m e n t o fs e a r c he n g i n e a b s t r a c t t h eb a s i cf u n c t i o no fi n t e r n e ti sp r o v i d i n gi n f o r m a t i o n c o n s i d e r i n gt h em a s s o fi n f o r m a t i o no nl i n e ，t h es e a r c he n g i n eb e c o m e st h em e t h o df o rs e e k i n gu s e f u l i n f o r m a t i o no u to ft h em a s s ，a n di n d i s p e n s i b l em e t h o da n db a s i ca p p l i c a t i o n i n c h i n a ，t h eg r o w i n gp o p u l a t i o no fn e t i z e n sm a k ei tn e c e s s a r yt oi m p r o v es e a r c h e n g i n et e c h n o l o g ya n d t h i si n d u s t r y t h i sp a p e ra n a l y z e st h ed e v e l o p m e n to fs e a r c he n g i n ei n d u s t ya n d i t s t e c h n o l o g yb a s e do nt h ei n v e s t i g a t i o n t h e ni tp o i n t s o u tt h ea d v a n t a g ei nt h e i n d u s t r ya n dt h ee x i s t i n gp r o b l e m s b a s e do nt h i s ，t h i sp a p e rp u t sf o r w a r dt w os u g g e s t i o n st oi m p r o v es e a r c h e n g i n et e c h n o l o g y f i r s t ，t e x ts e a r c ht h r o u g hw a v e l e ta n di m a g ei n v e r t e d s e c o n d ， r a n k i n gs e q u e n c eb a s e do nu s e rp r e f e r e n c e a l s o ，t h i sp a p e rp r o p o s e s s e v e r a l s o l u t i o n st od e v e l o ps e a r c he n g i n ei n d u s t r y , s u c ha s ，d e v e l o p i n gv e r t i c a ls e a r c h ； m o b i l es e a r c h ；d e v e l o p i n gu p s t r e a ma n dd o w n s t r e a mi n d u s t r i e s ；c u l t i v a t i o n o f t a l e n t s ；g o v e r n m e n ts u p p o r t ；l e g i s l a t i o no f s e a r c he n g i n e b a s e do na n a l y s i so ns e a r c he n g i n ei n d u s t r y ，i t st e c h n o l o g y ，a d v a n t a g ea n d e x i s t i n gp r o b l e m s ，t h i sp a p e rg i v e sa d v i c ea n ds o l u t i o n s ，w h i c hh a sr e f e r e n c ev a l u e f o rp r o m o t i n gs e a r c he n g i n ei n d u s t r yc o n t i n u e dd e v e l o p m e n t k e y w o r d s ：s e a r c he n g i n e ：g r a p h i cs e a r c h ：u s e rp r e f e r e n c e 图表清单 图卜1 本文框架结构2 图6 一1 个性化排序与一般排序实验结果对比3 0 表6 1 个性化排序用户满意度实验结果2 9 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得 金罡王些盔堂 或其他教育机构的学位或证书而使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：f i 兰了霉 签字日期：2 0 0 7 年阳l , e i 学位论文版权使用授权书 本学位论文作者完全了解金壁王些太堂有关保留、使用学位论文的规定，有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权金胆王些太堂可 以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：f 习霉 签字日期：2 0 0 7 年4 月i b 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： ，锗黧 枷1 孙飙 特别声明 本学位论文是在我的导师指导下独立完成的。在研究生学习期间，我的导 师要求我坚决抵制学术不端行为。在此，我郑重声明，本论文无任何学术不端 行为，如果被查出有任何学术不端行为，一切责任完全由本人承担。 学位论文作者签名：匀善 签字日期：2 斫年乎月6 日 致谢 在合肥工业大学预测与发展研究所的两年多的研究生学习生活，让我不仅 在思想和能力上有了很大提高，而且各方面都得到了发展，这是一段十分值得 珍惜的时光。 首先要感谢我的导师杨皖苏副研究员。两年多来，杨老师对我严格要求， 给我孜孜不倦的耐心教导，督促我学好扎实的理论基础，并鼓励我积极参与科 研活动，对我的成长倾注了大量的心血。在杨老师的悉心培养下，我的综合素 质有了很大的提高，这使我受益终生。杨老师渊博的学识、严谨的治学态度、 敏锐的学术思想以及积极开拓的科研精神是我终身学习的楷模。在平时生活中， 杨老师为人谦和，平易近人，给了我莫大的关心和帮助。谨借此机会，向杨老 师致以衷心的感谢和深深的敬意。 本文是在杨老师的悉心指导下完成的。本论文的写作，杨老师倾注了大量 心血。从论文的选题、写作的角度到论文整体框架的构思，杨老师都给予了精 心指导，提出了关键性的意见；在论文初稿完成后，杨老师又对论文的结构、 学术观点、语言措辞以及标点符号等各个方面进行了仔细的斟酌与修改，严格 把关，不放过任何一个细节，精益求精。 本论文的完成还要感谢严鸿和老师，他给了我许多无私的指导和帮助，使 我收获至大。在此，谨向严鸿和老师表示衷心的感谢。 在读研究生期间，在学习和生活方面还得到了刘心报、毛家杰、吕正阳、 荣威等管理学院和研究生院的领导和老师们的培养和帮助，在此对他们表示衷 心的感谢。 两年多来，得到工作室同学的帮助，在此一并表示感谢。 最后我要衷心感谢我的父母，他们为我提供良好的物质基础，给予我精神 鼓励，使我以良好的状态完成学业。 作者：闰冬 2 0 0 9 年4 月于合肥工业大学 第一章绪论 1 1 研究背景及其意义 互联网最基础的功能即提供信息。目前互联网上的信息已是海量，搜索引 擎则是网民在汪洋中搜寻信息的工具，是互联网上不可或缺的工具和基础应用 之一。 2 0 0 8 年1 月，中国互联网络信息中心在北京发布第2 1 次国际互联网络 发展状况统计报告【l 】，调查结果显示，目前2 1 亿网民中使用搜索引擎的比 例是7 2 4 ，即已有1 5 2 亿人从搜索引擎获益，半年净增加3 0 8 6 万人。位列 网络应用中网络音乐、即时通信、网络影视和网络新闻之后的第五位，高于电 子邮件。与其他国家相比，由于中国互联网仍旧是娱乐功能占主体，总体网民 的搜索引擎使用率偏低。在美国，搜索引擎使用率已经达到9 1 。在中国这样 一个网民快速增长和以年轻网民主导的国家，搜索引擎用户将会继续增长。对 于拥有核心技术和海量用户的搜索引擎行业，发展前景令人看好。 随着信息化进程的加快，网络信息的爆炸式增长，搜索引擎行业迎来了前 所未有的发展机遇。但与此同时，搜索引擎在技术和行业发展上面临着诸多问 题的制约。这些问题的产生有来自搜索引擎先天的原因，也有随着使用的深入 而产生的。如何应对这些问题，并产生有效的应对方案，是整个行业亟待解决 的课题。 未来的时代是搜索的时代，脱离搜索引擎而进行盲目浏览是不可想象的。 今后几年将是搜索引擎行业发展的关键时期。搜索引擎行业的快速发展，一方 面对我国的经济社会有巨大的推动作用。另一方面，也帮助用户更有效地使用 互联网，进而发挥出互联网的核心优势。所以，对搜索引擎技术和行业发展的 研究，具有很大的实用价值和社会价值。 在本文写作前，本人收集了较丰富的有关搜索引擎技术发展现状和最新的 行业发展动态的资料。同时还查阅了大量相关的统计资料、报刊文章和相关中 外专著，在导师的指导下，经过深入思考和反复讨论，本人对如何促进搜索引 擎的健康发展形成了自己的观点。 本文通过对搜索引擎技术和行业的现状、当前的优势及面临的主要问题进 行深入的分析，经过认真思考，对搜索引擎技术改进和行业发展提出了相应的 对策建议。希望本文能为搜索引擎行业发展问题和技术进步做出一点有益的探 索，也希望本文所提出的见解能为搜索引擎技术和行业发展提供一些有价值的 借鉴。 1 2 本文框架结构 图卜1 本文框架结构 1 3 本文主要创新点 本文对搜索引擎技术和行业发展进行了一定的探索和研究，创新点主要体 现在以下几个方面： ( 1 ) 提出了提高图像搜索准确率的基于小波和图像特征倒排的新的图像搜 索方法。用小波对图像预处理，提取出图像颜色、纹理、形状三特征，对这三 特征进行倒排处理，查询时针对这三特征进行查询，可以大大改善图像的查找 精度。 ( 2 ) 提出了提高用户查询满意度的个性化排序方案。通过建立用户信息表和 用户浏览兴趣表数据库，对用户浏览过程中表现浏览兴趣的习惯进行记录迭代， 当用户再次查询时将兴趣表和一般查询进行混合计算，从而返回符合用户个性 化的查询结果。 2 ( 3 ) 提出加快发展垂直搜索引擎，拓展新的盈利模式。具体包括：成为行业 交易中介平台；为相关行业提供有效搜索数据；对行业用户提供相关广告推荐。 ( 4 ) 提出搜索引擎行业要依托搜索引擎主业的优势，积极拓展其行业链。具 体包括：向上游拓展，发展传媒事业；横向延伸，发展搜索的企业级应用，为 企业定制搜索服务；向下游拓展，发展电子商务事业。 3 第二章搜索引擎行业发展和当前商业模式概况 随着互联网信息的日益膨胀，人们在互联网中寻找信息必须依赖搜索引擎 作为工具。搜索引擎在人们生活、学习中的作用日渐增强。 2 1 搜索引擎组成 搜索引擎由搜索器( r o b o t ) 、索引( i n d e x e r ) 、检索器( s e a r c h e r ) 和用户接口等 四个部分组成 2 】。系统首先由搜索器收集网页的内容；然后索引器分析收集内 容，建立索引；再由检索器响应用户的检索请示，用户输入关键字后，搜索器 要用这个检索词与建立的索引器匹配，匹配后作相关性排序；最后通过用户接 口将排序结果送给用户。 1 、搜索器 搜索器在互联网中漫游，发现和搜集信息。它是一个计算机程序，日夜不 停地运行。它要尽可能多、尽可能快地搜集各种类型的新信息，同时互联网信 息更新很快，它还要定期更新已搜集过的旧信息，以避免死连接和无效连接。 搜索器常用分布式并行计算技术，以提高信息发现和更新的速度。 2 、索引器 索引器理解搜索器所搜索的信息，从中抽取出索引项，用于表示文档以及 生成文档库的索引表。索引器读入搜索器生成的f u l l t e x t 文件，首先进行分词 处理生成索引项，并作归并排序，生成i n v 和i n d e x 文件。i n v 文件为倒排表， 即由索引项查找相应的文档；i n d e x 文件存储分词与倒排表的对应关系，内容 为分词在倒排表中相应的文档块起始地址，含有该词的文档数量等信息。索引 器使用集中式索引算法或分布式索引算法。当数据量很大时必须实现即时索引， 否则跟不上信息量急剧增加的速度。索引算法对索引器的性能( 如大规模峰值查 询时的响应速度) 有很大的影响。一个搜索引擎的有效性在很大程度上取决于索 引的质量。 3 、检索器 检索器根据用户的查询在索引库中快速检索出文档，进行文档与查询的相 关度评价，对要输出的结果进行排序，并实现某种用户相关性反馈机。制检索 器通常支持多种语法规则，如逻辑操作符a n d 、o r 、n o t ，“+ 等。对于每 个索引项，匹配i n d e x 文件，查询倒排表中包含该索引项的文档，并对所有找 出的文档进行集合运算，将结果集按照基于内容和基于链接分析的方法进行相 关度评价并排序，最大限度保证检索结果与用户查询串的高相关性，将最终形 成的有序文档结果集合返回给用户接口。 4 4 、用户接口 用户接口的主要作用是输入用户查询、显示查询结果、提供用户相关性反 馈机制。其主要目的是方便用户使用搜索引擎，高效率、多方式地从搜索引擎 中得到有效、及时的信息。用户接口的设计和实现使用人机交互的理论和方法， 以充分适应人类的思维习惯。搜索引擎是某些网站提供的一项服务，它将 i n t e r n e t 上的网站和网页信息进行收集、整理和组织，以帮助用户找到所需信息。 事实证明，在浩如烟海的i n t e r n e t 上查找你所需要的信息，使用优秀的搜索引 擎常常可以事半功倍。 2 2 搜索引擎分类 l 、目录索引类搜索引擎 基于目录的搜索引擎是按目录分类的网站链接列表。数据库由人工建立， 编辑人员访问某个w e b 站点后，根据站点的内容和性质归类，并把站点的u r l 和描述放入该类别。当用户用某个关键字查询时，搜索软件只能在这些描述 中搜索。该类搜索引擎查准率高，查全率低，搜索范围较小。用户完全可以 不进行关键字查询，仅靠分类目录也可找到需要的信息。目录索引中最具代 表性的是y a h o o 。其他著名的还有o p e nd i r e c t o r yp r o j e c t ，l o o k s m a r t ，a b o u t 等。国内的搜狐、新浪、网易也属于这一类。 2 、全文搜索引擎 全文搜索引擎是名副其实的搜索引擎，它们从互联网上提取各网站信息 ( 以网页文字为主) 建立数据库，通过数据库检索与用户查询条件匹配的相关记 录，按一定的排列顺序将结果返回给用户。国外具有代表性的有g o o g i e ， 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 ) 。全文搜 索引擎擎信息量大，更新及时、无需人工干预，但返回信息过多，有很多无 关信息，用户必须从结果中进行筛选。 3 、元搜索引擎 元搜索引擎在接受用户查询请求时，同时在其他多个引擎上进行搜索，并 将结果返回给用户。元搜索引擎没有存放网页信息的数据库，当用户查询关键 字，它把用户的查询请求转换成其他搜索引擎能够接受的命令格式，并行访问 数个搜索引擎来查询这个关键字，并把这些搜索引擎返回的结果经过处理后返 回给用户。著名的元搜索引擎有i n f o s p a c e ，d o g p i l e ，v i v i s i m 等，中文元搜索 引擎中具代表性的有搜星搜索。 2 3 搜索引擎行业发展与盈利模式概述 第一代搜索引擎，以人工分类的目录分类为主，代表厂商是y a h o o ，其特 点是用人工的方式把网站放在各种目录下，允许客户通过各种方式找到想要的 网站，现在这种方式依然还在采用。但随着网络应用技术的发展，客户不再满 足于对网站分类和摘要的简单查找，更希望对内容进行查找，于是就出现了关 键字查询，即第二代搜索引擎。这时最有代表性的是g o o g l e ，它使用关键字网 页搜索，内容可以覆盖互联网全部网页内容。 目前搜索引擎的主要盈利模式是基于竞价排名的广告模式，具体广告主在 向垂直搜索引擎购买该项服务后，通过注册一定数量的关键字，按照付费最高 者排名靠前的原则，购买了同一关键字的网站按不同的顺序进行排名，出现在 网民相应的搜索结果中。之后根据点击效果，搜索引擎企业向广告主收取相应 的费用p j 。 2 4 当前各主要搜索引擎现状与特点分析 l 、g o o g l e g o o g l e ( h t t p ：w w w g o o g l e o n ) 是业界著名的搜索网站，g o o g l e 获得过最受 欢迎搜索引擎奖、最佳搜索引擎技术奖、最佳图像搜索技术奖等多项荣誉。不 论是中文还是英文搜索都同样出色，而且还有业内公认的高水平图像搜索技术 与日渐成熟的目录搜索功能。g o o g l e 是易用性最强的搜索网站，搜索速度快而 且提供了最丰富的高级搜索功能。除了不支持自然语言和通配符搜索以外，其 他不论是单个汉字、多个汉字或者一个句子，都可以作为关键字在g o o g l e 上进 行搜索。而且g o o g l e 还支持关键字的简繁转换功能，您只需要输入简体或者繁 体的关键字，就可以同时在简体中文网页和繁体中文网页中查找。 g o o g l e 的搜索结果的排名准确性相当高。这归功于g o o g l e 根据网页的相 关性、网站内部的链接结构及受欢迎的程度，来确定搜索结果的排列顺序的专 利技术p a g e r a n k 。与传统排名方式不同的是，它能确保优秀的网站总能够排在 搜索结果的前列，这也是用户使用g o o g l e 往往能够更快更容易地命中搜索目标 的原因。 死链率比较高是g o o g l e 最大的问题，中文网站检索的更新频率不够高， 不能及时淘汰已经过时的链接。虽然通过“网页快照 功能，可以减少目标页 面不存在的现象，但g o o g l e 的“网页快照”功能在国内经常出现不可访问的问 题，令用户无所适从【4 j 。 2 、新浪 新浪搜索( h t t p ：s e a r c h s i n a c o m o n ) 将网页、网站和新浪自己的内容结合 在一起，网页搜索使用g o o g l e 的搜索技术，网站搜索依靠制作人员与网友人工 6 编辑的网站目录来实现。无论是网页搜索还是网站搜索，都能找到比较多的结 果，而且准确性也不错。新浪搜索在使用过程中缺少提示信息，并且由于曾经 多次更换搜索技术提供商，对用户的影响较大。新浪搜索的帮助文档虽然很详 细，但其中的内容有些并没有及时更新，介绍的还是过时的搜索方法。此外， 新浪的网站搜索死链率较高，而且由于编辑水平的参差不齐，有许多网站的说 明都比较简单和不清楚。在网站数量有增无减、缺乏科学的排名的情况下，搜 索效果不太理想。 3 、雅虎 雅虎中国( h t t p ：o n y a h o o c o m ) 支持网页、网站搜索，搜索速度快而且准确 性比较高。在人工分类目录检索服务方面，雅虎中国有着比较丰富的经验，从 1 9 9 5 年开始积累的分类目录服务信息和经验都是其他提供商所无法比拟的，雅 虎中国的网站搜索的准确性也体现出了这种优势，并且其网页搜索功能的表现 也相当不错。 僵雅虎中国的搜索结果死链率很高，而且缺少一些应有的高级搜索功能。 另外，该搜索的易用性有待提高，虽然在5 月份升级后改善了网页的界面，严 格控制搜索页面中的排名广告，规定每次搜索结果中的广告数量不能超过5 个， 但用户打开雅虎中国的首页时还是要受到一些影响。而且，对搜索结果的描述 和在用户搜索过程中的提示说明也不太清晰、明了，离雅虎“关注用户体验”这 一宣传口号，还有一定的距离。 4 、网易 网易搜索( h t t p ：s e a r c h 1 6 3 t o m ) 支持网页、网站搜索，网页搜索使用的是 百度的搜索技术，除了分页方式以外，其他的返回结果都与百度一样，但推荐 的站点比较少。值得一提的是，网易的网站搜索功能相当不错，虽然也有一些 已经过时的网站链接，但是分类目录中收录的网站还是有一定的代表性，大多 是该分类中的知名站点。不过网易搜索也有一些不尽如意的地方，首先，网易 搜索的操作界面不太方便，在使用的过程中也缺少提示。在使用多个关键字同 时搜索时，如果超过8 个关键字就无法处理，而且搜索的结果没有“网页快照” 功能。 5 、搜狐 搜狐( h t t p ：s e a r c h s o h o t o m ) 支持网页、网站搜索，在国内享有很高的声 誉，曾经一度是微软i e 浏览器使用的默认中文搜索网站，在i e 浏览器地址栏 直接输入关键字即可进行搜索。搜狐的网页、网站搜索准确性都比较高，但除 了通过人工编辑的网站搜索功能值得推荐以外，其他功能都或多或少存在一些 问题。搜狐的网页搜索准确性较高，但搜索结果中重复的问题比较严重，虽然 7 重复的站点未必是同一个网页，但都属于同一个网站。另外，搜狐的搜索结果 中没有标出关键字，查阅起来非常不便。 6 、慧聪 长期以来，国内的搜索技术提供厂商很少，百度作为先驱者，占据了大部 分份额。到了2 0 0 2 年，国内搜索市场中出现了一匹黑马，那就是慧聪搜索( h t t p ： w w w i s e a r c h s i n o b n e t c o r n ) 。短短一年时间内，慧聪搜索在国内各大网站上实 现了大规模的应用，市场占有率迅速增长，国内三大门户网站之一的新浪网也 曾经采用过其技术，而目前包括2 6 3 和中华网等大型站点在内的许多大型网站 也都采用了慧聪搜索的技术【5 】。 但遗憾的是，慧聪除了易用性不错、搜索结果的准确性比较高以外，很多 方面都不尽如人意。它只能够使用有限的几种关键字，缺乏高级搜索功能，死 链率也不低，而且搜索结果中重复的网站较多。另外比较奇怪的是，在使用慧 聪进行搜索时，有时会发生无法找到任何网页的错误。2 6 3 网站采用的也是慧 聪搜索的技术，但其出现错误的几率比慧聪搜索低不少。 7 、百度 百度( h t t p ：w w w b a i d u t o m ) 是中国互联网领先的搜索技术提供商，在国内 提供搜索功能的大型站点中，有许多网站采用的是百度的搜索技术。除了提供 网页搜索以外，百度还支持新闻、m p 3 、f l a s h 的搜索，另外还有搜索特定关键 字的“主题搜索”和网站目录导航功能。在显示搜索结果时，有与g o o g l e 的“网 页快照 功能相同的“百度快照”，搜索速度快，返回结果的准确性也相当高， 中文网页搜索的结果绝对能够配得上百度在国内的盛名。 百度搜索的网站分类目录比较落后，缺乏应有的检索功能，并且百度的搜 索结果中死链率也较高，虽然这是所有检索网页总数量多的搜索网站难以避免 的问题，但是对于一个专注于中文网页的搜索网站来说，还是应该进一步提高。 此外，百度的高级搜索功能也是需要改善的地方。 百度搜索结果的准确性较高，这与其前十个链接都是编辑整理的推广链接 有很大关系。这种通过支付费用将自己的链接安插在前十名的作法，是否会影 响百度的搜索结果，可以说是一个见仁见智的问题。部分用户对此可谓是深恶 痛绝，但另外一些用户却认为，这些广告链接只要能符合搜索目的的话，也会 具有一定的价值，毕竟它们都是同类站点中比较有实力的【6 】。 8 、天网 天网搜索( h t t p ：e p k u e d u c n ) 是国家“九五 重点科技攻关项目“中文编 码和分布式中英文信息发现”的研究成果。天网搜索提供了网页、网站搜索和 f t p 服务器文件搜索功能，网页搜索功能除能够搜索互联网上的网站以外，还 8 可以搜索到部分其他搜索网站没有的教育网中的内容。另外，天网搜索还提供 了类似于g o o g l e 的“网页快照”功能的“历史网页”，但不同的是，该功能不 只是存储目标网页最后一次检索的内容，而是存储每次检索到的更新内容，即 使目标网页己经更新多次，也有可能被检索到一3 。 9 第三章搜索引擎当前使用技术分析 搜索引擎技术门槛非常高，它综合运用了当前计算机行业的很多热门技术， 在本章将对这些技术进行逐一分析。 3 1r o b o t 技术 “机器人 ( r o b o t ) 是一种自动运行的软件，其功能是搜索i n t e r n e t 上的网 站或网页。这种软件定期在i n t e r n e t 上漫游，通过网页间的链接，顺序搜索新 的地址，当遇到新的网页时，就给该网页上的某些字或全部字做上索引并把它 加到搜索引擎的数据信息中，由此，搜索引擎的数据信息得以定期更新。目前 的搜索引擎广泛地使用了r o b o t 技术【8 j 。 1 、r o b o t 搜索策略 要建立全面的索引数据库，必须对w w w 进行系统全面的遍历。可将w w w 作为有向图处理，每个页面看作图的节点，页面中的超链接看作图的有向边， 因此，可以使用有向图遍历法对其进行遍历，有向图遍历法分为深度优先算法 和广度优先算法【9 1 。从r o b o t 的发展历程来看，它主要有以下几种搜索策略： ( 1 ) i p 地址搜索策略。先赋予r o b o t 一个起始的i p 地址，然后根据i p 地址 递增的方式搜索本i p 地址段后的每一个w w w 地址中的文档，它完全不考虑 各文档中指向其它w e b 站点的超级链接地址。优点是搜索全面，能够发现那些 没被其它文档引用的新文档的信息源；缺点是不适合大规模搜索。 ( 2 ) 深度优先搜索策略。深度优先搜索是在开发r o b o t 的早期使用较多的方 法。它的目的是要达到被搜索结构的叶结点( 即那些不包含任何超链的h t m l 文件) 。在一个h t m l 文件中，当一个超链接被选择后，被链接的h t m l 文件 将执行深度优先搜索，即在搜索其余的超链接结果之前必须先完整地搜索单独 的一条链。深度优先搜索沿着h t m l 文件上的超链接走到不能再深入为止，然 后返回到某一个h t m l 文件，再继续选择该h t m l 文件中的其他超链接。当 不再有其他超链接可选择时，说明搜索已经结束。深度优先搜索的优点是能遍 历一个w e b 站点或深层嵌套的文档集合：缺点是由于w e b 结构相当深，有可 能造成一旦进去再也出不来的情况发生。 ( 3 ) 宽度搜索优先策略。在宽度优先搜索中，先搜索完一个w e b 页面中所 有的超级链接，然后再继续搜索下一层，直到底层为止。例如，一个h t m l 文 件中有三个超链接，选择其中之一并处理相应的h t m l 文件，然后不再选择第 一个h t m l 文件中的任何超链接，而是返回并选择第二个超链接，处理相应的 h t m l 文件，再返回，选择第三个超链接并处理相应的h t m l 文件。一旦一层 上的所有超链接都己被选择过，就可以开始在刚才处理过的h i m l 文件中搜索 其余的超链接。这就保证了对浅层的首先处理。当遇到一个无穷尽的深层分支 1 0 时，不会导致陷进w w w 中的深层文档出不来的情况发生。宽度优先搜索策略 还有一个优点，即它能在两个h t m l 文件之间找到最短路径。但是如果要遍历 一个指定的站点或者深层嵌套的h t m l 文件集，用宽度优先搜索策略则需要花 费比较长的时间才能到达深层的h t m l 文件。 2 、搜索程序专用协议 w e b 站点管理员和网页作者采取r o b o te x c l u s i o np r o t o c o l 协议或r o b o t m e t at a g 指令限制r o b o t 程序对站点网页的访问 1 0 】。 ( 1 ) r o b o te x c l u s i o np r o t o c o l 协议。w e b 站点管理员可以使用r o b o t s t x t 文件为来访的r o b o t 程序提供一个标准的访问策略，来指出站点的哪一部分可 以被r o b o t 访问。这个文件存储在w e b 站点的根目录。所以当r o b o t 访问一个 站点时，应该首先检查r o b o t s t x t ，如果这个文件存在，它便会按照这样的纪录 格式去分析： u s e r a g e n t ：幸，d i s a l l o w ：e g i b i n ，d i s a l l o w ：t r n p ，u s e ra g e n t 开头的行： 指出下面的禁止行适用于哪个r o b o t ，意味着该网站适用于所有的 r o b o t d i s a l l o w 开头的行，指出禁止访问的目录或子目录，列出的路径以及它 下面的子路径都对r o b o t 关闭。d i s a l l o w ：表示整个站点对外关闭。如果该站 的r o b o t s t x t 文件禁止r o b o t 访问，则r o b o t 将不对该站点进行处理。 ( 2 ) r o b o tm e t a 标记。r o b o tm e t at a g 允许h t m l 网页作者指出某一页是 否可以被索引，或是否可以用来查找更多的链接文件。该m e t at a g 放在h t m l 文件的h e a d 中。其格式如下： r o b o tm e t at a g 指令使用逗号隔开，可以使用的指令包括i n d e x 和i n d e x 指令指出r o b o t 是否可以对本网页进行索引；f o l l o w 指令指出r o b o t 是否可 以跟踪本网页的链接。r o b o t 应该遵守这些协议，避免访问r o b o t s t x t 以及r o b o t m e t at a g 内禁止访问的网页。 3 、r o b o t 优化技术 羹。( 1 ) 分布式系统方式来实现r o b o t 。w 曲数据量大且处在动态变化中， 魂n t e r n e t 网络传输环境复杂，要在单机上实现性能稳定、搜索效率高的r o b o t 存在一定困难。当搜索的页面数量很大时，单机的内存难以存放和维护u r l 线 性表，硬盘存放的网页内容文件太大将严重影响读写响应时间，单机所处的 i n t e r n e t 网络传输环境发生种种意外情况而导致超时或死机时，r o b o t 的稳定 性和健壮性无法保证；另外，单机实现r o b o t 时，也不能充分利用网络带宽来 提高效率。因此我们可采用分布式系统方式对i n t e r n e t 实现并行搜索。这种方 案可以有效地解决在单机上存在的各种问题，从而实现高效、稳定、可灵活配 置、伸缩性好的r o b o t 。 ( 2 ) 单一多线程相结合。采用多线程技术将待查询的站点分配给每个线程， 并行搜集信息资源，从而加快处理速度。由主线程启动各个搜索线程，各个搜 索线程在找到新的未搜索超链时，首先判断新超链的h o s t 是否与本线程正在搜 索的h o s t 相同，若相同则加入本线程的待搜索队列，否则加入主线程的待搜索 队列，并把地域相近的u r l 分配给同一个r o b o t 采集。 ( 3 ) 与服务器方协作。在获取服务器信任的基础上，开发生存于站点服务器 的r o b o t 。在服务器端跟踪服务器上文档的修改、删除、增加等情况，根据情 况向搜索引擎服务器主动发送信息。或在服务器上生成关于服务器文档变更情 况的特殊文件，并把需要更新的文档在本地进行预处理，当r o b o t 访问该服务 器时，首先浏览这个文件。采取这种方案，可以很大程度地减少网络流量。 ( 4 ) 对已经获取的u r l 充分处理。r o b o t 在运行过程中经常与u r l 列表交 互，由于u r l 列表非常庞大，为了提高r o b o t 与u r l 集合的交互效率，必须 对u r l 列表进行充分处理。 首先，管理拒绝r o b o t 访问的u r l ：当r o b o t 访问一个站点时，应该首先 检查r o b o t s t x t 。如果这个文件存在，应该按照这个文件中的规定进行访问，并 将不可访问的链接信息进行登记。 其次，u r l 的存储可以在存储占用空间以及访问速度两个方面进行优化。 在添加u r l 之前先把已获取的u r l 按字典顺序排列，只存储u r l 的增加部分， 可以减少数据库的存储量。利用h a s h 的方法存储，可以加速u r l 的访问。另 外，还要辨别出内容重复比。 最后，把从源u r l 集合中读取的u r l 根据既定规则分配给不同的r o b o t ， 均衡负载。 ( 5 ) 逐渐形成不同更新时间间隔的u r l 列表。由于不同的u r l 一般都具有不 同的更新时间间隔，在r o b o t 访问过程中，逐渐把u r l 根据其更新时间间隔归 并到不同的u r l 列表中，r o b o t 则依据时间间隔访问，提高r o b o t 的搜集效率。 ( 6 ) 根据网页权重有选择地选取重要地u r l 进行更新。目前网页数量增长 迅速，内容更新频繁，限于存储容量以及r o b o t 本身的时耗( w e b 容量大约是 1 5 t b ，每个月大约有6 0 0 g b 的网页更新) ，随时跟踪并更新所有网页几乎是不 可能的事情。对一个搜寻程序来讲，总是希望搜寻程序能取到最有价值的页面。 为了尽可能地获得最感兴趣的页面，在每次从u r l 队列中选择新的u r l 时， 就要尽可能地选择最为重要的页面【1 1 1 。把u r l 按其重要性排序，优先获取重 要网页。 4 、r o b o t 过滤技术 r o b o t 中使用了3 种过滤技术：u r l 级过滤、a n c h o r 上下文级过滤和页面 内容级过滤。 ( 1 ) u r l 级过滤。u r l 级过滤的主要任务是尽量过滤掉不需要的u r l 。其 1 2 过滤范围包括那些构造有误的不合法u r l 和那些虽然合法但是明显不是属于 所需下载的范围之内的u r l 。 ( 2 ) a n c h o r 上下文级过滤。超链接周围的文字能为链接页面的内容提供很 重要的提示信息。h t m l 文档下载完毕从中提取出超链接之后，提取超链接周 围前后若干字符。然后对这些文字进行分析，找出是否有所关心领域内的关键 字。该方法与u r l 级过滤联合使用。 ( 3 ) 页面内容级过滤。爬行初期，根据标注好的w e b 页面，对其中的关键 字计算出一个具有代表性的文档向量r d v 。爬行过程中，对下载的h t m l 文 档根据向量空间模型计算它与r d v 之间的相关度。如果相关度大于阈值，就 认为该文档属于搜索领域之内，保存该文档并且提取其中的链接，否则简单地 抛弃整个文档。对于相关度较高的文档，将继续参加r d v 的计算。 3 2 中文分词技术 1 、分词方法 为了提取关键字或者知识，必须分隔出单个的词和句子。计算机内部存储 的中文信息没有明显的词与词之间的切分标志，因此必须利用汉语中词的切分 规范将中文信息转化为词，即自动分词【l 引。以下简要介绍几种方法： ( 1 ) 逐词遍历法。逐词遍历法将词典中的所有词按由长到短的顺序在文章中 逐字搜索，直到文章结束。不管文章有多短，词典有多大，都要将词典遍历一遍。 ( 2 ) 正向最大匹配。其目的是将最长的复合词分离出来。假设自动分词词典 中的最长词条所含汉字个数为n 个，则取材料中当前字符串序数中的n 个字作 为匹配字段，查找分词词典，若词典中有这样一个n 个字长的词则匹配成功， 匹配字段作为一个词被切分出来；如果词典中找不到这样一个n 字长的词，则 匹配失败。在要匹配字段中去掉最后一个汉字，剩下的字符作为新的匹配字段， 进行新的匹配，如此下去，直到切分到成功为止，即完成一轮匹配，切分出一 个词，然后接以上步骤进行下去，直到切分出所有词。 ( 3 ) 逆向最大匹配法。这种方法又称为r m m 法，其基本原理和正向最大匹配 法相同，不同的是分词切分的方向与之相反，并且使用的分词词典也不同。逆 向最大匹配法从被处理文档的末端开始匹配扫描，每次取最末端的n 含字符作 为匹配字段，若匹配失败，则去掉匹配字段最前面的一个字，继续匹配。 相应地，它使用的分词词典是逆序词典，其中的每个词条都将按逆序方式 存放。在实际处理时，先将文档进行倒排处理，生成逆序文档。 然后，根据逆序词典，对逆序文档用正向最大匹配法。为了提高系统分词 的准确度，可以采用正向最大匹配法和逆向最大匹配法相结合的方法。先根据 切分标志对文档进行粗切分，把文档分解成若干个子段，然后再对这些子段用 正向最大匹配法和逆向最大匹配法进行扫描切分。如果两种分词方法得到的匹 1 3 配结果相同，则认为分词正确，否则，按最小集处理。 ( 4 ) 二次扫描法。二次扫描法的基本思想是取待处理材料中两个切分标志之 间的部分作为样本串。首先从该样本串中取两个汉字作为匹配串，检查分词词 典中是否有一个词的前两个汉字和该样本串相同，若有的话则取样本串的前三 个汉字作为匹配串，事先在分词词典中找可以匹配串的词，若有则重复下去， 直到进行n 个汉字为止( 设n 为词典中最长词所含汉字的个数) ，则切分出一个 n 字词；若没有则完成了一次扫描；把匹配中的最后一个汉字去掉，作为新的 匹配串，进行第二次扫描，第二次扫描是用m m 方法或r m m 方法进行。 ( 5 ) 基于频度的方法。这种方法不依靠词典，而是将文章中任意两个字同时 出现的频率进行统计，次数越高的越可能是一个词。这种方法可以很容易将专 业名词提炼出来。 2 、两种汉语分词方案 第一种方案针对提高分词精度，算法如下： 先将文章分词为字符串集，再采用优先大频率事件匹配的“最佳匹配法 ， 从字符串集中生成“预选词集 。根据“预选词集”并结合基于词典的某种方法 进行第二次分词，从而提高分词精度，而且解决了一些分词歧义问题。这种方 法能够识别大部分生词。 第二种方案保证分词的效率和速度。它基于这样的出发点：正向最大匹配 法与逆向最大匹配法相结合可以消除一部分交集性歧义，同时使用正向和逆向 最大匹配法，如果分词的结果相同就认为是正确的；不同的部分按可同时包含 两部分的最小长度串处理。但是这样基于词典的处理对未收入一记录的人名、 地名、专业术语效果不好，因而将其与基于无词典的频率统计法结合起来。这 样既发挥了无词典分词结合上下文识别生词的长处，又保证了基于词典分词方 法速度快、精度高的优点【l 引。 3 、汉语自动分词词典机制 目前有三种典型的分词词典机制：基于整词二分分词词典机制；基于t r i e 索引树分词词典机制；基于逐字二分分词词典机制。 ( 1 ) 基于整词二分分词词典机制。其结构通常分为三级，前两级为索引： 首字散列表。词首字散列函数根据汉字的国标区位码给出。通过一次哈 希运算即可直接定位汉字在首字散列表中的序号。首字散列表的一个单元包括 两项内容：入口项个数：以该字为首字的词的个数；第一入口项指针：指向第 一入口项在词索引标中的位置。 词索引表。因词的长度可变，故以选择不定长存储为宜；此外必须实现 对词的随机访问。这两条决定了必须建立词索引表。 词典正文指针。指向词在词典正文中的位置。词典正文是以词为单位的 1 4 有序表。通过词搜索表和词典正文的配合，很容易实现指定词在词典正文中的 整词二分快速查找。由于中文分词要用到逆向最大匹配法，所以有必要建立一 个倒排词典，并产生相应的倒排索引。 ( 2 ) 基于t r e e 索引数的分词词典机制。t r e e 索引树是一种以树的多重链 表形式表示的键树。面向英文的t r e e 索引树一般以2 6 个字母作为关键字，树 结点包含个数相同的指针。汉字接近7 0 0 0 个，如果采用同样的策略构造中文词 典，显然将造成指针的大量浪费。面向中文的t r e e 索引树的结点应允许指针 个数变化。基于t r 树的分词词典由三部分组成： 首字散列表。首字散列表的一个单元是所对应汉字的t r e e 索引树的根 结点。 t r e e 。t r e e