在体验搜索引擎的开发过程之前，我们先在第 1 章介绍一下搜索引擎的基本概念。搜索引擎的基础是应用于信息检索、数据库等领域的信息技术，要想开发搜索引擎，横跨多个领域的广泛知识是不可或缺的。在本章我们尽可能通俗易懂、简明扼要地总结归纳了这些知识。由于本章讲解的是后续章节的背景知识，所以恳请诸位认真地读下去。

1-1　理解搜索引擎的构成

在本节，我们首先介绍什么是搜索引擎，然后再大略地讲解其基本架构。由于从 1-2 节开始还会详细地讲解有关内容，所以在本节就让我们先在大体上了解一下搜索引擎的全貌吧。

什么是搜索引擎

搜索引擎是一类系统或软件的统称，作用是从文档的集合中查找（检索）出匹配信息需求（查询）的文档，信息需求是由单词、问题等构成的。

确切地说，本书所讲解的搜索引擎其实是“全文搜索引擎”。所谓的“全文”指的就是全部的句子，当检索的对象为“由文本构成的文档中的全部句子”时，对于该文档进行的检索就称为全文搜索。而实现了这种全文搜索的系统就是全文搜索引擎（全文搜索系统），在英文中一般称为 Full-text Search Engine。在本书之后的章节中，提到“搜索引擎”指的就是全文搜索引擎。

在现代的搜索引擎中，不仅能看到 Google 和 Yahoo! 等 Web 检索，还可以看到邮件检索和专利检索等各式各样的应用程序（应用层）。当然，应用程序的用途和使用方式不同，搜索引擎的规模和其所要求的系统必备条件也就不同。尽管如此，在这些应用程序中，搜索引擎的基本结构却没有太大的差异。本书将以搜索引擎的基本结构为主进行讲解。

下面，就让我们先从搜索引擎的全貌看起吧。

构成搜索引擎的组件

搜索引擎一般由以下 4 个组件构成。

• 索引管理器（Index Manager）

• 索引检索器（Index Searcher）

• 索引构建器（Indexer）

• 文档管理器（Document Manager）

展示了构成搜索引擎的全部要素。首先让我们简单地看看这些组件都在进行着怎样的工作吧。

∎ 索引管理器

索引管理器组件的作用是管理带有索引结构的数据，索引结构是一种用于进行高速检索的数据结构。对索引的访问也是通过索引管理器进行的。

索引管理器通常是将索引作为二级存储上的二进制文件来进行管理的。而且，还经常会通过保存经过压缩的索引来达到减少从二级存储加载的数据量，提升检索处理效率的目的。

∎ 索引检索器

索引检索器是利用索引进行全文搜索处理的组件。索引检索器根据来自检索应用程序用户的查询，协同索引管理器进行检索处理。在大多数情况下，索引检索器都会根据某种标准对与查询相匹配的检索结果排序，并将排在前面的结果返回给应用程序。

另外，本书将查询和信息需求视为同义词。所谓查询是指“由 1 个以上的单词或词组组成的对搜索引擎的询问”。

∎ 索引构建器

索引构建器是从作为检索对象的文本文档中生成索引的组件。索引构建器会先通过解析将文本文档分解为单词序列，然后再将该单词序列转换为索引结构。在搜索引擎中，将生成索引的环节称为索引构建(Index Construction)。

∎ 文档管理器

文档管理器是管理文档数据库的组件，文档数据库中储存着作为检索对象的文档。文档管理器会先从文档数据库中取出与查询相匹配的文档，然后再根据需要从该文档中提取出一部分内容作为摘要。

由于文档管理器的结构非常简单，只是对应着文档特定的 ID（文档编号）来保存文档的内容，所以本书就省略了相关的详细介绍。我们经常能看到有人将数据库管理系统（DBMS）和基于二级存储的数据库管理器（DBM）等用作文档管理器。

由文档管理器管理的文档数据库既可以在构建索引的阶段随索引一同构建，也可以提前构建。

与搜索引擎相关的组件

严格来讲，本节所介绍的爬虫和搜索排序系统虽不是搜索引擎的一部份，但却是与搜索引擎密切相关的组件。

∎ 爬虫

