在浩如烟海的Internet上，特别是其上的Web（World Wide Web万维网）上，不会搜索，就不会上网。网虫朋友们，你了解搜索引擎吗？它们是怎么工作的？你都使用哪些搜索引擎？今天我就和大家聊聊搜索引擎的话题。 
一、搜索引擎的分类 
　　获得网站网页资料，能够建立数据库并提供查询的系统，我们都可以把它叫做搜索引擎。按照工作原理的不同，可以把它们分为两个基本类别：全文搜索引擎（FullText Search Engine）和分类目录Directory）。

　　全文搜索引擎的数据库是依靠一个叫“网络机器人（Spider）”或叫“网络蜘蛛（crawlers）”的软件，通过网络上的各种链接自动获取大量网页信息内容，并按以定的规则分析整理形成的。Google、百度都是比较典型的全文搜索引擎系统。

　　分类目录则是通过人工的方式收集整理网站资料形成数据库的，比如雅虎中国以及国内的搜狐、新浪、网易分类目录。另外，在网上的一些导航站点，也可以归属为原始的分类目录，比如“网址之家”（http://www.hao123.com/）。

　　全文搜索引擎和分类目录在使用上各有长短。全文搜索引擎因为依靠软件进行，所以数据库的容量非常庞大，但是，它的查询结果往往不够准确；分类目录依靠人工收集和整理网站，能够提供更为准确的查询结果，但收集的内容却非常有限。为了取长补短，现在的很多搜索引擎，都同时提供这两类查询，一般对全文搜索引擎的查询称为搜索“所有网站”或“全部网站”，比如Google的全文搜索（http://www.google.com/intl/zh-CN/）；把对分类目录的查询称为搜索“分类目录”或搜索“分类网站”，比如新浪搜索（http://dir.sina.com.cn/）和雅虎中国搜索（http://cn.search.yahoo.com/dirsrch/）。

　　在网上，对这两类搜索引擎进行整合，还产生了其它的搜索服务，在这里，我们权且也把它们称作搜索引擎，主要有这两类：

　　⒈元搜索引擎(META Search Engine)。
　　这类搜索引擎一般都没有自己网络机器人及数据库，它们的搜索结果是通过调用、控制和优化其它多个独立搜索引擎的搜索结果并以统一的格式在同一界面集中显示。元搜索引擎虽没有“网络机器人”或“网络蜘蛛”，也无独立的索引数据库，但在检索请求提交、检索接口代理和检索结果显示等方面，均有自己研发的特色元搜索技术。比如“metaFisher元搜索引擎”
（http://www.hsfz.net/fish/），它就调用和整合了Google、Yahoo、AlltheWeb、百度和OpenFind等多家搜索引擎的数据。

　　⒉集成搜索引擎（All－in－One Search Page）。
　　集成搜索引擎是通过网络技术，在一个网页上链接很多个独立搜索引擎，查询时，点选或指定搜索引擎，一次输入，多个搜索引擎同时查询，搜索结果由各搜索引擎分别以不同页面显示，比如“网际瑞士军刀”（http://free.okey.net/%7Efree/search1.htm）。

二、搜索引擎的工作原理

　　全文搜索引擎的“网络机器人”或“网络蜘蛛”是一种网络上的软件，它遍历Web空间，能够扫描一定IP地址范围内的网站，并沿着网络上的链接从一个网页到另一个网页，从一个网站到另一个网站采集网页资料。它为保证采集的资料最新，还会回访已抓取过的网页。网络机器人或网络蜘蛛采集的网页，还要有其它程序进行分析，根据一定的相关度算法进行大量的计算建立网页索引，才能添加到索引数据库中。我们平时看到的全文搜索引擎，实际上只是一个搜索引擎系统的检索界面，当你输入关键词进行查询时，搜索引擎会从庞大的数据库中找到符合该关键词的所有相关网页的索引，并按一定的排名规则呈现给我们。不同的搜索引擎，网页索引数据库不同，排名规则也不尽相同，所以，当我们以同一关键词用不同的搜索引擎查询时，搜索结果也就不尽相同。

