信息检索导论四：索引构建

对于大型的语料库，不能在硬盘采用同样的索引构建算法，需要一个外部排序算法。

BSBI

1. 基本思想

   • 对每一个块都生成倒排记录，并排序，写入硬盘中

   • 然后将这些块合并成一个长的排序好的倒排记录

2. 步骤

   1. 将文档集分割成几个大小相等的部分

   2. 将每个部分的词项 ID—文档 ID 对排序

   3. 将中间产生的临时排序结果存放到磁盘中

   4. 将所有的中间文件合并成最终的索引

3. 图解

   image

4. 问题

   1. 基于块的排序索引算法具有很好的可扩展性，但是需要一种将词项映射成其 ID 的数据结 构。对于大规模的文档集来说，该数据结构会很大以致在内存中难以存放。

分布式索引构建

1. 利用集群(Cluster)中的主控节点指挥索引构建工作。 • 我们认为主控节点是“安全”的。 • 将索引构建过程分解成一组并行的任务。 • 主控计算机从集群中选取一台空闲的机器并将任务 分配给它。

2. 步骤

   1. 将输入文档集分割成n个数据片，每个数据片就是一个文档子集

   2. 分析器

      1. 主节点将一个数据片分配给一台空闲的分析服务器。

      2. 分析器依次读取文档并生成<词项，文档>对

      3. 分析器将这些<词项，文档>对分成j个段

      4. 每一段是按照词项首字母划分的一个区间 • (例如：a-f, g-p, q-z)-这里 j=3

   3. 倒排器

      1. 对于一个词项分区，倒排器收集所有的<词项，文 档>对(也就是“倒排记录”)。

      2. 排序,并写入最终的倒排记录表。

3. 图解

   image

动态索引构建

1. 迄今为止，我们都假设文档集是静态的。 • 但文档集通常不是静态的： • 文档会不断地加入进来 • 文档也会被删除或者修改 • 这就意味着词典和倒排记录表需要修改： • 对于已在词典中的词项更新倒排记录 • 新的词项加入到词典中

2. 方法

   1. 维护一个大的主索引

   2. 新文档信息存储在一个小的辅助索引中

   3. 检索可以同时遍历两个索引并将结果合并

   4. 删除

      1. 文档的删除记录在一个无效位向量(invalidation bit vector)中

      2. 在返回结果前利用它过滤掉已删除文档 •

   5. 定期地，将辅助索引合并到主索引中