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

倒排索引的构建方法

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

在表1-2中，我们以书中使用过的单词为行标题，以页码为列标题。写好行、列标题后，当某页使用了某个单词，就将1填入对应的格子中。例如，第1页（P1）使用了I、like、search、engine几个单词，因此就在对应的几个格子中写入1。对于第2页（P2）也是如此。由于表格是从左向右填写的，所以自然也要从左向右浏览，这样就能读出出现在各页中的单词了。若是从上向下浏览，又会有什么发现呢？这样浏览应该能读出每个单词都出现在哪一页上了。为了便于浏览，我们交换了表1-2的行和列，并将单词按照词典顺序进行了排序，最终结果如表1-3所示。

从表1-3应该就能看出，实际上到了这个阶段，倒排索引就已经大致完成了。剩下的步骤就与制作图书的索引一样了，只要改用精简的表示方式，即只列出“每个单词都出现在了第几页上”，就可以制成表1-1那样的表格了。

像这样，将表示“在哪一页上使用了哪个单词”的表格转换为“哪个单词出现在了哪一页上”的表格，就可以制作出倒排索引了。另外，之所以称这种索引为倒排索引，是由于刚刚进行过的交换表格行、列的操作叫作“倒排”。

倒排索引中的术语

在生成的倒排索引中，我们建立起了页中的单词和页的对应关系。也就是说，我们是把页当成了构建索引的单位。之所以这样做，是因为在翻阅图书时，人们通常是以“页”作为单位的。

那么，对于其他情况又要如何处理呢？例如，对于Web上的HTML文档，我们可以将1个HTML网页作为构建索引的单位。而对于邮件，我们可以将1封邮件作为构建索引的单位。

由此可见，对于每种作为检索对象的数据，构建索引的单位都是不同的。在全文搜索中，将构建索引的单位统称为“文档”（Document），将文档的标识信息称为“文档编号”。文档编号类似图书的页码，用于唯一地标识某个文档。因此，也可以这样说，所谓倒排索引就是“把单词和单词所在文档的文档编号对应起来的表格”。

另外，在倒排索引中，将表示单词和文档编号对应关系的信息称为倒排项（Posting），将各个单词的倒排项的集合称为倒排列表（Postings List）。例如，在刚刚的倒排索引中，单词search的倒排项是P1和P2，倒排列表是P1、P2的集合，记作“P1, P2”。