搜索引擎工作原理演示文稿课件.ppt

1、第九章 搜索引擎工作原理第一节 搜索引擎和信息检索第二节 搜索引擎的概念第三节 搜索引擎的历史第四节 搜索引擎的工作原理第一节 搜索引擎和信息检索n对大多数人来说，在Web上搜索信息是一项日常活动。n目前，计算机最普遍的应用是-、-。(搜索和通信）n许多人试图改进搜索引擎，其实都是在信息检索领域工作。n信息检索一词的含义非常宽泛。信息检索如何定义？n从20世纪50年代，该领域的主要焦点是-、-。（text和text documant，文本和文本形式的文档)n网页、电子邮件、学术论文、图书和新闻报道只是文档类型中的一部分。n所有这些文档都有一定的结构，例如与科技期刊论文的内容相关联的标题、作者、

2、日期和摘要信息等。n当用于数据库记录时，这些结构由属性或域组成。n文档和典型的数据记录（如银行账号记录）最重要的区别是？。n文档中的大部分信息以文本形式存放，文本是没有结构。n账号记录中包含两个典型属性：账号和当前余额。无论在格式上，还是意义上，这两个属性都被非常精确的定义。要比较这些属性的值非常容易。n因此可以直接实现某个算法，识别出满足某个查询条件的记录，例如：“找出账号为321456账户”或者“找出余额大于5万美金的账户”n文本的比较容易？n定义一个词、句子、段落或者整个新闻报道的意义，比定义一个账号要难得多。n对人们比较文本的过程进行理解和建模，并设计计算机算法以便精确地执行这种比较，

3、是信息检索的核心。n信息检索的应用逐步扩展到带有结构的多媒体文档、有意义的文本内容和其他媒体。n垂直搜索、企业搜索、桌面搜索。nVertical search：是网络搜索的特殊形式，搜索被限制在特殊的主题上。nenterprise search：是在散布在企业内部网中的大量计算机文件中查找所需信息。n信息检索不仅仅研究基于用户查询的搜索（有时被称为特殊搜索），还包括过滤、分类和问答。n信息检索的关键问题之一是相关性。相关性检索模型。n之二是评价问题。n之三是注重用户和他们的信息需求。n目前人们从网上获取信息的主要工具是浏览器。n通过浏览器得到信息通常有三种方式：直接向浏览器输入一个关心的网址（

4、URL），浏览器返回所请求的网页，根据该网页的内容及其包含的超链接文字的引导，获得所需的内容。此种方式最有针对性。n登录到某知名网站，根据该网站提供的分类目录和相关链接，逐步寻找自己感兴趣的信息。此种方式类似于读报。n登录到某搜索引擎网站，输入代表自己所关心信息的关键词或者短语，依据所返回的相关信息列表、摘要和超链接引导，寻找需要的信息。此种方式适用于用户需求较明确，但不知信息所在位置，所以搜索引擎给出一些相关内容的网址及其相关内容的列表，供用户选择。nURL（uniform resource locator）用来定义互联网上信息资源的一种协议（或者说描述规范），网页的定位通常是以形如http

5、:/host/path/file.html的URL来描述的，n而FTP资源则以形如ftp:/host/path/file的URL来描述。第二节 搜索引擎概念n搜索引擎指的是一种在Web上应用的软件系统，它以一定的策略在Web上搜集和发现信息，在对信息进行处理和组织后，为用户提供Web信息查询服务。n呈现在使用者面前的是一个网页界面，使其通过浏览器提交一个词语或者短语，然后很快返回一个可能和用户输入内容相关的信息列表。（注意：在系统内部搜索得到，而不是在Web上搜索）列表中的每一条目代表一篇网页，每个条目至少有三个元素：n标题：以某种方式得到的网页标题。最简单的方式就是从网页的标签中提取的内容。

6、nURL：该网页对应的访问网址。有经验的用户往往通过这个元素对网页内容的权威性进行判断。（注意：链接的是网页的原始出处）n摘要：以某种方式得到的网页内容的摘要。最简单的一种方式就是将网页内容的头若干字节截取下来作为摘要。n所以，从理论上搜索引擎并不保证用户在返回结果列表上看到的标题和摘要内容与其点击URL所看到的内容一致，甚至不保证那个网页存在。（这是搜索引擎和传统信息检索的一个重要区别）。n为了弥补这种差别，现代搜索引擎都保存网页搜集过程中得到的网页全文，并在返回结果列表中提供“网页快照”或者“历史网页”链接，保证用户能看到和摘要信息一致的内容。第三节 搜索引擎的发展历史n在Web出现以前，