　　和全文搜索引擎一样，分类目录的整个工作过程也同样分为收集信息、分析信息和查询信息三部分，只不过分类目录的收集、分析信息两部分主要依靠人工完成。分类目录一般都有专门的编辑人员，负责收集网站的信息。随着收录站点的增多，现在一般都是由站点管理者递交自己的网站信息给分类目录，然后由分类目录的编辑人员审核递交的网站，以决定是否收录该站点。如果该站点审核通过，分类目录的编辑人员还需要分析该站点的内容，并将该站点放在相应的类别和目录中。所有这些收录的站点同样被存放在一个“索引数据库”中。用户在查询信息时，可以选择按照关键词搜索，也可按分类目录逐层查找。如以关键词搜索，返回的结果跟全文搜索引擎一样，也是根据信息关联程度排列网站。需要注意的是，分类目录的关键词查询只能在网站的名称、网址、简介等内容中进行，它的查询结果也只是被收录网站首页的URL地址，而不是具体的页面。分类目录就像一个电话号码薄一样，按照各个网站的性质，把其网址分门别类排在一起，大类下面套着小类，一直到各个网站的详细地址，一般还会提供各个网站的内容简介，用户不使用关键词也可进行查询，只要找到相关目录，就完全可以找到相关的网站（注意：是相关的网站，而不是这个网站上某个网页的内容，某一目录中网站的排名一般是按照标题字母的先后顺序或者收录的时间顺序决定的）。

三、搜索引擎的发展趋势。

　　一个好的搜索引擎，不仅数据库容量要大，更新频率、检索速度要快，支持对多语言的搜索，而且随着数据库容量的不断膨胀，还要能从庞大的资料库中精确地找到正确的资料。

　　⒈提高搜索引擎对用户检索提问的


解。
　　为了提高搜索引擎对用户检索提问的理解，就必须有一个好的检索提问语言。为了克服关键词检索和目录查询的缺点，现在已经出现了自然语言智能答询。用户可以输入简单的疑问句，比如“如何能杀死计算机中的病毒”，搜索引擎在对提问进行结构和内容的分析之后，或直接给出提问的答案，或引导用户从几个可选择的问题中进行再选择。自然语言的优势在于，一是使网络交流更加人性化，二是使查询变得更加方便、直接、有效。就以上面的例子来讲，如果用关键词查询，多半人会用“病毒”这个词来检索，结果中必然会包括各类病毒的介绍，病毒是怎样产生的等等许多无用信息，而用“如何能杀死计算机中的病毒”检索，搜索引擎会将怎样杀死病毒的信息提供给用户，提高了检索效率。

　　⒉垂直主题搜索引擎有着极大的发展空间。
　　网上的信息浩如烟海，网络资源以惊人的速度增长，一个搜索引擎很难收集全所有主题的网络信息，即使信息主题收集得比较全面，由于主题范围太宽，很难将各主题都做得精确而又专业，使得检索结果垃圾太多。这样以来，垂直主题的搜索引擎以其高度的目标化和专业化在各类搜索引擎中占据了一席之地。目前，一些主要的搜索引擎，都提供了新闻、Mp3、图片、Flash等的搜索，加强了检索的针对性。

　　⒊元搜索引擎，能够提供全面且较为准确的查询结果。
　　现在的许多搜索引擎，其收集信息的范围、索引方法、排名规则等都各不相同，每个搜索引擎平均只能涉及到整个Web资源的30－50%，这样导致同一个搜索请求在不同搜索引擎中获得的查询结果的重复率不足34%，而每一个搜索引擎的查准率不到45%。元搜索引擎(META Search Engine)是将用户提交的检索请求发送到多个独立的搜索引擎上去搜索，并将检索结果集中统一处理，以统一的格式提供给用户，因此有搜索引擎之上的搜索引擎之称。它的主要精力放在提高搜索速度、智能化处理搜索结果、个性化搜索功能的设置和用户检索界面的友好性上，查全率和查准率都比较高。

四、主要的搜索引擎介绍

　　这里介绍的是在国内外影响比较大的主要的一些搜索引擎和分类目录站点，由于现在的站点一般都同时提供全文搜索和分类目录两种服务，所以我们按照其自有的技术进行分类和介绍。

　　㈠主要的全文搜索引擎

　　⒈Google（http://www.google.com/）。Google成立于1997年，几年间迅速发展成为世界范围内规模最大的搜索引擎。Google数据库现存有42.8亿个Web文件，每天处理的搜索请求已达2亿次，而且这一数字还在不断增长。Google借用Dmoz（http://dmoz.org/）的分类目录提供“网页目录”查询（http://www.google.com/dirhp?hl=zh-CN&tab=wd&ie=UTF-8&oe=UTF-8&q=），但默认网站排列顺序并非按照字母顺序，而是根据网站PageRank的分值高低排列。

　　⒉百度（http://www.baidu.com/）。百度是国内最早的商业化（早期为其它门户网站提供搜索服务，现在的竞价排名更是日进斗金）全文搜索引擎，拥有自己的网络机器人和索引数据库，专注于中文的搜索引擎市场，除有网页搜索外，百度还有新闻、MP3、图片等搜索，并在2003年底推出“贴吧”、按地域搜索等功能。

