搜索引擎综述.doc

搜索引擎综述电子与信息工程系1006班 张 成U201012954摘要：对搜索引擎及其历史发展，搜索引擎的关键技术进行综合性的介绍，基于此，对搜索引擎的杰出代表Google的核心技术PageRank技术和超文本匹配分析技术进行简单探索，最后展望搜索引擎未来发展重要方向。关键词：搜索引擎 Google核心技术 信息检索Introduction of Search EngineElectronic and Information Engineering Class1006 ZHANG Cheng U201012954Abstract: To the search engine and its historical development, search engine of key technologies are comprehensively introduced, based on this, to the search engines outstanding representative Googles core technology using PageRank technology and hypertext matching analysis technology simple exploration, the future search engine future development important direction. Keyword: search engine Google core technology information retrieval1. 引言据统计，在短短20多年的时间里，Internet中产生的信息量相当于人类过去100年产生的信息总量，而且Internet上的信息量正以几何级数递增。搜索引擎已经成为人们进行Internet信息资源搜索必不可少的工具。鉴于此，笔者认为有必要对其进行综合性概述，让更多人对其有一个更全面的认识，从而能更好的运用搜索引擎，更希望引起大家对搜索引擎技术开发的兴趣。2. 搜索引擎的简单定义和原理搜索引擎是根据一定的策略、运用特定的计算机程序搜集互联网上的信息,在对信息进行组织和处理后，为用户提供统。检索服务的系搜索引擎一般由搜索器、分析器、索引器、检索器和用户接口等5个部分组成，如下图所示。1搜索器是一个机器人程序，其具有高效的搜索策略和高性能系统结构，能自动地在互联网中搜集信息下载到本地文档库。分析器对本地文档库进行分析以便于索引。文档分析技术包括分词、过滤和转换等。索引器的功能是理解搜索器所搜索的信息，从中抽取出索引项，将文档表示为一种便于检索的方式并存储在索引数据库中，生成文档库的索引表。检索器的功能是根据用户的查询要求在索引库中快速检出文档。进行文档与查询的相关度的评价，对将要输出的结果进行排序，并实现某种用户相关性反馈机制。其检索方法有以下几种：基于关键词的检索；基于概念的检索；基于内容的检索。用户接口的作用是为用户提供可视化的查询输入和结果输出界面，提供用户相关性反馈机制。在输出界面中，搜索引擎将检索结果展现为一个线性文档列表，其中包含了文档的标题、摘要，所在URL等信息。3. 搜索引擎的分类按照信息收集方法、服务提供方式和系统结构的不同，搜索引擎系统可以分成不同的类别。搜索引擎系统按其工作机制可以分为以下类别。（1） 机器人搜索引擎：由一个机器人程序以某种策略自动的搜索信息，下载在本地文档库进行分析，有索引器建立索引，对查询由检索器检索索引库，最后把查询结果返回给用户。（2） 目录式搜索引擎：由Web站点主动提交或用半自动方式收集信息，由人工对Web站点进行评价、分类，形成摘要，使其按树型作主题分类组织，从树根逐层向下形成各级分类，叶节点则包括指向Web信息资源的连接。目录搜索引擎中最具代表性的莫过于大名鼎鼎的Yahoo、新浪分类目录搜索。（3） 元搜索引擎：对用户的查询请求进行预处理，转换为底层搜索引擎能过处理的格式，向多个搜索引擎递交，在对各搜索引起的检索结果进行组合，排除重复，排序等处理后返回给用户。（4） 信息检索Agent：是智能化的程序，能够学习用户要求，具有智能性，主动性，协作性等特点。4. 搜索引擎的发展（1） 世界上第一个Spider程序是MIT Matthew Gray的World Wide Web Wanderer, 用于跟踪互联网发展规模。（2） 1993年2月，6个斯坦福大学学生想分析字词关系，以对互联网上的大量信息做更有效的检索。到1993年中，这已是一个完全投资项目，他们还发布一个供webmaster在自己网站上使用的搜索软件版本，即后来的Excite for Web Server。（3） 1994年4月，斯坦福的两名博士生，美籍华人杨致远和David Filo共同创办了Yahoo!Yahoo!几乎成为20世纪90年代的因特网的代名词。（4） 1995年一种新的搜索引擎形式出现了元搜索引擎。第一个元搜索引擎是Washington大学硕士生Eric Selberg和Oren Etzioni的Metacrawlar。（5） 1995年12月，DEC正式发布Alta Vista。Alta Vista是第一个支持自然语言搜索的搜索引擎，第一个实现高级搜索语法的搜索引擎。（6） 1995年9月26日，加州伯克利分校助教Eric Brewer、博士生 Paul Gauthier创立了Inktomi，1996年5月20日，Inktomi公司成立，强大的HotBot出现在世人面前。（7） 1997年8月，Northernlight搜索引擎正式现身。它曾是拥有最大数据库的搜索引擎之一，它是第一个支持对搜索结果进行简单自动分类的搜索引擎。（8） 1998年10月之前，Google只是斯坦福大学的一个小项目BackRub。1999年2月，Google完成了从Alpha版到Beta版的蜕变。（9） 1996年8月，sohu公司成立，制作中文网站目录，曾有“出门找地图，上网找搜狐”的美誉。（10） 2000年1月，两位北大校友，超链接专利发明人、前Infoseek资深工程师李彦宏与好友徐勇（加州伯克利分校博士后）在北京中关村创立百度公司。2001年8月发布百度搜索引擎Beta版。2001年10月22日正式发布Baidu搜索引擎，专注中文搜索引擎。（11） 2003年12月23日，原慧聪搜索正式独立运作，成立中国搜索。2004年2月，中国搜索发布桌面搜索引擎网络猪1.0（12） 2005年6月，新浪正式推出自主研发的搜索引擎“爱问”。（13） 2007年7月1日，全面采用网易自主研发的有道搜索技术，并且合并了原来的综合搜索和网页搜索。5. 搜索引擎的杰出代表Google的核心技术简介Google是有两个斯坦福大学学生Larry Page和Sergey Brin共同设计的，自从Google网站问世以来，逐月激增的访问人次、业界的推崇及市场的占有率，都足以证明其成功。笔者认为很有必要对其核心技术进行简单介绍，感受技术的力量。5.1PageRank算法搜索引擎在排序最终搜索结果时，必须首先给出排序的重要性尺度。2PageRank算法是Google搜索引擎对搜索结果的一种排序算法。它的基本思想主要来自传统文献计量学中文献引文分析，即一篇文献的质量和重要性可以通过其它文献对其引用的数量和引文质量来衡量，也就是说，一篇文献被其它文献引用越多，并且引用它的文献质量越高，则该文献本身就越重要。Google在给出页面排序时也有两条标准：一是看有多少超级链接指向它；二是要看超级链接指向它的那个页面中不重要。这两个直观想法就是PageRank算法的基础，也是Google搜索引擎最基本的工作原理。PageRank算法利用互联网独特的超链接结构和网络的拓扑结构来判断网页的重要性。PageRank算法原理中有一个重要的假设：所有的网页形成一个闭合的链接图，除了这些文档以外没有其他任何链接的出入，并且每个网页能从其他网页通过超链接达到。PageRank算法的具体实现可以利用网页所对应的图的邻接矩阵来表达超链接关系为此，首先写出所对应的图的邻接矩阵A为了能将网页的页面等级值平均分配给该网页所链接指向的网页，对各个行向量进行归一化处理，得矩阵PageRank算法的矩阵是将归一化矩阵A转置所得矩阵W这样形成的矩阵W被称为转移概率矩阵，它的各个列向量之和为全概率1，各个行矢量表示状态之间的转移概率转移概率矩阵与Markoff过程有着密切的联系。3转置的理由是，PageRank算法并非重视链接到多少页面，而是重视被多少页面链接各个网页的页面等级值PageRank的计算，就是求这个转移概率矩阵W的最大特征值所属的特征向量5.2超文本匹配分析技术4Google再排列其检索结果时，都会考虑每个网页的PageRank值，将重要的、高质量的网页排列在结果列表的前面。但即使网页的PageRank值再高，如果不能满足用户的检索需求也是毫无意义。因此，Google将Pagerank算法与完善的超文本匹配分析技术结合在一起。一般的搜索引擎仅仅考虑检索词出现的次数，而Google还在此基础上分析关键词的字体、字号以及关键词在网页中出现的精确位置，并且对该网页的临近网页的内容加以分析。Google认为，关键词在网页中出现的位置以及字体等因素都体现了该关键词在该网页中的重要程度，比如说，如果检索词出现在网页A的标题中，而只是出现在网页B的正文中，那么在不考虑其他因素的情况下，说明网页A与用户需求更匹配。Google还引入了锚文本对网页内容进行分析。Google会记录网页中所有的超文本链接的情况，包括该链接的具体对象。Google认为，某超文本链接的文字描述在某种程度上能更加准确地其链接网页的内容。因此，在检索匹配的过程中，Google会考虑某网页邻近网页的超文本链接的情况。6. 搜索引擎前沿研究虽然搜索引擎技术的发展目前比较健全，但仍然存在诸多问题，学界开展的研究也比较多，笔者列举一二供读者参考。6.1搜索结果排序的优化分析在目前所存在的搜索引擎中，没有一个搜索引擎能够覆盖所有的WWW资源，大部分的搜索引擎都只能涉及到整个WWW资源的39%50%左右。集成搜索引擎能将其接收到的用户查询提交给底层的多个搜索引擎&因此集成多个搜索引擎而产生的集成搜索引擎具有比传统引擎覆盖面大、引擎效果更好且具有可扩展性等优点。5集成搜索引擎系统对来自不同搜索擎的结果进行整合，如剔除重复、统一格式、检验链接等，最关键的是重新给出相关度，按新的相关性排列查询结果后提交给用户，经过这样的二次处理，查准率将明显提高。66.2搜索引擎中评分方法的研究目前网络搜索引擎普遍存在对用户的查询请求返回过多的查询结果，而如何从这些查询结果中发现有用的信息是迫切需要解决的问题。此外，由于检索出过多的相关网页，因此多数Web上的用户使用搜索引擎时更关注排序靠前的搜索结果。这些都可能与评分问题有关Cornell大学的Jon M.Kleinberg等人研制了Clever系统，并在该系统中提出了一组算法对媒体环境的链接结构进行研究，并从中自动抽取出超媒体某些类型的信息纽约州立大学Binghamton分校的M. Cutler等人研制了Webor系统7该系统主要研究如何将HTML文件的结构用于改进检索的性能和效果，讨论了自适应Web站点的概念,它通过对访问存取模式的学习来半自动地改进Web站点的组织和表示。Letizia是通过记录用户的浏览行为来挖掘相关与该用户兴趣的页面。我国的韩立新教授也提出了Ranking Method方法。该方法主要是利用协同过滤技术对查询预处理说返回的搜索结果集进行进一步的处理，找到更多和更好的页面，并对其进行更好的排序，以便用户浏览页面。参考文献：1 印 鉴，陈忆群，张 钢 计算机工程，2005年7月第14期2 Arasu A, Cho J, Hector G M, et al. Searching the Web. ACM Transactions on Internet Technology, 2001, 1(1):2433