自制搜索引擎——1-7　构建倒排索引

前面我们已经了解了由索引管理器管理的倒排索引的结构以及在索引检索器上进行检索处理的流程。下面，就让我们再来看一下如何在索引构建器上构建倒排索引吧。 使用内存构建倒排索引 生成了与文档编号对应的单词表后对该表进行倒排，在1-2 节我们通过这种方法生成了倒排索引。若让计算机来处理的话也是如此，先在内存上生成与文档编号对应的单词表（二维数组），然后用相同的方法倒排该表，就可以构建出倒排索引了。但是，由于大多数情况下倒排索引都是非常稀疏的表，因此这种构建方法可能会消耗大量的内存。 于是就有了用链表实现倒排列表这一优化方法。相比之下，该方法只需少量的内存就可以构建出倒排索引。 使用二级存储构建倒排索引 在今天的硬件环境下不乏装配有大量内存的计算机，尽管如此，在很多情况下还是需要处理超过实际内存量的大规模文档。遇到这种情况时，可以利用二级存储来构建索引。作为利用二级存储构建索引的代表性方法，本书将会介绍“基于排序的构建方法”和“基于合并的构建方法”。为了使文章简明扼要，下面只介绍如何构建文档级别的倒排文件，但是其中步骤也适用于构建单词级别的倒排文件。 基于排序的索引构建法 基于排序的索引构建法是一种将由单词和倒排项组成的二元组写入二级存储，并以单词的词典 顺序对这些二元组排序，以此来构建倒排索引中的倒排列表的方法。具体的构建程序如代码清单1-4 的伪代码所示。 首先，对各文档中构成该文档的每个单词都建立一条形如“单词、文档编号、单词在文档中的出现次数（TF）”的记录，然后将该记录写入到二级存储上的文件的末尾（①）。 接下来，将文件中的各条记录优先按照单词的升序排列，单词字段相同的记录需再按照文档编号的升序排列（②）①。 最后，从第一行开始逐行地读取排序后的文件，取出每个单词的文档编号的列表，并用这些列表构建出各个单词的倒排列表（③）。此外，压缩倒排列表的操作也是在④的步骤中进行。 代码清单1-4　基于排序的索引构建法 图1-7 是基于排序的索引构建处理的示意图。 －－－－－——— A　这时的排序方法通常会选择合并排序，例如像下面这样做：首先以块的整数倍 为单位将多条记录加载到内存中，然后对这些记录进行快速排序并将排序后的记录导出到文件中，最后利用多路合并排序将多个导出的文件合并在一起。 ———————— 图 1-7　基于排序的索引构建法 基于合并的索引构建法 基于合并的索引构建法是一种先在内存上构建出倒排索引的片段，然后将这些片段导出到二级存储，最后将导出的多个倒排索引片段合并在一起，以此来构建最终的倒排索引的方法。具体的构建程序如代码清单1-5 的伪代码所示。 代码清单1-5　基于合并的索引构建法 首先，在内存上构建出以单词为键，以倒排列表为值的映射表（Mapping），即由部分数据构成的倒排索引的片段（①）。 每当遇到文档中的单词不在映射表中时，都要将该单词加入到映射表中（②）。 当映射表的大小（事先已设定好）达到内存大小的上限时，就将该映射表导出到文件中（③）① 。 像这样反复处理，直到处理完所有的文档，最后利用多路合并将导出的多个文件合并在一起，构建出最终的倒排索引（④）。另外，压缩倒排列表的操作也是在④的步骤中进行。 基于归并的索引构建处理的示意图如图1-8 所示。 图1-8　基于合并的索引构建法 虽然本节省略了对相关算法的详细分析，但是一般认为基于合并的索引构建法拥有更高的效率。这是由于相对于基于合并的方法，基于排序的方法要在二级存储上进行排序，所以读写的总量往往会增多。 －－－———————— A　在这段伪代码中，由于是将哈希表用作词典，所以要在导出时进行排序。然而若使用像树那样的、带有顺序的数据结构来管理词典的话，就可以省略排序的步骤了。 ——————————— 静态索引构建和动态索引构建 之前讲解过的索引构建方法都是对输入数据进行批量构建处理。也就是说，在构建处理完成之 后索引才能用于检索。在信息检索领域中，这样的构建方法被称为“静态构建方法”（Offline Index Construction）。静态构建方法多用于文档集合较稳定，或是即使文档集合发生了变化，在变化同步到索引之前还有一定时间等场景。 与此相对，还有一种“动态构建方法”（Online Index Construction/Dynamic Indexing）。这种方法不但可以使索引结构时刻处于可供检索的状态，还可以一边实时更新索引，一边构建索引。这种方法多用于信息的时效性非常重要的文档，例如Web 上的新闻或博客中的文章等。在书后的附录部分中我们将会详细地讲解动态构建方法。