　　⒊中国搜索（http://www.huicong.com/）。中国搜索的前身是慧聪搜索，原慧聪搜索在联合中国网等30多家知名网站的基础上，2002年9月25日，正式组建了中国搜索联盟，经过一年多的发展，联盟成员就已达630多家，成为中国互联网一支重要的力量。由于发展迅速，慧聪集团借上市之机，将慧聪搜索更名为中国搜索，全力发展其在搜索引擎方面的业务，以打造中文搜索领域的全新品牌。

　　㈡主要分类目录

　　⒈雅虎中国分类目录（http://cn.yahoo.com/）。雅虎中国的分类目录是最早的分类目录，现有14个主类目，包括“商业与经济”、“艺术与人文”等，可以逐层进入进行检索，也可以利用关键词对“分类网站”进行搜索（http://m6.search.cnb.yahoo.com/dirsrch/）。此外，雅虎中国也可以对“所有网站”进行关键词搜索（http://cn.search.yahoo.com/websrch/），早期，他的搜索结果使用Google的数据，2004年2月正式推出自己的全文搜索引擎，并结束了与Google的合作。

　　⒉新浪分类目录（http://dir.sina.com.cn/）。新浪的分类目录目前共有18个大类目，用户可按目录逐级向下浏览，直到找到所需网站。就好像用户到图书馆找书一样，按照类别大小，层层查找，最终找到需要的网站或内容。通过和其它全文搜索引擎的合作，现在，也可以使用关键词对新浪的“分类网站”或“全部网站”进行搜索。

　　⒊搜狐分类目录（http://dir.sohu.com/）。搜狐分类目录把网站作为收录对象，具体的方法就是将每个网站首页的URL地址提供给搜索用户，并且将网站的题名和整个网站的内容简单描述一下，但是并不揭示网站中每个网页的信息内容。除此之外，也可以使用关键词对搜狐的“分类目录”或所有网站进行搜索。

　　⒋网易分类目录（http://search.163.com/）。网易的分类目录采用“开放式目录”管理方式，在功能齐全的分布式编辑和管理系统的支持下，现有5000多位各界专业人士参与可浏览分类目录的编辑工作，极大地适应了互联网信息爆炸式增长的趋势。在加强与其它搜索引擎合作的基础上，新版搜索引擎支持使用关键词对所有网站进


检索。

信息的生产、传播、搜集与查询是人类最基本的活动之一。考虑以文字为载体的信息，传统上有图书馆、相应的编目体系和专业人员帮助我们很快找到所需的信息，其粒度通常是“书”或者“文章”。随着计算机与信息技术的发展，有了信息检索（InformationRetrieval，IR）学科领域，有了关于图书或者文献的全文检索系统，使我们能很方便地在“关键词”的粒度上得到相关的信息。
我们注意到，上述全文检索系统一般工作在一个规模相对有限、内容相对稳定的馆藏（collection）上，被检索的对象通常是经过认真筛选和预先处理的（例如人工提取出了“作者”，“标题”等元数据，形成了很好的“摘要”等），并且系统需要同时响应的查询数量通常都不会太大（例如每秒钟10个左右）。
1994年左右，万维网（WorldWideWeb，简记为WWW或Web）出现。它的开放性（openness）和其上信息广泛的可访问性（accessibility）极大地鼓励了人们创作的积极性。作为一个信息源，Web和上述全文检索系统的工作对象相比，具有许多不同的特征，它们给信息检索领域带来了新的发展机遇和技术挑战。
规模大。在短短的10年左右时间，人类至少生产了40亿网页[Google,2004]，而人类有文字上万年以来产生了大约1亿本书；中国网上到2004年初大致有了约3亿网页[天网,2004]，而中华民族有史以来出版的书籍大约不过275万种。尽管书籍的容量和质量是一般网页不可比的，但在对应的时间背景上考察其文字的总体数量，我们不能不为人类在Web上创造文字的激情惊叹！
内容不稳定。除了不断有新的网页出现外，旧的网页会因为各种原因被删除（有研究指出50%网页的平均生命周期大约为50天[ChoandGarcia-Molina,2000,Cho,2002]）；
从原则上讲，读者数和作者数在同一个量级，形式和内容的随意性很强，权威性相对也不高，也不太可能进行人工筛选和预处理。
与生俱来的数字化、网络化。传统载体上的信息，人们目前正忙于将它们数字化、上网（花费极高），而网络信息天生如此。这个特性是一把双刃剑：一方面便于我们搜集和处理，另一方面也会使我们感到太多，蜂拥而至，鱼目混珠。
而作为要在Web上提供服务的信息查询系统，如搜索引擎和数字图书馆，通常要具备同时对付大量访问的能力（例如每秒钟1000个查询），而且响应时间还要足够的快（例如1秒钟）。
本书旨在介绍构建这类搜索引擎的有关技术。传统的IR

