第一节 搜索引擎的基本工作机制
大型互联网搜索引擎的数据中心一般运行数千台甚至数十万台计算机，而且每天向计算机集群里添加数十台机器，以保持与网络发展的同步。搜集机器自动搜集网页信息，平均速度每秒数十个网页，检索机器则提供容错的可缩放的体系架构以应对每天数千万甚至数亿的用户查询请求。企业搜索引擎可根据不同的应用规模，从单台计算机到计算机集群都可以进行部署。 搜索引擎一般的工作过程是：首先对互联网上的网页进行搜集，然后对搜集来的网页进行预处理，建立网页索引库，实时响应用户的查询请求，并对查找到的结果按某种规则进行排序后返回给用户。搜索引擎的重要功能是能够对互联网上的文本信息提供全文检索。 图1 搜索引擎的工作流程 搜索引擎通过客户端程序接收来自用户的检索请求，现在最常见的客户端程序就是浏览器，实际上它也可以是一个用户开发的简单得多的网络应用程序。用户输入的检索请求一般是关键词或者是用逻辑符号连接的多个关键词，搜索服务器根据系统关键词字典，把搜索关键词转化为wordID，然后在标引库（倒排文件）中得到docID列表，对docID列表中的对象进行扫描并与wordID进行匹配，提取满足条件的网页，然后计算网页与关键词的相关度，并根据相关度的数值将前K篇结果(不同的搜索引擎每页的搜索结果数不同)返回给用户，其处理流程如图1所示。 图2描述了一般搜索引擎的系统架构，其中包括页面搜集器、索引器、检索器、索引文件等部分，下面对其中的主要部分的功能实现进行了介绍。 图2 搜索引擎各个组成部分的关系图3搜索引擎抓取网页过程
一、搜集器搜索引擎通过一种程序robot（又称spider），搜集器的功能是在互联网中漫游，发现并搜集信息，它搜集的信息类型多种多样，包括HTML页面、XML文档、Newsgroup文章、FTP文件、字处理文档、多媒体信息等。搜索器是一个计算机程序，其实现常常采用分布式和并行处理技术，以提高信息发现和更新的效率。商业搜索引擎的搜集器每天可以搜集几百万甚至更多的网页。搜索器一般要不停地运行，要尽可能多、尽可能快地搜集互联网上的各种类型的新信息。因为互联网上的信息更新很快，所以还要定期更新已经搜集过的旧信息，以避免死链接和无效链接。另外，因为Web信息是动态变化的，因此搜集器、分析器和索引器要定期更新数据库，更新周期通常约为几周甚至几个月。索引数据库越大，更新也越困难。
互联网上的信息太多，即使功能强大的搜集器也不可能搜集互联网上的全部信息。因此，搜集器采用一定的搜索策略对互联网进行遍历并下载文档，例如，一般采用以广度优先搜索策略为主、线性搜索策略为辅的搜索策略。 在搜集器实现时，系统中维护一个超链队列，或者堆栈，其中包含一些起始URL( 理解成像DMOZ、Yahoo目录Google sitemap等），搜集器从这些URL出发，下载相应的页面，并从中抽取出新的超链加入到队列或者堆栈中，上述过程不断重复队列直到堆栈为空。为提高效率，搜索引擎将Web空间按照域名、IP地址或国家域名进行划分，使用多个搜集器并行工作，让每个搜索器负责一个子空间的搜索。为了便于将来扩展服务，搜集器应能改变搜索范围。 1、线性搜集策略 线形搜索策略的基本思想是从一个起始的IP地址出发，按IP地址递增的方式搜索后续的每一个IP地址中的信息，完全不考虑各站点的HTML文件中指向其他Web站点的超链地址。此策略不适用于大规模的搜索（主要原因在于IP可能是动态的），但可以用于小范围的全面搜索，利用此种策略的搜集器可以发现被引用较少或者还没有被其他HTML文件引用的新HTML文件信息源。2、深度优先搜集策略
深度优先搜集策略是早期开发搜集器使用较多的一种方法，它的目的是要达到被搜索结构的叶结点。深度优先搜索顺着HTML文件上的超链走到不能再深入为止，然后返回到上一个接点的HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。深度优先搜索适宜遍历一个指定的站点或者深层嵌套的HTML文件集，但对于大规模的搜索，由于Web结构相当深，也许永远也出不来了3、广度优先搜集策略
广度优先搜集策略是先搜索同一层中的内容，然后再继续搜索下一层。假如一个HTML文件中有三个超链，选择其中之一并处理相应的HTML文件（注意：这里的处理文件指的是对文件内容进行检索，文件上的其他超链接先不作处理），然后返回并选择刚才第一个网页的第二个超链，处理相应的HTML文件，再返回。一旦同一层上的所有超链都已被处理过，就可以开始在刚才处理过的HTML文件中搜索其余的超链。（广度链接的定义） 这样保证了对浅层的首先处理，当遇到一个无穷尽的深层分支时，也就不会再陷进去。宽度优先搜集策略容易实现并被广泛采用，但是需要花费比较长的时间才能到达深层的HTML文件4、收录搜集策略
有些网页可以通过用户提交的方式进行搜集，例如某些商业网站向搜索引擎发出收录申请，搜集器就可以定向搜集提交申请网站的网页信息并加入到搜索引擎的索引数据库中。 二、分析器 对搜集器搜集来的网页信息或者下载的文档一般要首先进行分析，以用于建立索引，文档分析技术一般包括: 分词（有些仅从文档某些部分抽词，如Altavista）、过滤（使用停用词表stoplist）、转换（有些对词条进行单复数转换、词缀去除、同义词转换等工作），这些技术往往与具体的语言以及系统的索引模型密切相关。三、索引器
索引器的功能是对搜索器所搜索的信息进行分析处理，从中抽取出索引项，用于表示文档以及生成文档库的索引表。索引项有元数据索引项和内容索引项两种: 元数据索引项与文档的语意内容无关，如作者名、URL、更新时间、编码、长度、链接流行度为元数据索引项等等; 内容索引项是用来反映文档内容的，如关键词及其权重、短语、单字等等。内容索引项可以分为单索引项和多索引项（或称短语索引项）两种。单索引项对于英文来讲是英语单词，比较容易提取，因为单词之间有天然的分隔符（空格）; 对于中文等连续书写的语言，必须进行词语的切分。在搜索引擎中，一般要给单索引项赋予一个权值，以表示该索引项对文档的区分度，同时用来计算查询结果的相关度。使用的方法一般有统计法、信息论法和概率法。短语索引项的提取方法有统计法、概率法和语言学法。 为了快速查找到特定的信息，建立索引数据库是一个常用的方法，即将文档表示为一种便于检索的方式并存储在索引数据库中。索引数据库的格式是一种依赖于索引机制和算法的特殊数据存储格式。索引的质量是Web信息检索系统成功的关键因素之一。一个好的索引模型应该易于实现和维护、检索速度快、空间需求低。搜索引擎普遍借鉴了传统信息检索中的索引模型，包括倒排文档、矢量空间模型、概率模型等。例如在矢量空间索引模型中，每个文档d都表示为一个范化矢量V(d)=(t1,w1 (d)…ti,w1(d)…tn,wn(d))。其中ti为词条项，wi(d)为ti在d中的权值，一般被定义为ti在d中出现频率tfi(d)的函数。 索引器的输出是索引表，它一般使用倒排形式（Inversion List），即由索引项查找相应的文档。索引表也可能记录索引项在文档中出现的位置，以便检索器计算索引项之间的相邻或接近关系（proximity）。索引器可以使用集中式索引算法或分布式索引算法。当数据量很大时，必须实现实时索引（Instant Indexing），否则就无法跟上信息量急剧增加的速度。索引算法对索引器的性能（如大规模峰值查询时的响应速度）有很大的影响。一个搜索引擎的有效性在很大程度上取决于索引的质量四、检索器
检索器的功能是根据用户的查询在索引库中快速检出文档，进行文档与查询的相关度评价，对将要输出的结果进行排序，并实现某种用户相关性反馈机制。检索器常用的信息检索模型有集合理论模型、代数模型、概率模型和混合模型等多种，可以查询到文本信息中的任意字词，无论出现在标题还是正文中。 检索器从索引中找出与用户查询请求相关的文档，采用与分析索引文档相识的方法来处理用户查询请求。如在矢量空间索引模型中，用户查询q首先被表示为一个范化矢量V(q)=(t1,w1(q); …; ti,wi(q); …; tn,wn(q))，然后按照某种方法来计算用户查询与索引数据库中每个文档之间的相关度，而相关度可以表示为查询矢量V(q)与文档矢量V(d)之间的夹角余弦，最后将相关度（怎样判断相关度？文件内容、文件的反响链接数与质量）大于阀值的所有文档按照相关度递减的顺序排列并返还给用户。当然搜索引擎的相关度判断并不一定与用户的需求完全吻合。五、用户接口
用户接口的作用是为用户提供可视化的查询输入和结果输出界面，方便用户输入查询条件、显示查询结果、提供用户相关性反馈机制等，其主要目的是方便用户使用搜索引擎，高效率、多方式地从搜索引擎中得到有效的信息。用户接口的设计和实现必须基于人机交互的理论和方法，以适应人类的思维和使用习惯。 在查询界面中，用户按照搜索引擎的查询语法制定待检索词条及各种简单或高级检索条件。简单接口只提供用户输入查询串的文本框，复杂接口可以让用户对查询条件进行限制，如逻辑运算（与、或、非）、相近关系（相邻、NEAR）、域名范围（如edu、com）、出现位置（如标题、内容）、时间信息、长度信息等等。目前一些公司和机构正在考虑制定查询选项的标准。 在查询输出界面中，搜索引擎将检索结果展现为一个线性的文档列表，其中包含了文档的标题、摘要、快照和超链等信息。由于检索结果中相关文档和不相关文档相互混杂，用户需要逐个浏览以找出所需文档。