主题：[推荐]《An Introduction to Information Retrieval》参考译文之五——索引（Index）

4 索引构造
4．1 硬件基础
信息检索系统的很多功能设计都与它所运行的计算机硬件条件密切相关。

按照硬件条件，我们可以得出一些基本结论：
1）对内存的访问速度快于对外存的访问速度。读取内存一个字节只需几个时钟周期（约5 × 10-9秒），但是读取外存一个字节却需要更长的时间（约2 × 10-8秒）。所以，一般情况下，我们应当尽可能的在内存存储所有数据，特别对于那些需要频繁访问的数据，它们相应的存储空间被称为缓存（cache）.
2）当进行外存读写时，磁盘磁头定位到相关数据存储地方也需要一定的时间，被称为寻道时间（seek time），对于典型的硬盘而言，平均为5毫秒。在寻道期间，没法传输任何数据。为了使得创度速度最大化，需要被连续读取的数据一般要连续存储在外存上。按照上述硬件标准，假设要传输外存的10M数据到内存，如果这些数据都连续存储在一个数据单元（chunk）中，则需要时间要少于0.2秒，但是如果这些数据被分开存放在不连续的100个数据单元中，由于需要频繁移动磁头近100次，所以需要的时间可达到0.2＋100×（5×10－3）＝0.7秒。
3）操作系统一般以数据块（block）为单位来读写外存，所以读取1个字节和读取整个数据块所花费的时间差不多是一样的。数据块的大小一般为8KB，16KB，32KB和64KB等。通常把即将读写近外存的内存数据单元称为数据缓冲（buffer）。
4）外存和内存之间的数据传输一般是利用系统总线来进行的，而非处理器。这就意味着在进行IO操作时处理器完全可以用于对其他数据的处理工作。有效利用这种特征可以加快读写外存数据的速度，如对这些数据启用压缩。在使用一种高效解压算法的时候，读取和解压这些数据的总时间要少于读取未压缩数据的总时间。
5）信息检索系统所在的服务器一般都有几个GB大小的内存。可用的外存空间更高据个级别。

4．2 基于分块排序的索引（Blocked sort-based indexing）
前文已经说明构建无词语位置信息索引的方法，该方法首先遍历全部文档，构造全部的词语文档对（term－docID），然后再以词语为主键、文档号为辅键，对词语文档对进行排序，最后利用文档号对每个词语构建相关的标记序列，同时还要计算词语频率和文档频率等统计指标值。对于小规模的数据而言，这些操作都可以在内存中直接进行。但是对于大规模的数据而言，就必须要使用外存。
为了使得构建索引更为高效，需要使用词语号（termID）来作为区分不同词语的唯一标记符，这个词语号可以在处理文档集合时即时生成，或者采用两阶段做法，先生成词语号，然后构建相关索引。
本章所讲述的内容主要基于路透社的Reuters-RCV1文档集合，大约有1GB的数据量，它主要包含路透社新闻专线从1996年8月20日到1997年8月19日所收集的近80万篇文档。典型的文档含有包括图片在内的各种信息，不过本文主要关注于其中的文本信息。这个文档集合所涉及的内容包含各方面的国际主题，如政治、商业、体育和科技等。
Reuters-RCV1文档集合大概含有1亿个标识（token），假设使用4个字节来表达每个词语号和文档号的值对，则所有值对的大小可达0.8GB。事实上，常见信息检索系统所涉及的相关值对集合可达更高级别的规模，对它的排序等操作显然会让一些大型计算机也不堪重负。虽然可以使用压缩技术来减少中间文件的大小，但是相应的标记文件（postings file）即便是压缩后也远远超过常见的内存大小。
既然内存有限，所以就有必要使用外部排序算法，也就是说要使用外存资源。为了使得运算速度保持在合理的范围内，这些算法必须要设法减少在排序期间随机寻道的次数。一种常见的算法就是基于分块排序的索引（Blocked sort-based indexing，BSBI）。该方法主要包含一下步骤：
1）将全部文档集合划分为若干相同大小的块，这个块的大小一般和内存正好相同，。
2）在内存中对每个块的所有词语号和文档号构成的值对进行排序。
3）将这些排好序的中间值对序列先行存储到外存中。
4）合并所有的中间值对序列，生成最终的完整索引。
这个算法的时间复杂度为O（T×logT），其中消耗时间最多的是对块的排序过程，T是所要排序的数量上限，也就是所有值对的数量总和。这些时间是基本稳定的，实际索引的时间往往更易于解析文档和最终的合并过程所影响。
虽然Reuters-RCV1文档集合较信息检索系统的实际数据可能较小，但是这种索引的方法却是适应海量数据存储要求的。