是其基础，同时也充分讨论了由上述Web信息的特征所带来的新问题及其解决方案。
早在Web
出现之前，互联网上就已经存在许多旨在让人们共享的信息资源。那些资源当时主要存在于各种允许匿名访问的FTP站点（anonymousftp），内容以学术技术报告、研究性软件居多，它们以计算机文件的形式存在，文字材料的编码通常是PostScript或者纯文本（那时还没有HTML）。
为了便于人们在分散的FTP资源中找到所需的东西，1990年加拿大麦吉尔大学（UniversityofMcGill）计算机学院的师生开发了一个软件，Archie。它通过定期搜集并分析FTP系统中存在的文件名信息，提供查找分布在各个FTP主机中文件的服务。Archie能在只知道文件名的前提下，为用户找到这个文件所在的FTP服务器的地址。Archie实际上是一个大型的数据库，再加上与这个大型数据库相关联的一套检索方法。该数据库中包括大量可通过FTP下载的文件资源的有关信息，包括这些资源的文件名、文件长度、存放该文件的计算机名及目录名等。尽管所提供服务的信息资源对象（非HTML文件）和本书所讨论搜索引擎的信息资源对象（HTML网页）不一样，但基本工作方式是相同的（自动搜集分布在广域网上的信息，建立索引，提供检索服务），因此人们公认Archie为现代搜索引擎的鼻祖。
值得一提的是，即使是在10多年后的今天，以FTP文件为对象的信息检索服务技术依然在发展，尤其是在用户使用界面上充分采用了Web风格。北大天网文件检索系统就是一个例子（见http://bingle.pku.edu.cn）。不过鉴于本书写作定位的关系，后面将主要讨论网页搜索引擎的相关问题。
以Web网页为对象的搜索引擎和以FTP文件为对象的检索系统一个基本的不同点在于搜集信息的过程。前者是利用HTML文档之间的链接关系，在Web上一个网页、一个网页的“爬取”（crawl），将那些网页“抓”（fetch）到本地后进行分析；后者则是根据已有的关于FTP站点地址的知识（例如得到了一个站点地址列表），对那些站点进行访问，获得其文件目录信息，并不真正将那些文件下载到系统上来。因此，如何在Web上“爬取”，就是搜索引擎要解决的一个基本问题。在这方面，1993年MatthewGray开发了WorldWideWebWanderer，它是世界上第一个利用HTML网页之间的链接关系来监测Web发展规模的“机器人”（robot）程序。刚开始时它只用来统计互联网上的服务器数量，后来则发展为能够通过它检索网站域名。鉴于其在Web上沿超链“爬行”的工作方式，这种程序有时也称为“蜘蛛”（spider）。因此，在文献中crawler,spider,robot一般都指的是相同的事物，即在Web上依照网页之间的超链关系一个个抓取网页的程序，通常也称为“搜集”。在搜索引擎系统中，也称为网页搜集子系统。
现代搜索引擎的思路源于Wanderer，不少人在MatthewGrey工作的基础上对它的蜘蛛程序做了改进。1994年7月，MichaelMauldin将JohnLeavitt的蜘蛛程序接入到其索引程序中，创建了大家现在熟知的Lycos，成为第一个现代意义的搜索引擎。在那之后，随着Web上信息的爆炸性增长，搜索引擎的应用价值也越来越高，不断有更新