爬虫 (Crawler) 是用于收集 Web 上的 HTML 文件等文档的系统（机器人）。例如，用于 Web 检索的爬虫就是通过追随 Web 页面上的超链接来收集全世界的 HTML 网页的。全世界的 Web 页面正以惊人的速度不断增长，因此爬虫的任务就是高效地收集这些网页。

∎ 搜索排序系统

以 Google 的 PageRank 系统为代表的搜索排序系统是给作为检索对象的文档打分的系统。例如，在 Web 检索中，通常会以考量了查询与文档的关联性以及文档的热门度后得出的分数为基准，将检索结果排序后提供给应用程序的用户。搜索排序系统正是用于此目的的、能（机械地）算出文档热门度的系统。

在本节，我们讲解了搜索引擎的一般构成以及各个组件的主要用途。由于在后面的章节还会继续一一讲解各个组件，所以即使现在还未能充分理解也不必担心，可以先从大体上把握搜索引擎的全貌。

1-2　 实现了快速全文搜索的索引结构

本节讲解的是用于快速进行全文搜索的索引结构。在讲解广泛应用于全文搜索的、名为倒排索引的索引结构之前，让我们先来梳理一下全文搜索的方法。

全文搜索的两种方法

全文搜索大致上可以分为两种方法，一种是利用全扫描进行全文搜 索，一种是利用索引进行全文搜索。

∎ 利用全扫描进行全文搜索

第一种方法是从头到尾扫描作为检索对象的文档，以此来搜索要检索的字符串。由于 Unix 的字符串检索命令“grep”也是以同样的方式进行搜索的，所以有时也将这种方法称为“grep 型搜索”。

在利用全扫描进行全文搜索时，虽然不需要事先处理作为检索对象的文档，但问题是文档数越多检索时间就越长。因此，一般认为这种方法只适用于处理少量或暂时性的文档。

另外，在通过对文档进行全扫描来搜索字符串的方法中，有一些高效的算法，例如 KMP 算法和 BM 算法。本书并不会介绍这些算法，若诸位有兴趣的话可以去参考有关算法的教材。

∎ 利用索引进行全文搜索

相对于利用全扫描进行全文搜索的方法，第二种方法，即利用索引的方法，则需要事先为文档建立索引，然后利用索引来搜索要检索的字符串。虽然事先建立索引需要花费时间，但是优点是即使文档的数量增加，检索速度也不会大幅下降。因此，一般认为这种方法更适合处理大量的文档。搜索引擎一般也会采用这种方法。

虽然索引分为很多种，每种的结构都不同，但是以 Google 和 Yahoo! 为代表的大多数搜索引擎采用的都是名为倒排索引的索引结构。也就是说，在全文搜索中倒排索引是一种最常见的索引结构。各位将要通过本书体验其开发过程的搜索引擎采用的也是倒排索引。

下面我们就开始讲解倒排索引的结构。

倒排索引的结构

虽然看似与本节的主题无关，但还是请诸位先回想一下印在教材或专业书等图书后面的索引。在书后的索引中，通常都会写有关键词（单词）和出现了该关键词的页码。由于关键词是按词典顺序排列的，所以查找时无需逐一浏览，只需按照拼音字母的顺序逐渐缩小查找范围，就能轻松地找到关键词。而只要再向这个关键词的旁边看一眼，就能立刻知道该关键词出现在哪一页了。

实际上，倒排索引具有与图书索引完全相同的逻辑结构。下面就让我们以一本书中的文档为例来具体看看倒排索引吧。这本书由以下两页组成，内容分别如下所示。

• 第 1 页（P1）：I like search engines.

• 第 2 页（P2）：I search keywords in Google.

表 1-1 列出了这本书的倒排索引。

表 1-1　示例书籍中的倒排索引

engine	P1
Google	P2
I	P1,P2
in	P2
keyword	P2
like	P1
search	P1, P2

从表 1-1 应该就能看出倒排索引确实和图书的索引拥有相同的结构。看到单词时只要查一下这张表，该单词出现在哪一页就一目了然了。所谓倒排索引就是一张列出了“哪个单词出现在了哪一页”的表格。

倒排索引的构建方法

如何才能构建出倒排索引呢？下面就让我们使用上面的书籍示例，具体地看一看构建倒排索引的步骤吧。首先，要以表格的形式归纳出书中的每一页都使用了哪些单词。归纳出的表格如表 1-2 所示。请注意此时要将英文单词的复数形式还原为单数形式。