所谓“搜索引擎”，说到底是一个计算机应用软件系统，或者说是一个网络应用软件系统。从网络用户的角度
看，它根据用户提交的类自然语言查询词或者短语，返回一系列很可能与该查询相关的网页信息，供用户进一
步判断和选取。为了有效地做到这一点，它大致上被分成三个功能模块，或者三个子系统；即网页搜集，预处
理和查询服务。
现代大规模高质量搜索即：网页搜集、预处理和查询服务。
在具体搜集过程中，如何抓取一篇篇的网页，也可以有不同的考虑。最常见的一种是所谓“爬取”：
将Web上的网页集合看成是一个有向图，搜集过程从给定起始URL集合S（或者说“种子”）开始，沿着网页中的
链接，按照先深、先宽、或者某种别的策略遍历，不停的从S中移除URL，下载相应的网页，解析出网页中的超
链接URL，看是否已经被访问过，将未访问过的那些URL加入集合S。整个过程可以形象地想象为一个蜘蛛
（spider）在蜘蛛网（Web）上爬行（crawl）。后面我们会看到，真正的系统其实是多个“蜘蛛”同时在爬。
另外一种可能的方式是在第一次全面网页搜集后，系统维护相应的URL集合S，往后的搜集直接基于这
个集合。每搜到一个网页，如果它发生变化并含有新的URL，则将它们对应的网页也抓回来，并将这些新URL也
放到集合S中；如果S中某个url对应的网页不存在了，则将它从S中删除。这种方式也可以看成是一种极端的先
宽搜索，即第一层是一个很大的集合，往下最多只延伸一层。还有一种方法是让网站拥有者主动向搜索引擎提
交它们的网址（为了宣传自己，通常会有这种积极性），系统在一定时间内（2天到数月不等）定向向那些网站
派出“蜘蛛”程序，扫描该网站的所有网页并将有关信息存入数据库中。大型商业搜索引擎一般都提供这种功
能。
，一个合适的数据结构是查询子系统工作的核心和关键。这里只是指出：现行最有效的数据结构是“
倒排文件”（inverted file）；倒排文件是用文档中所含关键词作为索引，文档作为索引目标的一种结构（类
似于普通书籍中，索引是关键词，书的页面是索引目标）
下面讨论从网页集合形成这样的倒排文件过程中的几个主要问题，即我们所说的 “预处理”。主要包
括四个方面，关键词的提取，“镜像网页”（网页的内容完全相同，未加任何修改）或“转载网页”（near-
replicas，主题内容基本相同但可能有一些额外的编辑信息等，转载网页也称为“近似镜像网页”）的消除，
链接分析和网页重要程度的计算。
这里我们只是指出，为了支持后面的查询服务，需要从网页源文件中提取出能够代表它的内容的一些
特征。从人们现在的认识和实践来看，所含的关键词即为这种特征最好的代表。于是，作为预处理阶段的一个
基本任务，就是要提取出网页源文件的内容部分所含的关键词。
对于中文来说，就是要根据一个词典Σ，用一个所谓“切词软件”，从网页文字中切出Σ所含的词语
来。在那之后，一篇网页主要就由一组词来近似代表了，p = {t1, t2, …, tn}。一般来讲，我们可能得到很
多词，同一个词可能在一篇网页中多次出现。从效果(effectiveness)和效率（efficiency）考虑，不应该让所
有的词都出现在网页的表示中，要去掉诸如“的”，“在”等没有内容指示意义的词，称为“停用词”(stop
word)。这样，对一篇网页来说，有效的词语数量大约在200个左右。
。从信息检索的角度讲，如果系统面对的仅仅是内容的文字，我们能依据的就是“共有词汇假
设”（shared bag of words），即内容所包含的关键词集合，最多加上词频（term frequency 或tf、TF）和
词在文档集合中出现的文档频率（document frequency 或df、DF）之类的统计量。而TF和DF这样的频率信息能
在一定程度上指示词语在一篇文档中的相对重要性或者和某些内容的相关性，这是有意义的。
，从一个原始网页集合S开始，预处理过程得到的是对S的一个子集的元素的某种内部表示，这种表示
构成了查询服务的直接基础。对每个元素来说，这种表示至少包含如下几个方面：
原始网页文档
aURL和标题
b编号
c所含的重要关键词的集合（以及它们在文档中出现的位置信息）
d其他一些指标（例如重要程度，分类代码等）
而系统关键词总体的集合和文档的编号一起构成了一个倒排文件结构，使得一旦得到一个关键词输入，系统能
迅速给出相关文档编号的集合输出。
服务子系统是在服务进行的过程中涉及的相关软件程序，而为这些软件程序事先准备数据的程序都算
在预处理子系统中。下面来看对服务子系统的要求和其工作原理，主要有三个方面。
1. 查询方式和匹配
查询方式指的是系统允许用户提交查询的形式。考虑到各种用户的不同背景和不同的信息需求，不可
能有一种普适的方式。一般认为，对于普通网络用户来说，最自然的方式就是“要什么就输入什么”一般地，
我们用q0表示用户提交的原始查询，例如，q0 =“网络与分布式系统实验室”。它首先需要被“切
词”（segment）或称“分词”，即把它分成一个词的序列。如上例，则为“网络 与 分布式 系统 实验室”（
注意，不同的分词软件可能得出不同的结果，这里用的是北大计算语言所的在线分词软件）。然后需要删除那
些没有查询意义或者几乎在每篇文档中都会出现的词（例如“的”），在本例中即为“与”。最后形成一个用
于参加匹配的查询词表，q = {t1, t2, …, tm}，在本例中就是q = {网络，分布式，系统，实验室}。倒排文
件就是用词来作为索引的一个数据结构，显然，q中的词必须是包含在倒排文件词表中才有意义。有了这样的q
，它的每一个元素都对应倒排文件中的一个倒排表（文档编号的集合），记作L(ti)，它们的交集即为对应查询
的结果文档集合，从而实现了查询和文档的匹配。上述过程的基本假设是：用户是希望网页包含所输入查询文
字的。
2. 结果排序
上面，我们了解了得到和用户查询相关的文档集合的过程。这个集合的元素需要以一定的形式通过计
算机显示屏呈现给用户。就目前的技术情况看，列表是最常见的形式（但人们也在探求新的形式，如Vivisimo
引擎将结果页面以类别的形式呈现）。给定一个查询结果集合，R={r1, r2, …, rn}，所谓列表，就是按照某
种评价方式，确定出R中元素的一个顺序，让这些元素以这种顺序呈现出来。笼统地讲，ri和q的相关性
（relevance）是形成这种顺序的基本因素。但是，有效地定义相关性本身是很困难的，从原理上讲它不仅和查
询词有关，而且还和用户的背景，以及用户的查询历史有关。不同需求的用户可能输入同一个查询，同一个用
户在不同的时间输入的相同的查询可能是针对不同的信息需求。为了形成一个合适的顺序，在搜索引擎出现的
早期人们采用了传统信息检索领域很成熟的基于词汇出现频度的方法。大致上讲就是一篇文档中包含的查询（q
）中的那些词越多，则该文档就应该排在越前面；再精细一些的考虑则是若一个词在越多的文档中有出现，则
该词用于区分文档相关性的作用就越小。这样一种思路不仅有一定直觉上的道理，而且在倒排文件数据结构上
很容易实现。
然而，由于网页编写的自发性、随意性较强，仅仅针对词的出现来决定文档的顺序，在Web上做信息检
索表现出明显的缺点，需要有其他技术的补充。这方面最重要的成果就是前面提到过的PageRank。通过在预处
理阶段为每篇网页形成一个独立于查询词（也就和网页内容无关）的重要性指标，将它和查询过程中形成的相
关性指标结合形成一个最终的排序，是目前搜索引擎给出查询结果排序的主要方法。
3. 文档摘要
搜索引擎给出的结果是一个有序的条目列表，每一个条目有三个基本的元素：标题，网址和摘要。其
中的摘要需要从网页正文中生成。一般来讲，从一篇文字中生成一个恰当的摘要是自然语言理解领域的一个重
要课题，人们已经做了多年的工作并取得了一些成果。但相关的技术用到网络搜索引擎来有两个基本困难。一
是网页的写作通常不规范，文字比较随意，因此从语言理解的角度难以做好；二是复杂的语言理解算法耗时太
多，不适应搜索引擎要高效处理海量网页信息的需求。
因此搜索引擎在生成摘要时要简便许多，基本上可以归纳为两种方式，一是静态方式，即独立于查询
，按照某种规则，事先在预处理阶段从网页内容提取出一些文字，例如截取网页正文的开头512个字节（对应
256个汉字），或者将每一个段落的第一个句子拼起来，等等。这样形成的摘要存放在查询子系统中，一旦相关
文档被选中与查询项匹配，就读出返回给用户。
我们有了“动态摘要”方式，即在响应查询的时候，根据查询词在文档中的位置，提取出周围的文字
来，在显示时将查询词标亮。这是目前大多数搜索引擎采用的方式。为了保证查询的效率，需要在预处理阶段
分词的时候记住每个关键词在文档中出现的位置。