更强的搜索引擎系统推出（下一节会有介绍）。
在许多场合，也称Yahoo!之类的门户网站提供的信息查找功能为搜索引擎。但从技术上讲，这样的门户中提供的搜索服务和前述搜索引擎是很不同的。这样的门户依赖的是人工整理的网站分类目录，一方面，用户可以直接沿着目录导航，定位到他所关心的信息；另一方面，用户也可以提交查询词，让系统将他直接引导到和该查询词最匹配的网站。图1-2就是我们在搜狐上查询“伊拉克战争”的结果。和图1-1相比，不难看到其风格是很不相同的。在需要区别的场合，我们可以分别称“自动搜索引擎”和“目录搜索引擎”，或者“网页搜索引擎”和“网站搜索引擎”。一般来讲，前者的信息搜索会更全面些，后者则会准确些。在没有特殊说明的情况下，本书中所讨论的“搜索引擎”不包括Yahoo!和搜狐这样的搜索方式。随着网上信息越来越多，单纯靠人工整理网站目录取得较高精度查询结果的优势逐渐退化——对海量的信息进行高质量的人工分类已经不太现实。目前有两个发展方向。一是利用文本自动分类技术，在搜索引擎上提供对每篇网页的自动分类，这方面最先看到的例子是Google的“网页分类”选项，但它分类的对象只是英文网页。在中文方面，文本自动分类的研究工作有很多，但我们知道的第一个在网上提供较大规模网页自动分类服务的是北大网络实验室冯是聪和龚笔宏等人的工作[冯是聪,2003]，他们于2002年10月在天网搜索上挂接了一个300万网页的分类目录。另一个发展方向是将自动网页爬取和一定的人工分类目录相结合，希望形成一个既有高信息覆盖率，也有高查询准确性的服务。互联网上信息量在不断增加，信息的种类也在不断增加。例如除了我们前面提到的网页和文件，还有新闻组，论坛，专业数据库等。同时上网的人数也在不断增加，网民的成分也在发生变化。一个搜索引擎要覆盖所有的网上信息查找需求已出现困难，因此各种主题搜索引擎，个性化搜索引擎，问答式搜索引擎等纷纷兴起。这些搜索引擎虽然还没有实现如通用搜索引擎那样的大规模应用，但随着互联网的发展，我们相信它们的生命力会越来越旺盛。另外，即使通用搜索引擎的运行现在也开始出现分工协作，有了专业的搜索引擎技术和搜索数据库服务提供商。例如美国的Inktomi，它本身并不是直接面向用户的搜索引擎，但向包括Overture（原GoTo）、LookSmart、MSN、HotBot等在内的其他搜索引擎提供全文网页搜集服务。从这个意义上说，它是搜索引擎数据的来源。搜索引擎出现虽然只有10年左右的历史，但在Web上已经有了确定不移的地位。据CNNIC统计，它已经成为继电子邮件之后的第二大Web应用。虽然它的基本工作原理已经相当稳定，但在其质量、性能和服务方式等方面的提高空间依然很大，研究成果层出不穷，是每年WWW学术年会1的重要论题之一。
本章介绍搜索引擎的基本工作原理和它作为一种网络应用软件的体系结构。在后面的三章中，我们将以一个实际的例子，具体展开在这些原理基础上实现的一种方案。通过这几章学习，读者将得到一个可实际运行搜索引擎的实现细节。第一节基本要求如在第一章第二节所述，搜索引擎是一个网络应用软件系统，对它有如下基本要求。能够接受用户通过浏览器提交的查询词或者短语，记作q，例如“非典”，“伊拉克战争”，“床前明月光”等等。在一个可以接受的时间内返回一个和该用户查询匹配的网页信息列表，记作L。上一章讲过，这个列表的每一条目至少包含三个元素（标题，网址链接，摘要）。q,q,…L,L,…1212搜索引擎网页数据库图2-1搜索引擎示意图这里有几个问题需要注意，它们对应上面黑体的文字：“可以接受的时间”，也就是响应时间。对于在Web上面向广大用户提供服务的软件来说，这个时间不能太长，通常也就在“秒”这个量级。这是衡量搜索引擎可用性的一个基本指标，也是和传统信息检索系统的一个差别。更进一步的，这样的响应时间要求不仅要能满足单个用户查询，而且要能在系统设计负载的情况下满足所有的用户。也就是说，系统应该在额定吞吐率的情况下保证秒级响应时间。这其中详细的分析将在中篇第八章展开。“匹配”，指的是网页中以某种形式包含有q的内容，其中最简单、最常见的形式就是q在其中直接出现。不过后面我们会看到，如果一个搜索引擎就是以百分之百满足这种简单的包含关系为目标，即使实现了也并不就达到了最好的效果。“列表”，这蕴含着一种“序”（rank）。在绝大多数情况下，L是相当长的，例如超过1万个条目（这是和图书馆全文检索系统的又一个不同，那里返回的列表通常较短，例如几十个条目）。这不仅是由于Web上的信息量大，也由于搜索引擎的查询方式简单。简单，意味着抽象；抽象，意味着有更多的具体事物可能是它的体现。对于一个长长的列表，很少有用户有耐心都审视一遍（不仅是因为长，还因为大多数使用搜索引擎的用户通常都是“找到为止”，而不是“不全部找到不罢休”，加上这个列表中和一个用户关心的其实只占很少的比例）。有分析统计表明，用户平均察看返回结果不超过2页[Baldi,etal.,2003],[Wang,etal.,2001],[单松巍,2003]。现代大规模高质量搜索引擎一般采用如图2-2所示的称之为三段式的工作流程，即：网页搜集、预处理和查询服务。搜集预处理服务图2-2搜索引擎三段式工作流程第二节网页搜集搜索引擎这样一个软件系统应该是何种工作方式？如果说软件系统是工作在某个数据集合上的程序的话，这个软件系统操作的数据不仅包括内容不可预测的用户查询，还要包括在数量上动态变化的海量网页，并且这些网页不会主动送到系统来，而是需要由系统去抓取。首先，我们考虑抓取的时机：事先还是即时。我们都有经验，在网络比较畅通的情况下，从网上下载一篇网页大约需要1秒钟左右，因此如果在用户查询的时候即时去网上抓来成千上万的网页，一个个分析处理，和用户的查询匹配，不可能满足搜索引擎的响应时间要求。不仅如此，这样做的系统效益也不高（会重复抓取太多的网页）；面对大量的用户查询，不可能想象每来一个查询，系统就到网上“搜索”一次


