论文部分内容阅读
由于信息科技的飞速发展,数据爆炸式增长,形成了人类史上前所未有的海量文本信息。面对海量的文本信息,倒排索引作为一种有效的全文索引技术,能够快速准确地帮助人们查找所需要的信息。但是海量的文本信息形成了规模庞大的倒排索引,其规模最大可达原文的300%,所以倒排索引的压缩是十分必要的。倒排索引生成算法的一般流程是docID分配、Posting Lists生成和Posting Lists压缩。常见的标识符分配算法有基于URL排序的标识符分配算法和基于交叉的标识符重分配算法；常见的Posting Lists压缩算法有Unary Code、Variable Byte Code、 Simple-9和PForDelta等。本文提出了基于TermID序列排序的标识符重分配算法。通过遍历已创建的倒排索引生成正排表,规定正排表内termID序列的排序规则,并按照该规则对正排表中的文档记录进行排序得到新顺序的文档序列,然后根据新的文档顺序依次为文档分配新标识符,重新创建倒排索引。本文实现了基于URL排序的标识符分配算法(URL)、基于交叉的标识符重分配算法(IBDA)、基于TermID序列排序的标识符重分配算法(SBDRA)等标识符分配算法和VByte、Simple-9、Simple-16、New PFD、Opt PFD、PForDelta等posting lists压缩算法。使用Wikipedia网站文档数据集,实现了18组混合交叉实验。实验结果表明,对于大规模的文档数据集,本文提出的基于TermID序列排序的标识符重分配算法性能优于基于URL排序的标识符分配算法和基于交叉的标识符重分配算法,其生成的倒排索引具有更好的整体压缩效果。