7、互联网上就已经存在许多旨在让人们共享的信息资源。此时的信息资源主要存在于各种可以匿名访问的FTP站点，内容以学术技术报告、研究性软件居多。它们以计算机文件的形式存在，文字材料的编码通常是PostScript或者纯文本（当时还没有HTML）n1990年，加拿大University of McGill计算机学院的师生开发软件-Archie，被认为现代搜索引擎的鼻祖。nArchie通过定期搜集并分析FTP系统中存在的文件名信息，提供查找分布在各个FTP主机中文件的服务。（包括提供资源的文件名、文件长度、存放该文件的计算机名及目录名等。）nArchie实际上是一个大型的数据库，在加上与这个数据库相关联

8、的一套检索方法。其工作方式与搜索引擎的基本相同：自动搜集分布在广域网上的信息，建立索引，提供检索服务。n以Web网页为对象的搜索引擎和以FTP文件为对象的检索系统一个基本的不同点在于搜集信息的过程。前者是利用HTML文档之间的链接关系，在Web上一个网页一个网页地“爬取”（crawl），将那些网页“抓”（fetch）到系统来进行分析；后者则根据已有的关于FTP站点地址的知识，对那些站点进行访问，获取其文件目录信息，并不真正将那些文件下载到系统中来。所以如何在Web上抓取网页是搜索引擎要解决的一个基本问题。n1993年，Matthew Gray开发了World Wide Web Wanderer

9、，世界上第一个利用HTML网页之间的链接关系来监测Web发展规模的机器人（robot）程序。刚开始是用来统计互联网上的服务器数量，后发展为能够通过它检索网站域名。由于其爬行的工作方式，也被称为“蜘蛛”。n在文献中crawler,spider,robot,都指的是Web上依据网页之间的超链关系一个个抓取网页的程序，通常也被称为搜集。在搜索引擎系统中，也称为网页搜集子系统。n现代搜索引擎的思路来源于Wanderer，经过不断的改进，1994年7月，Michael Mauldin将John leavitt的蜘蛛程序接入到其索引程序中，创建了为人熟知的Lycos,成为第一个现代意义的搜索引擎。n随着信

10、息技术的发展和信息资源的猛增以及搜索引擎的地位的重要性增强，不断有新的、强的搜索引擎系统推出。由于采用独特的PageRank技术，Google后来居上，成为目前最受欢迎的搜索引擎。n此外，还出现了基于目录的信息服务网站，如Yahoo，被成为目录搜索引擎，以区别于前面的自动搜索引擎，或者被称为网站搜索引擎，以区别于前面的网页搜索引擎。分别具有搜索结果准确或全面的特点。n随着网上资源的增加，单纯依靠人工整理网站目录取得较高精度查询结果的优势逐步退化。目前有两个发展方向：一是利用文本自动分类技术，在搜索引擎上对每篇网页的自动分类，如Google的“网页分类”选项；二是将自动网页爬取和一定的人工分类目

11、录结合，这样既有高信息覆盖率，也有高查准率。n随着信息数量、信息种类的变化以及网民成分的变化，出现了多种的主题搜索引擎、个性化搜索引擎、问答式搜索引擎等的出现，以满足不同的信息需求。n通用搜索引擎的运行出现了分工：专业的搜索引擎技术和搜索数据库服务提供商（如美国的Inktomi，不是直接面向用户的搜索引擎，而是为Hotbot,Looksmart等搜索引擎提供全文网页搜集服务）n搜索引擎在网络信息服务中具有不可替代的地位。虽然其基本工作原理已经相当稳定，但在其质量、性能和服务方式等方面的发展空间很大。搜索引擎设计与核心信息检索问题搜索引擎是信息检索技术在大规模文本集合上的实际应用。“搜索引擎”一

12、词原来是指为文本搜索服务的特殊的硬件。n从20世纪80年代中期开始，在描述用来比较查询和文档并生成文档排序结果的软件系统时，逐渐使用“搜索引擎”一词，而不是“信息检索系统”。信息检索核心问题n相关性 -有效排序n评价 -测试和测量n信息需求 -用户交互n搜索引擎设计中的重要问题包括了信息检索中的各种问题-、-、-。n（参见：搜索引擎：信息检索实践/（美）克罗夫特（Croft,W.B）等著；刘挺等译/机械工业出版社 2010，2：1-7）n在搜索引擎的部署过程中遇到的大规模数据的运行环境，还给搜索引擎带来了许多其他许多难题。搜索引擎设计中的核心问题n效能 有效的搜索和索引n合并新数据 -覆盖率和