因此我们看到，大规模搜索引擎服务的基础应该是一批预先搜集好的网页（直接或者间接）。这一批网页如何维护？可以有两种基本的考虑。定期搜集，每次搜集替换上一次的内容，我们称之为“批量搜集”。由于每次都是重新来一次，对于大规模搜索引擎来说，每次搜集的时间通常会花几周。而由于这样做开销较大，通常两次搜集的间隔时间也不会很短（例如早期天网的版本大约每3个月来一次，Google在一段时间曾是每隔28天来一次）。这样做的好处是系统实现比较简单，主要缺点是“时新性”（freshness）不高，还有重复搜集所带来的额外带宽的消耗。增量搜集，开始时搜集一批，往后只是（1）搜集新出现的网页，（2）搜集那些在上次搜集后有过改变的网页，（3）发现自从上次搜集后已经不再存在了的网页，并从库中删除。由于除新闻网站外，许多网页的内容变化并不是很经常的（有研究指出50%网页的平均生命周期大约为50天[ChoandGarcia-Molina,2000]，[Cho,2002]），这样做每次搜集的网页量不会很大（例如我们在2003年初估计中国每天有30-50万变化了的网页），于是可以经常启动搜集过程（例如每天）。30万网页，一台PC机，在一般的网络条件下，半天也就搜集完了。这样的系统表现出来的信息时新性就会比较高，主要缺点是系统实现比较复杂；这种复杂还不仅在于搜集过程，而是还在于下面要谈到的建索引的过程。上面讲的是系统网页数据库维护的基本策略。在这两种极端的情况之间也可能有一些折中的方案，J.Cho博士在这方面做过深入的研究[ChoandGarcia-Molina,2000]，[Cho,2002]，根据一种网页变化模型和系统所含内容时新性的定义，提出了相应优化的网页搜集策略。其中一个有趣的结论是：在系统搜集能力一定的情况下，若有两类网页（例如“商业”和“教育”），它们的更新周期差别很大（例如“商业”类网页平均更新周期是“天”，而“教育”类网页平均更新周期是“月”），则系统应该将注意力放在更新慢的网页上[ChoandGarcia-Molina,2000]，以使系统整体的时新性达到比较高的取值。在具体搜集过程中，如何抓取一篇篇的网页，也可以有不同的考虑。最常见的一种是所谓“爬取”：将Web上的网页集合看成是一个有向图，搜集过程从给定起始URL集合S（或者说“种子”）开始，沿着网页中的链接，按照先深、先宽、或者某种别的策略遍历，不停的从S中移除URL，下载相应的网页，解析出网页中的超链接URL，看是否已经被访问过，将未访问过的那些URL加入集合S。整个过程可以形象地想象为一个蜘蛛（spider）在蜘蛛网（Web）上爬行（crawl）。后面我们会看到，真正的系统其实是多个“蜘蛛”同时在爬。这种方式的好处除了概念很漂亮，一般实现起来也不困难外，还有很重要的一条是容易通过一定的策略，使搜集到的网页相对比较“重要”。前面提过，任何1所谓“间接”，指的是提供搜索服务的系统可能利用别人已经事先抓好的数据，元搜索引擎就是如此。
搜索引擎是不可能将Web上的网页搜集完全的，通常都是在其他条件的限制下决定搜集过程的结束（例如磁盘满，或者搜集时间已经太长了）。因此就有一个尽量使搜到的网页比较重要的问题，这对于那些并不追求很大的数量覆盖率的搜索引擎特别重要。研究表明[NajorkandWiener,2001]，按照先宽搜索方式得到的网页集合要比先深搜索得到的集合重要（这里当然有一个重要性的指标问题）。这种方式的一个困难是要从每一篇网页中提取出所含的URL。由于HTML的灵活性，其中出现URL的方式各种各样，将这个环节做得彻底不容易（例如我们现在还没有很好的简单办法从JavaScript脚本中提取URL）。同时，由于Web的“蝴蝶结”形状[Broder,etal.,2000]，这种方式搜集到的网页不大会超过所有目标网页数量2的2/3。另外一种可能的方式是在第一次全面网页搜集后，系统维护相应的URL集合S，往后的搜集直接基于这个集合。每搜到一个网页，如果它发生变化并含有新的URL，则将它们对应的网页也抓回来，并将这些新URL也放到集合S中；如果S中某个url对应的网页不存在了，则将它从S中删除。这种方式也可以看成是一种极端的先宽搜索，即第一层是一个很大的集合，往下最多只延伸一层。还有一种方法是让网站拥有者主动向搜索引擎提交它们的网址（为了宣传自己，通常会有这种积极性），系统在一定时间内（2天到数月不等）定向向那些网站派出“蜘蛛”程序，扫描该网站的所有网页并将有关信息存入数据库中。大型商业搜索引擎一般都提供这种功能。第三节预处理得到海量的原始网页集合，距离面向网络用户的检索服务之间还有相当的距离。宏观地看，服务子系统是一个程序。采用Wirth关于“程序=算法+数据结构”的观点来考察这个程序，一个合适的数据结构是查询子系统工作的核心和关键。这里只是指出：现行最有效的数据结构是“倒排文件”（invertedfile）；倒排文件是用文档中所含关键词作为索引，文档作为索引目标的一种结构（类似于普通书籍中，索引是关键词，书的页面是索引目标）。我们在第八章中有进一步分析。下面讨论从网页集合形成这样的倒排文件过程中的几个主要问题，即我们所说的“预处理”。主要包括四个方面，关键词的提取，“镜像网页”（网页的内容完全相同，未加任何修改）或“转载网页”（near-replicas，主题内容基本相同但可能有一些额外的编辑信息等，转载网页也称为“近似镜像网页”）的消除，链接分析和网页重要程度的计算。1.关键词的提取2所谓“目标网页”指的是搜索引擎设计覆盖的网页范围。例如Google是全球，天网是全中国。
随便取一篇网页的源文件（例如通过浏览器的“查看源文件”功能），我们可以看到其中的情况纷乱繁杂。除了我们从浏览器中能够正常看到的文字内容外，还有大量的HTML标记。根据天网统计，网页文档源文件的大小（字节量）通常大约是其中内容大小的4倍（例如http://net.pku.edu.cn就是如