4．3 一遍式内存排序（Single-pass in-memory indexing）
上述索引方法虽然具有较好的可缩放性，但是它要求一个数据结构存储所有的词语和映射的词语号。对于大规模的文档集合而言，这个数据结构往往无法存储在内存中。相对而言，一遍式内存排序（Single-pass in-memory indexing，SPIMI）方法既有较高的可缩放性，同时无需使用词语号，直接将每个字典数据块信息写到外存，在开始新的字典数据块的生成。所以，该方法可以索引任何大小规模的文档集合，只要外存空间足够。
该方法首先解析文档，得到词语文档号的值对（term－docID pairs）序列，SPIMI方法会反复不断的对整个序列进行操作，直至处理完全部集合。
词语文档号的值对是一个接着一个被处理。当这个词语是首次出现，则将其添加进字典中，可能会采用哈希的方式存储，并生成新的标记列表。如果不是首次出现，则返回已有词语对应的标记列表。
这个方法与前面的方法有一个明显的区别，那就是该方法直接将标记添加到标记列表中。该方法不去首先获取全部的词语文档号的值对并对其排序，而把标记列表做成动态形式，也就是说，它的大小是可以动态调整的，并可以直接收集词语的标记信息。这样做有两个优点：一是由于没有额外的排序，所以速度很快；二是直接利用词语来得到相应的标记信息，无需使用词语号。所以该方法一次处理的数据块所包含的信息更多，相应的索引效率也就更高。
由于一开始不可能知道一个词语所对应的标记列表有多长，所以首次分配的空间不会很大，一旦塞满就扩展成原先的二倍。因此，这些标记会存在很多的空间浪费，在一定程度上抵消了省略存储词语号数据结构所节省的空间。但是，在整体上看，它所消耗的内存总量还是低于传统的BSBI方法。
一旦内存塞满，将需要将已经得到的字典及其标记信息全部写回外存。在这个过程中，需要按照词语进行排序，以便于以后的合并操作。否则，以后的合并操作就不可能一次遍历即可做完。
每一次调用SPIMI方法都会向外存写回一个数据块，所以SPIMI方法的最后一步就是合并所有的数据块形成最终的倒排索引。
这个方法除了能够即时生成标记结构和消除过多排序过程所带来的性能损耗，该方法还能辅以压缩处理，即压缩存储在外存的字典和相应标记信息。

4．4 分布式索引（Distributed indexing）
文档集合可能很大，以至于一台机器无法处理，特别对于Web环境的网页信息处理。这时可以使用计算机群集（computer cluster）来构造分布式的索引。这种索引或者根据词语或者根据文档，被分派到多台计算机上，大部分搜索引擎都使用基于文档的划分方法。
比较常见的分布式索引可以采用很多现成的分布式处理框架，如Google的MapReduce应用框架，这是一个通用型的分布式计算框架。它的设计目标就是实现计算机的群集运算，这些计算机都是一些廉价的普通计算机，在工作期间，任何一台计算机都有可能失败。所以为了实现整体系统的鲁棒性，需要一个主节点（master node）来统一协调工作任务的分配，特别是在某个工作节点失败时可以重新分配任务。

此主题相关图片如下：