13、新鲜度n可扩充性 随着数据量和用户量而增长n自适应 为适应特定应用而作调节n特殊问题 如：垃圾信息1.搜索引擎的效能n评价指标包括response time,query throughput,indexing speed。n响应时间：n查询吞吐量：n索引速度：2.将新数据合并到索引中的速度nCoverage:nRecency或freshness：搜索应用往往要处理动态持续变化的信息。3.可扩充性nScalability:面向一个特定应用的设计应该考虑到数据量和用户量的增长。4.adaptablen搜索引擎的许多功能，比如排序算法、界面或搜索策略，能够为满足新的应用需要而调整和适应。5.spam

14、n为某种商业利益而制作的文档中误导的、不合适的或不相关的信息。n尤其是搜索引擎必须处理一些文档中的垃圾词，这些词会导致搜索引擎响应一些热门查询时被检索出来。n信息检索研究包括了文本和语言的数学模型的建立、带有测试集合与用户的大规模环境的建立以及学术论文的写作。nSearch engineern搜索工程已经成为信息产业中的重要职业。第四节 搜索引擎工作原理n网页搜集n预处理n查询服务一.搜索引擎要达到的基本要求n能够接受用户通过浏览器提交的查询词或者短语；在一个可以接受的时间可以接受的时间内内返回一个和该用户查询匹匹配配的网页信息列列表。表。1.响应时间n可以接受的时间：衡量搜索引擎可用性的一个

15、基本指标，也是与传统检索系统的一个重要区别，通常在“秒”量级。n系统应该在额定吞吐率（throughput或称吞吐量，是指在单位时间里系统完成的总任务量。n对于搜索引擎来说，就是指系统在单位时间里“秒”可以服务的最大用户查询数量）的情况下保持秒级响应时间。这样的响应时间不仅能满足-用户的查询，而且要在系统设计负荷的情况下满足-用户。2.匹配n指的是网页中以某种形式包含有查询词的内容，其中最简单、最常见的形式是查询词在其中直接出现。n当然，如果一个搜索引擎就是以百分之百满足这种简单的包含关系为目标，即使实现了也并不就达到了最好的效果。3.列表n在大多数情况下，检索结果列表相当长。不仅因为网上信息

16、量大，也由于搜索引擎的查询方式简单。这就涉及到“序”（rank）的问题。二、工作原理n高质量的现代搜索引擎一般采用三段式的工作流程：搜集、预处理、服务。（一）网页搜集n搜索引擎这个软件系统操作的数据不仅包括内容不可预测的用户查询，而且还包括在数量上动态变化的海量网页，并且需要抓取。n对于搜索引擎来说，要抓取因特网上所有的网页是不现实。n一是因为有许多网页无法从其他网页的链接中找到；n二是因为存储和处理技术方面的问题。因此搜索引擎的网络蜘蛛只抓取部分重要和相关的网页。n网络信息采集的方式一般分人工采集和自动采集。(参见：网络信息检索技术及搜索引擎系统开发/高凯等/科学出版社 2010，P21)n

17、常规采集有定向和定题之分。n自动采集的优点是信息处理量大、数据更新及时、一般不需人工干预。n自动地发现并下载网页称为爬取（crawling）n下载网页的程序称为爬虫（web crawler）n互联网上的每一个网页都有自己唯一的统一资源定位器（uniform resource locator）或URLnhttp:/www.cs.umass.edu/csinfo/people.htmln用于描述网页URL由三部分组成：协议方案、主机名、资源名。n网页存储在网页服务器上，使用超文本传输协议来和客户端软件交换信息。n网络爬虫有两个任务：下载网页和发现URL。n网络爬虫的工作从一个种子（seed）集合开

18、始，种子集合是作为参数传递给网络爬虫的一个URL的集合。这些种子被添加到URL请求队列中取出URL地址下载解析链接标签n这个过程重复进行，直到网络爬虫用尽存储页面的磁盘空间或者请求队列为空。1.搜集过程n网页搜集的过程是从URL库（初始时包含用户指定的起始种子URL集合，可以是一个或多个）获得输入，解析URL中标明的Web服务器地址、建立连接、发送请求和接收数据，将获得的网页数据存储在原始网页库，并从中提取出链接信息放入网页结构库，同时将待抓取的URL放入URL库，保证整个过程的递归进行，直到URL库为空。下图显示Web信息的搜集过程：抓取提取URL库原始网页网页结构2.系统网页数据库维护的基