！）。另外，由于HTML文档产生来源的多样性，许多网页在内容上比较随意，不仅文字不讲究规范、完整，而且还可能包含许多和主要内容无关的信息（例如广告，导航条，版权说明等）。这些情况既给有效的信息查询带来了挑战，也带来了一些新的机遇，在后面的章节将会有进一步的论述。这里我们只是指出，为了支持后面的查询服务，需要从网页源文件中提取出能够代表它的内容的一些特征。从人们现在的认识和实践来看，所含的关键词即为这种特征最好的代表。于是，作为预处理阶段的一个基本任务，就是要提取出网页源文件的内容部分所含的关键词。对于中文来说，就是要根据一个词典Σ，用一个所谓“切词软件”，从网页文字中切出Σ所含的词语来。在那之后，一篇网页主要就由一组词来近似代表了，p={t,t,…,t}。12n一般来讲，我们可能得到很多词，同一个词可能在一篇网页中多次出现。从效果(effectiveness)和效率（efficiency）考虑，不应该让所有的词都出现在网页的表示中，要去掉诸如“的”，“在”等没有内容指示意义的词，称为“停用词”(stopword)。这样，对一篇网页来说，有效的词语数量大约在200个左右。2.重复或转载网页的消除与生俱来的数字化和网络化给网页的复制以及转载和修改再发表带来了便利，因此我们看到Web上的信息存在大量的重复现象。天网在2003年的一次大规模统计分析表明，网页的重复率平均大约为4。也就是说，当你通过一个URL在网上看到一篇网页的时候，平均还有另外3个不同的URL也给出相同或者基本相似的内容。这种现象对于广大的网民来说是有正面意义的，因为有了更多的信息访问机会。但对于搜索引擎来说，则主要是负面的；它不仅在搜集网页时要消耗机器时间和网络带宽资源，而且如果在查询结果中出现，无意义地消耗了计算机显示屏资源，也会引来用户的抱怨，“这么多重复的，给我一个就够了”。因此，消除内容重复或主题内容重复的网页是预处理阶段的一个重要任务。第七章对此有详细的分析论述。3.链接分析前面提到，大量的HTML标记既给网页的预处理造成了一些麻烦，也带来了一些新的机遇。从信息检索的角度讲，如果系统面对的仅仅是内容的文字，我们能依据的就是“共有词汇假设”（sharedbagofwords），即内容所包含的关键词集合，最多加上词频（termfrequency或tf、TF）和词在文档集合中出现的文档频率（documentfrequency或df、DF）之类的统计量。而TF和DF这样的频率信息能在一定程度上指示词语在一篇文档中的相对重要性或者和某些内容的相关性，这是有意义的。有了HTML标记后，情况还可能进一步改善，例如在同一篇文档中，之间的信息很可能就比在之间的信息更重要。特别地，HTML文档中所含的指向其他文档的链接信息是人们近几年来特别关注的对象，认为它们不仅给出了网页之间的关系，而且还对判断网页的内容有很重要的作用。例如“北大学报”这几个字在北京大学学报社会科学版的主页上是没有的，因此一个仅靠内容文字分析的搜索引擎就不可能返回该主页作为结果。但是北京大学主页上是用“北大学报（社）”作为链接信息指向了北京大学学报社会科学版的主页。因此在很好利用链接信息的搜索引擎中应该能返回北京大学学报社会科学版的主页。4.网页重要程度的计算搜索引擎返回给用户的，是一个和用户查询相关的结果列表。列表中条目的顺序是很重要的一个问题。由于面对各种各样的用户，加之查询的自然语言风格，对同样的q返回相同的列表肯定是不能使所有提交q的用户都满意的（或者都达00到最高的满意度）。因此搜索引擎实际上追求的是一种统计意义上的满意。人们认为Google目前比天网好，是因为在多数情况下前者返回的内容要更符合用户的需要，而不是所有情况下都如此。如何对查询结果进行排序有很多因素需要考虑，后面将有深入的讨论。这里只是概要解释在预处理阶段可能形成的所谓“重要性”因素。顾名思义，既然是在预处理阶段形成的，就是和用户查询无关的。如何讲一篇网页比另外一篇网页重要？人们参照科技文献重要性的评估方式，核心想法就是“被引用多的就是重要的”。“引用”这个概念恰好可以通过HTML超链在网页之间体现得非常好，作为Google创立核心技术的PageRank就是这种思路的成功体现[Page,etal.,1998]。除此以外，人们还注意到网页和文献的不同特点，即一些网页主要是大量对外的链接，其本身基本没有一个明确的主题内容，而另外有些网页则被大量的其他网页链接。从某种意义上讲，这形成了一种对偶的关系，这种关系使得人们可以在网页上建立另外一种重要性指标[Kleinberg,1998]。这些指标有的可以在预处理阶段计算，有的则要在查询阶段计算，但都是作为在查询服务阶段最终形成结果排序的部分参数。第四节查询服务如上述，从一个原始网页集合S开始，预处理过程得到的是对S的一个子集的元素的某种内部表示，这种表示构成了查询服务的直接基础。对每个元素来说，这种表示至少包含如下几个方面：倒排文件就是用词来作为索引的一个数据结构，显然，q中的词必须是包含在倒排文件词表中才有意义。有了这样的q，它的每一个元素都对应倒排文件中的一个倒排表（文档编号的集合），记作L(t)，它们的交集即为对应查询的结果文档集合，i从而实现了查询和文档的匹配。上述过程的基本假设是：用户是希望网页包含所输入查询文字的。2.结果排序上面，我们了解了得到和用户查询相关的文档集合的过程。这个集合的元素需要以一定的形式通过计算机显示屏呈现给用户。就目前的技术情况看，列表是最常见的形式（但人们也在探求新的形式，如Vivisimo引擎将结果页面以类别的形式呈现）。给定一个查询结果集合，R={r,r,…,r}，所谓列表，就是按照某种12n评价方式，确定出R中元素的一个顺序，让这些元素以这种顺序呈现出来。笼统地讲，ri和q的相关性（relevance）是形成这种顺序的基本因素。但是，有效地定义相关性本身是很困难的，从原理上讲它不仅和查询词有关，而且还和用户的背景，以及用户的查询历史