上图演示了它的基本工作过程。首先需要对任务进行分组，每组任务的大小要平均相同，不能太大，并且整体计算性能不低，所以分组的个数也不能太多。通常对于分布式索引而言，16MB或者64MB是比较合理的选择。这些不同的分组并非预先分配好，而是在运行期间动态分配，基本原则就是：只有一个节点结束一个分组任务后，才可以接受新的任务。如果一个节点失败或者因为硬件原因变得缓慢，主节点可以将这个节点原先进行的任务重新分配给其他节点继续运行。
MapReduce方法通常根据名值对（key-value pairs）为单位来对任务进行指派。对于索引而言，这个名值对就是词语号和文档号的值对（termID,docID）。值得注意的是，这里需要解决如何将词语映射为词语号的问题。常见的处理方式也是分布式的，即将常见词语及其词语号拷贝至每个节点，而对非常见词语则直接使用词语本身进行处理。随后处理完后，再统一处理这些非常见词语的编号。
在映射（map）阶段，MapReduce方法将输入的数据由解析器（parser）来分割成一组名值对，这些工作在BSBI和SPIMI索引中也是必须的。每个解析器都把处理完的数据暂时存放在本地的段文件中。段文件的主要功能就是要把同一个词语相关的所有值存储在一个地方，不同的段文件分别存放不同范围的词语内容。事实上，这些段文件的划分依据不一定是一些连续的词语，也可能是按照哈希之类的方法映射成不同的段文件。从总体上看，每个相同的词语就对应多个不同解析器上的段文件。
在约简（reduce）阶段，对某个名（即词语号）的相关值（文档号）进行收集，通过转换器（inverter）生成一个列表。主节点可以对每个词语分区指派一个转换器。所以，相同地位的段文件在总量上要能够适应一个节点的处理能力。最后，对所有的词语进行排序生成最终的索引。
解析器和转换器不一定非要是不同的机器。主节点自主的决定空闲机器并分派任务。事实上，除了索引工作外，甚至还有很多其他任务也在这些群集计算机上同时运行，所以在一个节点充当解析器和转换器的中间时间内，它极有可能进行诸如爬虫遍历等其他工作。
为了尽可能减少转换器在处理数据前的写入数据次数，每个解析器都将段文件信息保存在自己的本地存储器上。在约简阶段，主节点通知转换器段文件的所在位置。由于每个段文件只需被一个转换器一次读取，所以它所包含的词语信息都是这个转换器所需要处理的词语。这样的设计显然能够极大的减少网络通信流量。
在Google搜索引擎系统中，基于MapReduce的分布式处理正是上述模样。这些分布式处理工作不仅包含索引，而且还包含其他任务。即便是索引任务，除了这些词语标记信息的生成外，还要包含利用这些信息继续生成按照文档分区的索引信息。

4．5 动态索引
虽然这里所说的文档集合都是一些诸如莎士比亚选集之类的静态文档，但是信息检索系统中的文档集合通常会被更新，这就意味着新的词项会被添加到字典中，标记列表也会添加相应的项目。
简单的处理方法就是周期性的重建索引，当然这对于那些文档更新较少而且可以允许查询工作暂停的情况是可行的。但是，如果资源允许的话，完全可以在继续使用旧索引的情况下，同步构建新的索引。所以，对于常见的信息检索系统而言，更为合理的做法就是维护两份索引，一个是用于正常检索的主索引，另一个是用于存储新插入文档索引信息的辅助索引。辅助索引通常被存储在内存中，搜索活动会在两个索引上同时展开，并被合并。其中的删除信息通常使用失效位向量来表示，所以在返回结果时通过此失效位向量过滤掉被删除的文档信息。对于更新而言，可以理解为删除后再插入。
一旦辅助索引达到一定规模，我们就可以将其合并到主索引中，其中的资源花费依赖于索引文件的存储方式。如果我们将每个标记列表项单独存储为一个文件，合并工作就是直接将每个主索引中的标记列表项文件扩展，添加辅助索引中新的标记列表项信息。而且使用辅助索引还能减少每次添加文档所产生的磁盘搜索工作，如果Mavg为每篇文档的平均词汇数量，则不使用辅助索引就意味着添加一个文档信息就要平均搜索磁盘Mavg次。而使用辅助索引后，只有到最终合并的时候才产生一定运算开销，而在平时添加文档时只需直接在辅助索引中追加信息即可，节省了搜索磁盘的时间。
不过，每一个标记列表项对应一个文件其实并不可行，因为很多文件系统都不能有效处理大规模数量的文件。所以，在更多的情况下，我们不得不采用将很多标记列表项存储在同一个索引文件的方法。当然，为了折中可以考虑分段合并这些标记列表项。比较常见的方法就是对数合并算法（LOGARITHMIC MERGING）。
不过，应当看出拥有多个索引文件会在一定程度上增加系统的复杂度，任何操作都要进行多个索引的遍历，所以很多搜索引擎系统为了简化问题和提高整体性能，往往采用周期性重做索引的方式来构建新的索引，一旦新索引构建成功，就删除原有的旧索引。