19、本策略 A A、定期搜集，批量搜集。优缺点？系统实现简单，但开销大、额外的宽带消耗、时新性不高。B B、增量搜集：搜集新出现的网页；搜集那些在上次搜集后有过改变的网页；发现自上次搜集后已经不再存在的网页，并从库中删除。优缺点？时新性高，但系统实现比较复杂。除新闻网站外，许多网页的内容不是经常变化，研究认为50%的网页的平均生命周期大约为50天，中国每天约30-50万变化的网页，那么一台PC机，在一般的网络条件下，半天就可以搜集完，这样可以每天启动搜集过程，时新性得到了保证。C C、优化的网页搜集策略：在系统能力一定的情况下，若有两类网页，其更新周期差别大，则系统应该将注意力放在更新慢的网页上，

20、以使系统整体的时新性达到比较高的水平。3.搜集的方式n最常见的是一种爬取：将Web上的网页集合看成是一个有向图，搜集过程从给定起始URL集合S（或者说种子）开始，沿着网页中的链接，按照先深、先宽或者别的策略遍历，不停地从S中移除URL，下载相应的网页，解析出网页中的超链接URL，看是否已经被访问过，将未访问的那些URL加入集合S。整个过程犹如蜘蛛（spider）在蜘蛛网（Web）中爬行（crawl）。n多个蜘蛛同时在爬。n任何搜索引擎不可能将Web上的网页搜集完全（通常是在比如磁盘满或者搜集时间已经太长了），因此必须使搜索引擎搜集到比较重要的网页。n按照何种方式可以得到重要网页？n研究表明，按

21、照先宽搜集方式得到的网页集合要比先深搜集得到的网页重要。n为什么？4.如何避免网页的重复搜集n保证每个网页不被重复抓取。原因是一方面搜集程序没有清楚记录已经访问过的URL，二是由于域名与IP对应关系造成的。n解决的办法一是使用两个表：unvisited-table和visited-table，记录未访问、已访问URL和网页内容摘要信息。n二是找出那些指向同一物理位置URL的多个域名和IP，这是一个逐渐积累的过程。n其实域名和IP的对应关系存在四种情况：一对一、一对多、多对一、多对多，前者不会造成重复搜集，后三者会造成重复搜集。n所以首先要积累一定数量的域名和IP，然后将这些域名和IP对应的首页

22、和首页链接出的最开始的几个页面抓取回来，如果比较结果一样，则归为一组，以后搜集时可以只选择其中一个进行搜集。选择时应该优先选择有域名的，有的网站对于直接用IP访问是被禁止的。n例如：对应的IP地址为：202.108.42.73，202.108.42.91，202.108.42.64，202.108.42.63，202.108.42.71，202.108.42.72，但是直接用http:/202.108.42.73访问是被拒绝的。5.如何首先搜集重要的网页nWeb上的信息具有异质性和动态性，由于受时间和储存空间的限制，即使是最大的搜索引擎也不可能将全球所有的网页全部搜集过来，一个好的搜索策略是优

23、先搜集重要的网页，以便能够在最短的时间内把最重要的网页抓取过来，在此要求下，一方面要采用分布并行的体系结构来协调工作，一方面要优先搜集重要网页。n体现网页重要度的特征有哪些？体现网页重要度的特征n网页的入度（？）大，表明被其它网页引用的次数多n某网页的父网页入度（？）大n网页的镜像度高，说明网页内容比较热门，从而显得重要n网页的目录深度（？）小，易于用户浏览到n上述特征中哪些很容易被确定？n网页入度（page indegree)，针对一个网页，整个网络中指向该网页的超链接数目。n网页出度（page outdegree)，针对一个网页，该网页指向其他网页的超链接数目。nURL目录深度：网页对应的

