信息检索之索引构建

1、主要内容：     ①、与索引构建相关的计算机硬件的基本知识；     ②、面向静态文档记得高效单击索引算法---基于块的排序索引构建算法；     ③、内存是单遍扫描索引构建算法；     ④、分布式索引构建；     ⑤、动态索引构建（在很多文档机会动态变化的情况下）；     ⑥、安全性和排序式检索中的索引问题； 2、硬件基础：     ①、尽可能地将访问频繁的数据放入内存中，特别是那些访问频繁地数据。这种将频繁访问的磁盘数据放入内存的技术成为高速缓存。     ②、进行磁盘读写时，磁头移动到数据所在的磁道需要一段时间，该时间成为寻道时间，一般为5ms左右。为使数据的传输效率达到最大，连续读取的数据块也应该在磁盘上连续存放。     ③、操作系统往往以数据块为单位进行读写。因此，从磁盘上读取一个字节和读取一个数据块所耗费的时间可能一样多。将内存中保存读写快的那块区域称为缓冲区。     ④、IR系统的服务器的内存往往有数G甚至是十几G的字节，磁盘空间容量大小一般为百G。 3、基于块的排序索引方法：     ①、由于内存不足，必须使用就有磁盘的外部排序算法。核心思想是：在排序是尽量减少磁盘随即寻到的次数。     ②、总体思路：现将数据分割成多块，然后分而治之，最终再合并。     ③、BSBI算法如下：

    第一步：将文档集分割成几个大小相等的部分；     第二步：将每个部分的词项ID--文档ID对在内存中排序；     第三步：将中间产生的临时排序结果放在磁盘中；     第四步：将所有的中间文件合并成最终的索引；（按照继续微笑lsj的建议，使用多路归并排序）

算法步骤解释：①、首先是将此项用ID来代替，得到文档ID--文档ID对，并在内存中处理，直到累积至放满一个固定大小的块空间为止；②、选择合适的块大小使之能够加载入内存进行快速排序；③、排序后的块转换成倒排索引写入磁盘；④、将产生的多个块索引同时合并成一个索引文件。合并时，同时打开所有块对应的文件，内存中维护了为若干个块准备的读缓冲区和一个为最终合并索引准备的写缓冲区。每次迭代中，利用优先级队列（即堆结构）或者类似的数据结构选择最小的未处理词项 ID 进行处理。读入该词项的倒排记录表并合并，合并结果写回磁盘中。 

BSBI的问题：

前提假设是词典可以在内存放下，并需要一种将词项映射成其 ID 的数据结构。对于大规模的文档集来说，该数据结构会很大以致在内存中难以存放。实际上，倒排记录表可以直接采用term,docID 方式而不是termID,docID方式，但是此时中间文件将会变得很大。  

4、内存是单片扫描索引构建方法：

    解决问题：将此项映射成其ID的数据结构，对于大规模的文档集来说，该数据结构会很大以至于在内存中难以存放。

        SPIMI算法：

1、算法逐一处理每个词项—文档 ID 对；
2、如果词项是第一次出现，那么将之加入词典（最好通过哈希表来实现，在吴军博士的《数学之美》中提到过这，P96：使用哈希表判断网页的URL是否已经在表中，其原理和这类似） ，同时建立一个新的倒排记录表；
3、如果该词项不是第一次出现则直接在倒排记录表中增加一项；
4、由于倒排记录表是动态增长的，算法事先并不知道每个词项的倒排记录表大小，故一开始会分配一个较小的倒排记录表空间，每次当该空间放满的时候，就会申请加倍的空间；
5、基于上述步骤可以对每个块生成一个完整的倒排索引，为加快最后的合并过程，要对词项进行排序操作，然后写入磁盘形成单块索引；

6、这些独立的索引文件最后合并一个大索引文件。

与BSBI算法的比较：

SPIMI是直接在倒排记录表中增加一项。和那种一开始就整理出所有的词项 ID—文档 ID 并对它们进行排序的做法 （这正好是 BSBI中的做法）不同，由于不需要排序操作，因此处理的速度更快；
SPIMI 使用词项而不是其ID，它将每个块的词典写入磁盘，对于下一个块则重新采用新的词典。只要硬盘空间足够大，SPIMI就能够索引任何大小的文档集。 由于词项的 ID 不需要保存。这样，每次单独的处理的块大小可以非常大，整个倒排索引的构建过程也因此会非常高效。由于事先并不知道每个词项的倒排记录表大小，算法一开始 会分配一个较小的倒排记录表空间，每次当该空间放满的时候，就会申请加倍的空间 。这意味着一些空间被浪费，也正好抵消了不用保存词项 ID所省下的空间。然而，总体来说，在 SPIMI 中对块建立索引所需的内存空间仍然比 BSBI 少。

