首页 -> 1.2 构建反向索引的初次尝试
要在检索期间获得索引带来的速度提升，我们必须提前构建索引。主要的步骤是：
-
收集需要被索引的文档：
Friends,Romans, countrymen. So let it be with Caesar ... -
把文本分为一个一个记号，把每个文档变成记号的列表：
Friends Romans countrymen So ...
-
进行语言学的预处理，产生规范化的记号的列表，也就是要被索引的词：
friend roman countrymen so ...
- 通过创建包含字典和记录集的反向索引，索引每个词出现过的文档。
我们将在2.2节定义并讨论这个处理流程的前端，1-3步，在那之前，你可以把记号和规范化的记号大致理解为单词。这里，我们假设前三步已经完成，我们尝试构建一个基本的反向索引。
针对文档集，我们假定每个文档都有一个唯一的序列号，叫做文档标识符（docID）。索引构建过程中，我们可以连续地给每个第一次出现的文档分配一个整数。索引的输入是每个文档的一个规范化的记号表，我们也可以认为这是词和docID对的一个列表，如表1.4。索引的核心步骤是对这个列表排序，这样词是按照字母顺序排列的，展现起来就像表1.4中间一列那样。同一词在同一文档的多次出现会被合并。同一词的多个实例被分组，结果被分为字典和记录集，如图1.4右边一列显示。因为词通常出现在大量文档中，这种数据组织方式降低了索引的存储需求。字典还记录一些统计信息，例如包含具体每个词的文档数目（文档频率，同时也是每个记录集的长度）。这个信息不是基础的布尔搜索引擎所必须的，但是它可以提高查询期间搜索引擎的效率，而且是用于许多排名检索模型的统计信息。记录由docID排序。这就是高效查询处理的基础。这种反向索引数据结构本质上是支持文本搜索的最高效的结构。
在索引结果中，我们付出了存储字典和记录列表两者的存储代价。后者更大些，但是字典通常保存在内存，记录列表通常保存在硬盘，所以两者的尺寸都很重要，第5章，我们将考察它们的存储如何优化，如何高效访问。记录表应该使用什么数据结构？定长数组一定是浪费的，因为有些词出现在很多文档，有些出现的比较少。对于内存内记录表，两个好的选项是单链表或者变长数组。单链表需要额外的指针，文档插入记录表的开销非常小（其次是更新，例如重新爬行web更新文档），而且天生容易扩展到更高级的索引策略，例如忽略表（2.3节）。变长数组在空间需求上略胜一筹，因为避免了指针浪费空间，时间需求方面也占优，因为变长数组使用连续的内存，提高了在带有内存高速缓冲的现代处理器上的速度。额外的指针实践中常编码为表中偏移位置。如果更新不是很频繁，变长数组更近凑更快速。我们还可以为每个词使用链表和定长数组的混合模式。当记录列表保存在硬盘时，它们保存（也许压缩）为连续的记录不需要明确的指针（如图1.3），这样可以最小化记录列表的尺寸以及读取一个记录列表到内存所需的硬盘寻道次数。