24、url中除去域名部分的目录层次，即url为http=schema:/host/localpath中的localpath部分。如http:/的目录深度为0，http:/ Web page，不需要提交查询信息即可获得的页面）n底层包含的主要是动态网页（dynamic Web page，需要通过提交查询信息获得含有内容的网页）n目前搜索引擎主要集中在表层工作。n在表层中重要网页的分布或者更接近于海面，或者更接近于底层。对于网页的搜集工作，就像一条捕鱼的船行驶在海面上，目的是撒网捕捉尽可能多而且重要的网页。n实际搜集网页经验表明，网站的首页是漂浮在海面上的，网站数目远小于网页数，并且重要的网页也必然是

25、从这些网站首页链接过去的，因此搜集工作应当优先获取尽可能多的网站首页。因此宽度优先搜集是尽快获得重要网页最好的办法。n采取宽度优先搜集最直接有效的方法就是根据网页的URL的目录深度确定优先级，这样既客观有容易获取所需。n一般搜索引擎就根据网页的URL的目录深度和链接关系设定权值，以决定网页重要度，并优先搜集权值大的网页，实现类似于宽度优先搜集的启发式搜集策略。n相对来说代价比较低的方法是面向主题（focused）或话题（topical）的信息采集。n网络爬虫很难找到的站点统称为深层网络（deep web），也被称为隐藏网络（hidden web）nPrivate sitenForm resul

26、tnScripted pagen私人站点：倾向于隐私内容，没有任何指向它的链接，或者在使用该站点之前，需要使用有效的账户进行注册。n表单结果：通常需要在表单中填写数据才可以进入。如销售机票的站点，通常在页面的入口处会询问旅行的信息。大多数爬虫不可能越过这个表单获取航班时刻表的信息。（参见：搜索引擎：信息检索实践P25）n脚本页面：是使用JavaScript、Flash或其他客户端语言的页面。如果一个链接并不是以HTML语言给出的，而是通过在浏览器中运行JavaScript生成的，爬虫需要在该网页上执行JavaScript才能找到这个链接。技术上可行，但会影响速度，增加系统的复杂性。（二）预处理

27、按照“程序=算法+数据结构”的观点来考察程序，一个合适的数据结构是查询子系统的核心。现行最有效的数据结构是“倒排文件”（inverted file）.（组织和索引文件、以便于检索的一种方法。在该方法中，一个关键词的集合是基础，该集合中每一个关键词对应一串记录项，其中每一项包含一个文档编号、该关键字在该文档中出现的情况等信息）n倒排优点在于可支持快速的多途径检索，组配检索尤为方便，多数联机检索都使用倒排档进行检索或辅助检索。其缺点是建立倒排档需要时间和空间，维护较困难。n倒排文件是用文档中所含关键词作为索引、文档作为索引目标的一种结构。n预处理即网页集合形成倒排文件过程的几个主要问题：关键词的提

28、取、“镜像网页”的消除、链接分析和网页重要程度的计算。1.关键词的提取n一篇网页的源文件（通过浏览器的“查看源文件”功能）的情况纷繁复杂。除了可以看见的文字内容外，还有大量的HTML标记。n根据统计，网页文档源文件的大小（字节量）通常大约是其中内容大小的4倍。此外，由于HTML文档产生来源的多样性，许多网页在内容上比较随意，不仅文字不规范、完整，而且还可能包括许多和主要内容无关的信息，如广告、导航条、版权说明等。n为了支持后面的查询服务，需要从网页源文件中提取出能够代表它的内容的一些特征。n从认识和实践来看，所含的关键词是这种特征的最好代表。n因此（文本）预处理的第一步就是提取网页源文件内容部

29、分所含的关键词。n首先要进行切词切词（word segmentation）或分词。分词。n英文单词天然地被空格隔开，很容易切分，而中文的词相对困难些,中文词与词之间没有界定符。n汉语中分词还存在哪些困难？n此外汉语中存在大量的歧义现象，对几个字分词可能有多种结果。n简单的分词可能会歪曲查询的真正含义。比如“中国人”，若不能正确分词，按“中国”、“人”、“中国人”等关键词去检索，这样检索结果的质量就可想而知了。n在语义表达方面，也不是每个词的表达能力相等。n因此预处理除了分词以外，还包括、等操作。停用词的删除n从效果（effectiveness）和效率（efficiency）考虑，不应该让所有的