新的问题：实际当中，文档集通常都很大，在单台计算机上很难高效地构建索引。对Web构建规模合理的索引常常需要大规模的计算机集群。因此，Web搜索引擎通常使用下面的分布式索引构建算法。

5、分布式索引构建算法：

①、分布式索引构建核心思想：

维持一台主机(Master)来指挥索引构建任务‐这台主机被认为是安全的

把整个任务分成易分配的子任务块，集群中的主控节点（master node）负责处理任务在工作节点上的分配和重分配。

图4-5

r个分析器（相当于每台机器），r个分区文件，3个段。

②、实现步骤说明：

Map阶段：

主 控节点将一个数据片分配给一台空闲的分析器（Parser），分析器一次读一篇文档然后输出(term,docID)对，然后分析器将这些 (term,docID)对又分成j个词项分区，每个分区按照词项首字母进行划分。E.g., a‐f, g‐p, q‐z (这里j = 3)

Reduce阶段：

主控节点将一个词项分区分配给一台空闲的倒排器(Inverter)，倒排器收集对应某一词项分区(e.g., a-f分区)所有的(term,docID) 对(即倒排记录表)，排序并写进倒排记录表。

基于MapReduce的索引构建示图（Casesar简写成 C，conquered 简写成 c’ed）

图4-6

主控节点将每个词项分区分配给一个不同的倒排器。每个此项分区（对应r个分区文件，其中每个分区文件存放在一个分析器上）有一个倒排器来完成。最终每个键对应的所有值要进行排序并写道最终的排序倒排记录表中。

为了减少在倒排器对数据进行reduce之前的写时间，每个分析器将其分区文件写到本地磁盘。在reduce阶段，主控节点会通知倒排器与之相关的分区文件的位置（例如，词项a~f分区对应的r个分区文件）。在每个分析器上，由于与某个特定倒排器相关的数据已经被分析器写入到一个单独的分区文件中，所以每个分区文件近需要一次顺序读取过程。这种设置方法可以是索引时所需的网络通信开销最小。

新的问题：以上我们都假设文档集是静态的，这对于很少甚至永远不会改变的文档集来说没有任何问题。然而，大部分文档集会随文档的增加、删除或更新而不断改变。这也意味着需要将新的词项加入词典，并对已有词项的倒排记录表进行更新。所以便有了下面的方法：动态索引构建。

6、动态索引构建

简单办法：

最简单的索引更新办法就是周期性地对文档集从头开始进行索引重构。如果随时间的推移文档更新的次数不是很多，并且能够接受对新文档检索的一定延迟，再加上如果有足够的资源能够支持在建立新索引的同时让旧索引继续工作， 那么周期性索引重构不失为一种较好的选择。

引入辅助索引的解决办法：

同 时保持两个索引：一个是大的主索引，另一个是小的用于存储新文档信息的辅助索引（auxiliary index） ，后者保存在内存中。检索时可以同时遍历两个索引并将结果合并。每当辅助索引变得很大时，就将它合并到主索引中。文档的删除操作记录在一个无效位向量 （invalidation bit vector）中，在返回结果之前可以利用它过滤掉已删除文档。某篇文档的更新通过先删除后重新插入来实现。

主辅索引合并分析：

主辅索引的构建索引办法会导致合并过于频繁（内存索引变大时就得进行合并操作），合并时如果正好在搜索，那么搜索的性能将很低理 想情况下，如果将每个词项的倒排记录表都单独存成一个文件，那么要合并主索引和辅助索引，只需要将辅助索引的倒排记录表扩展到主索引对应的倒排记录表即可 完成。遗憾的是，由于绝大多数文件系统不能对大数目的文件进行高效处理，因此将每个倒排记录表存成一个文件这种方式实际是不可行的。另一种简单的方法是将 索引存到一个大文件中，也就说将所有倒排记录表存到一起。现实当中常常介于上述两者之间(例如：将大的倒排记录表分割成多个独立的文件，将多个小倒排记录表存放在一个文件当中)

对数索引合并(lucene最早应用)

同 以往一样，内存中的辅助索引（我们称之为Z0）最多能容纳n个倒排记录。当达到上限n时， Z0中的n个倒排记录会移到一个建立在磁盘上的新索引I0中。 当Z0下一次放满时，它会和I0合并，并建立一个大小为 2×n的索引Z1。Z1可以以I1的方式存储（如果I1不存在）或者和I1合并成Z2（如果I1已存在）。上述过程可以持续下去。对搜索请求进行处理时， 我们会利用内存的索引Z0和现有的磁盘上的有效索引Ii进行处理，并将结果合并。看到这里，对二项式堆结构比较熟悉的读者会发现它与刚才提到的对数合并下 的倒排索引结构之间具有很高的相似性。