信息检索笔记-索引构建
如何构建倒排索引，我们将这个过程叫做“索引构建”。如果我们的文档很多，这样索引就一次性装不下内存，该如何构建。
硬件的限制
我们知道ram读写是随机的操作，只要输入相应的地址单元就能瞬间将数据读出来或者写进去。但是磁盘不行，磁盘必须有一个寻道的过程，外加一个旋转时间。那么只有涉及到磁盘，我们就可以考虑怎么节省I/O操作时间。
【注】操作系统往往以数据块为单位进行读写。因为读一个字节和读一个数据库所耗费的时间可能一样多。
基于块的排序索引方法（BSBI）
通常建立一个倒排索引：我们需要扫描一遍文档得到所有词项-文档ID对；然后分别以词项为主键、文档ID为此次键进行排序；最后我们可能还要统计文档频率和词项频率。对于小文档来说，这一过程在内存中完成是没有问题的，但是对于文档集合较大的，可能在内存中无法进行。
BSBI第一步，在搜集词项的时候将其映射为ID（为什么映射为ID，提高效率）。
BSBI第二步，将文档分成多个大小相同的小文件（block）。
BSBI第三步，将每个小文件对词项ID-文档ID进行排序，并将中间产生的临时排序文件放在磁盘中。
BSBI第四步，将排序好的小文件进行归并排序得到最终的倒排索引。由于内存不足，我们必须使用基于磁盘的外部排序算法（多路归并排序，败者树http://blog.csdn.net/lsjseu/article/details/11708587）。
内存式单遍扫描索引构建（SPIMI）
BSBI构建方法具有很好的扩展性，但是需要一种映射为ID的数据结构，对于大规模文档，该结构可能导致内存放不下。
SPIMI不是用ID存储，而是直接采用词项本身。
SPIMI第一步，CPU内存虽然小，但是还可以构建一些，所以SPIMI现在内存构建索引，直到内存满了。这是，SPIMI将构造好的索引写入磁盘文件中存放。
SPIMI第二步，在第一步最后存放的时候，需要对词典进行排序，意思就是排序后再存放到磁盘。
SPIMI第三步，将多个块合并成最后的倒排索引。
【注】SPIMI与BSBI区别，BSBI是边处理每个小文件，边就排好序。而SPIMI处理完了每个小文件，然后对小文件整体排序。
分布式构建方法
实际当中，文件都非常大，一台机子可能处理不过来。这是可利用分布式系统来构建索引。这里我们需要用到MapReduce构架。MapReduce将一个庞大的处理任务分成子任务，然后分发到各个计算节点进行计算，计算完成后归并得到最后的结果。
各个子任务并不预先分配到某个节点，而是在运行过程中，由主控节点动态分配。这样的话，算得快的节点，可以分配任务多一点（因为很快就计算完了嘛，可以重新分配心的任务了），慢点的节点可能相对较少一点。或者说如果某台机子如果算不动了，可以把它的任务挪到其他节点上去完成。
动态构建索引方法
上面的方法都是静态的构建索引，就是说我的文档不变，但是有可能存在这样一种情况，我的文档在不断变化。那么，此时我们就需要动态构建索引。
此时，我们可以构建两个索引，一个大的主索引，一个小的辅助索引存在内存中。检索时，我们就可以同时遍历这两个索引，将两个索引结果进行归并操作。
同时，如果我们的辅助索引很大的时候，我们就它合并到主索引中去。