30、词都出现在网页的表示中，要去掉诸如“的“在等没有内容指示意义的词，称为“停用词”（stop word）,这样对一篇网页来说，有效的词语数量大约在200左右。n如果一个词在某个文本中多次出现，那么这个词与文本的主题相关？n如果一个词在多个文本中多次出现，那么这个词与这些文本的主题相关？n一般情况下，在文档库的文本中出现频率超过80%的词对检索过程起不到作用n这些词需要过滤，以提高检索效率。n建立停用词表。n删除停用词可以节省索引空间40%。缺点在于？词干提取n为了解决英文检索中存在的问题而采取的操作。n词干提取的优点？n提高召回率，索引空间缩小。n词干提取技术有：词缀删除、表格查询、后续变形、N

31、-连字。（参见：智能检索技术/陆建江等/科学出版社 2009，p4)n词缀删除n表格查询技术n后续变形技术n N-连字分词算法n自1983年第一个实用分词系统CDWS诞生至今，已经出现了很多有效的分词方法，如改进的最大匹配法、综合了最大匹配和最少切分的N-最短路径法、错误驱动机制、基于首字Hash的算法、基于PATRICIA树的方法、临近匹配算法、基于大规模语料库的统计机器学习方法、n所用的统计模型有相邻字的互信息模型、最大期望模型等，这些自动分词方法基本可归到两大类：基于字符串匹配的分词方法和基于统计的分词方法。中文的自动分词方法n基于字符串匹配的分词法：又称为机械分词方法，它是按照一定的策

32、略将待分析的汉字串与一个充分大的词典中的词条进行匹配，若在词典中找到某个字符串，则匹配成功（识别出一个词）。n按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按照不同长度优先匹配的情况，可以分为最大或最长匹配和最小或最短匹配；按照是否与词性标注过程相结合，又分为单纯分词方法和分词与标注相结合的一体化方法。n常用的几种机械分词方法有：正向最大匹配、逆向最大匹配和最少切分（使每一句中切出的词数最小。n还可以将以上三种方法相互组合。如可以将正向最大匹配方法和逆向最大匹配方法相互结合起来构成双向匹配法。由于汉字单字成词的特点，正向最小匹配和逆向最小匹配一般很少使用。一般来说，逆向匹配的切

33、分精度高于正向匹配，遇到的歧义现象也较少。n统计结果表明，单纯使用正向最大匹配的错误率为1/169，单纯使用逆向最大匹配的错误率为1/245。（汉语的中心语靠后的特点）n基于统计的分词方法。从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好地反映成词的可信度。n一种常用的方法是对语料中的相邻共现的各个字的组合的频度进行统计，计算它们的互现信息。n互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一阀值时，便可认为此字组可能构成了一个词。这种方法只需对语料库中的字组频度进行统计，不需要进行切分字典，因此

34、又称为无词典分词法或统计取词方法。n在实际应用中，一般只考虑？个汉子组成词的情况，因为大于？的字符组成词语的可能性很小。n基于统计的分词方法不需要切分词典，n但这种方法也有一定的局限性，会经常出现抽出一些共现频度高、但并不是词的常用字组。如“我的”等，并且对常用词的识别精度差，时空开销大。n实际应用的统计分词系统会经常使用一部基本的分词词典进行串匹配分词，同时使用统计方法识别一些新的词。n实际应用的分词系统都要使用一部基本的分词词典（常用词词典）进行串匹配分词，同时使用统计方法识别一些新的词，即将串匹配统计和串匹配结合。既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词结合上下文识别生

35、词、自动消除歧义的优点。2.重复或转载网页的消除n或者称为“镜像网页”或“转载网页”的消除。n镜像网页（mirror web page）：网页的内容完全相同，未加任何修改。n转载网页（near-replicas）:主题内容基本相同但可能有一些额外的编辑信息等，转载网页也称为“近似镜像网页”n与生俱来的数字化和网络化给网页的复制和转载以及修改再发表带来了便利，因此web上的信息存在大量重复现象。据统计网页的重复率平均约为4（通过一个URL在网上看到一篇网页时，平均还有另外3个不同URL也给出相同或者基本相似的内容）。n对于网民、搜索引擎来说意味着什么？n对于网民来说具有正面意义，即有了更多的访问

36、机会。但对于搜索引擎来说则主要是负面的，不仅在搜集网页时要消耗机器时间和网络宽带资源，而且如果在查询结果中出现，无意义地消耗了计算机显示屏资源，也会导致用户的不满。因此消除内容重复或主题重复的网页是预处理的第二个重要任务。3.链接分析n大量的HTML标记既给网页的预处理带来了麻烦，也带来了新的机遇。n从信息检索角度讲，如果系统面对的仅仅是内容上的文字，我们能依据“共有词汇假设”（shared bag of words，信息检索技术的一种最基本假设，即认为文档的含义可以由它所包含的关键词的集合来表达），即内容所包含的关键词集合，最多加上词频（term frequency,或tf,TF）和词在文档

