索引构建
索引构建
索引器
索引器需要原始文本，但是文档可能采用多种编码格式，索引器对中间文件和最后的索引文件进行压缩或者解压缩，在web搜索中，文档往往并不是来自本地，必须要通过网络采集才能得到。
一个2007年度的典型计算机系统的参数如下表所示
与IR系统设计相关的硬件参数：
由于内存不足，必须采用基于磁盘的外部排序算法。为了达到可以接受的速度，对该算法的核心思想要求是： 在排序时尽量减少磁盘随机寻道的次数 。
基于块的排序索引算法（BSBI， blocked sort-based indexing algorithm）
基于快的排序索引算法将每个块的倒排索引存储文件 f1 ,...fn 中，最后合并成文件fmerged。
具体过程可以细化为：
基于块的倒排索引合并过程：将两个块从磁盘读入内存，然后在内存中进行合并，最后写回磁盘。
时间复杂度 ：O（T logT），因为具有最高时间复杂度的步骤是排序，T是排序的项目数量上限（例如termID-docID对的数量）。但实际的索引时间通常由解析文档（ParseNextBlock）和完成最终合并（MergeBlocks）所花费的时间决定的。
优缺点 ：该算法有很好的扩展性，但是需要一种将词项映射成其ID的数据结构，对于大规模的文档集合来说，该数据结构会很大，在内存中难以存放。
SPIMI 算法的流程如图所示,其中省略了文档分析以及将文档转换成词项—文档 ID 流(算 法中称为 token_stream)的过程。反复调用 SPIMI-INVERT 函数直到将全部的文档集处理完为止。
BSBI 和 SPIMI 的区别
在实际当中，文档集通常都很大，在单台计算机上很难高效地构建索引，因此Web搜索引擎通常使用分布式索引构建，索引结果也是分布式的，往往按照词项或者文档进行分片后分布在多台计算机上。
索引更新方法 ：周期性地对文档集合从头开始进行索引重构。
实时性 ：要实时检索到新文档，可以采用辅助索引。辅助索引存储新文档信息，记录在内存中，检索时同时遍历两个索引。文档的删除记录保存在一个无效位向量中。
引入辅助索引的解决办法 ：
主辅索引合并分析：
对数合并
彩驰科技
2024-11-22 广告