关。不同需求的用户可能输入同一个查询，同一个用户在不同的时间输入的相同的查询可能是针对不同的信息需求。为了形成一个合适的顺序，在搜索引擎出现的早期人们采用了传统信息检索领域很成熟的基于词汇出现频度的方法。大致上讲就是一篇文档中包含的查询（q）中的那些词越多，则该文档就应该排在越前面；再精细一些的考虑则是若一个词在越多的文档中有出现，则该词用于区分文档相关性的作用就越小。这样一种思路不仅有一定直觉上的道理，而且在倒排文件数据结构上很容易实现。因为，当我们通过前述关键词的提取过程，形成一篇文档的关键词集合，p={t,t,…,t}的时候，很容易同12n时得到每一个ti在该文档中出现的次数，即词频，而倒排文件中每个倒排表的长度则对应着一个词所涉及的文档的篇数，即文档频率。然而，由于网页编写的自发性、随意性较强，仅仅针对词的出现来决定文档的顺序，在Web上做信息检索表现出明显的缺点，需要有其他技术的补充。这方面最重要的成果就是前面提到过的PageRank。通过在预处理阶段为每篇网页形成一个独立于查询词（也就和网页内容无关）的重要性指标，将它和查询过程中形成的相关性指标结合形成一个最终的排序，是目前搜索引擎给出查询结果排序的主要方法。