37、集合中出现的文档频率（document frequency,或df,DF）的统计量。nTF和DF的频率信息能在一定程度上指示词语在一篇文档中的相对重要性或者和某些内容的相关性。nHTML文档中所含的指向其他文档的链接信息是近几年来特别被关注的对象。不仅给出了网页之间的关系，而且还可以据此判断网页的内容有重要的作用。4.网页重要程度的计算n参照科技文献重要性的评估方式，其核心是“被引用多的就是重要的”，形成了排序结果的重要参数。n网页和文献不同，一些网页主要大量对外链接，反之一些网页则被大量的其他网页链接，这种对偶关系，可以建立一种重要性指标。n所以搜索引擎目前实际上追求的是统计意义上的满意（多

38、数情况下查询结果更符合用户的要求，而不是所有情况下都如此），因为面对的是多种多样的用户，加之查询的自然语言风格，对同样的查询需求返回的相同的结果列表不可能使所有的用户满意。预处理的系统结构索引索引网页库分析网页&建立倒排索引倒排表索引词表n网页的预处理步骤：为原始网页建立索引，实现索引数据库，有了索引就可以为搜索引擎提供网页快照功能；n针对索引网页库进行网页切分，将每一篇网页转化为一组词的集合；n将网页到索引词的映射转化为索引词到网页的映射，形成倒排文件（包括倒排表和索引词表），同时将网页中包含的不重复的索引词汇聚成索引词表。n基于索引的检索技术非常适应于大规模、稳定的或周期性变化的文本文档库

39、，如今绝大部分搜索引擎采用的都是基于索引的检索技术n网页的预处理处于搜索引擎第三阶段的中间，所产生的数据都是中间数据，如果不提供必要的应用程序接口，难以作为数据产品提供给其他程序使用。（三）查询服务n如上所述，从一个原始网页集合S开始，预处理过程得到的是对S的一个子集的元素的某种内容表示，这种表示构成了查询服务的直接基础。n对每个元素来说，这种表示至少包含：原始网页文档、URL和标题、编号、所含重要关键词的集合（以及其在文档中出现的位置信息）和其他一些指标（如重要程度、分类代码等）n系统关键词总体的集合和文档的编号一起构成了一个倒排文档结构，使得一旦得到一个关键词的输入，系统能迅速给出相关文档

40、编号的集合输出。n但是呈现在用户的目前是一个列表，而不是集合，所以如何从集合生成列表是服务子系统的主要工作。n服务子系统是服务过程中涉及的相关软件程序，其工作原理主要有以下三方面。1.查询方式和匹配n用一个词或短语来直接表达信息需求，希望网页中含有该词或该短语中的词，是主流搜索引擎查询方式。n通过分词或切词将用户的查询原始短语形成一个用于参加匹配的查询词表，对应倒排文件中的一个倒排表（文档编号的集合），两者的交集即为对应查询的结果文档集合，从而实现查询和文档的匹配。2.结果排序n在搜索引擎的早期采用传统信息检索领域成熟的基于词汇出现频率的方法。由于网页编写的自发性、随意性较强，仅仅针对词的出现

41、来决定文档的顺序，在Web信息检索上表现明显的缺点，需要其它技术补充，如Pagerank技术n即：通过在预处理阶段为每篇网页形成一个独立于查询词（和网页内容无关）的重要性指标，将它和查询过程中形成的相关性指标结合形成一个最终的排序，是目前搜索引擎查询结果排序的主要方法。3.文档摘要n搜索引擎给出的检索结果是一个有序的结果列表，每一个条目有三个基本元素：标题、网址和摘要。其中摘要需要从网页正文中生成。n从一篇文章中生成一个恰当的摘要是自然语言理解领域的一个重要课题，已经取得了不少成果。但是相关技术应用到搜索引擎上有两个基本困难：一是网页的写作不规范，文字比较随意，因此从语言理解的角度难以做好；二

42、是复杂的语言理解算法耗时太多，不适应搜索引擎高效处理海量网页信息的需求。n根据统计，在高档微机上每秒钟只能完成10篇左右网页的分词工作（基于文本理解的基础）。n搜索引擎在生成摘要时要简便得多，基本上可以归纳为两种方式：n一是静态方式，即独立于查询，按照某种规则，事先在预处理阶段从网页内容提取出一些文字，如摘取网页正文的开头512个字符（对应256个汉字），或者将每一个段落的第一个句子拼起来等等。n这种方式的优点？n动态方式的优点是实现简单，但是摘要和查询有时无关。其实当用户输入某个查询词，他一般是希望摘要中能够突出显示和查询直接对应的文字，希望摘要中出现与其关心相关的句子，因此有第二种方式，即

43、动态摘要。n二是动态摘要。即在响应用户查询的时候，根据查询词在文档中出现的位置，提取出查询词周围相关文字并返回给用户，这是目前大多数搜索引擎采取的方式。缺点是？n由于一篇文档会含有不同的查询词，因此动态摘要技术可能把同一个文档形成不同的摘要文字）为了保证查询的效率，需要在预处理阶段分词的时候记住每个关键词在文档中出现的位置。信息查询的系统结构查询代理Web搜索记录日志n经过预处理，传递到服务阶段的数据包括索引网页库和倒排文件，倒排文件中包括倒排表和索引词表。n查询代理接受用户输入的查询词语，切分后，从索引词表和倒排文件中检索获得包含查询短语的文档并返回用户。n因为内存与外存（磁盘）的响应时间差

44、距很大，在实际使用的搜索引擎中，为了提高响应时间，索引词表是驻留在内存中的，用户近期查询过的网页结果信息也是缓存在内存中的。如果内存足够大，所有倒排表项也可以驻留在内存中。只有这样，才能保证在大数据量和大访问量（如每秒1000个查询）的情况下，搜索引擎在秒级内得到响应。（四）搜索引擎总的体系结构n大规模的搜索引擎通常每天搜集上百万网页，而且是持续进行，并且稳定地提供网页信息，其核心是要综合解决效率、质量和“礼貌”问题，即“控制器”的作用。n下图为搜索引擎的体系结构。控制器索引器索引数据库搜集器日志分析器用户行为日志数据库用户WWW原始数据库检索器用户接口1.效率n所谓效率，即利用尽量少的资源（

45、计算机设备、网络宽带、时间）来完成预定的网页搜集量。n让网络通信时间和存放网页的磁盘访问时间重叠起来。由于从网上抓取一篇网页通常需要秒量级的等待网络通信时间，同时启动多个抓取进程线，或者利用操作系统提供的异步通信机制，让多个网络通信时间重叠起来。同时启动抓取进程的数量取决于硬件条件和搜集软件的设计。n并不是设备越多越好，一般不超出10台计算机（宽带瓶颈问题）n网络的服务器方，来不及提供所需的网页。2.礼貌n将对搜集活动的关注过分集中在几个网站上、或者一下段时间里从一个网站抓取太多的网页还可能引起其它的严重后果，即所谓的“礼貌”问题。n一般网站希望其网页被搜索引擎抓取，从而有可能得到更多的访问流

46、量，但是另一方面网站也不希望由于搜索引擎的密集抓取活动阻碍普通用户通过浏览器的访问，使那些用户得到这个网站访问困难的印象。n因此适当地规划网页的抓取，限制单位时间内对一个网站抓取网页的数量（例如每天不超过2万个，或者至少每隔30秒才对一个网站发出下一个网页请求等等），是大规模搜索引擎必须认真对待的问题。3.质量问题n在有限的时间，搜集有限的网页，希望是比较重要的网页。一般来说，靠近主页的网页通常PageRank值较高。所以，首先得到尽量多的主页，然后从主页开始的先宽搜索是较好的策略。（五）搜索引擎的架构n软件架构n基本的构件n组件及其功能软件架构n软件构件通常包括软件组件、组件提供的接口以及各组件之间的关系。基本的构建n搜索引擎的组件主要提供两种功能，即索引处理和查询处理。n索引处理建立可查找的数据结构，查询处理使用这些数据结构和用户查询生成一个排好序的文档列表。n索引处理包括文本采集、文本转换和索引创建。n查询处理包括用户交互、排序和评价。组件及功能n文本采集（爬虫、信息源、转换、文档数据库）n文本转换（解析器、停用词去除、词干提取、超链接的抽取与分析、信息抽取、分类器）n索引的创建（文档统计、加权、倒排、索引分派）n用户交互（查询输入、查询转换、结果输出）n排序（打分机制、性能优化、分布式）n评价（日志、排序分析、性能分析）