论文部分内容阅读
数据集的检索通常使用倒排索引模型进行检索,可以在海量的文本数据获取信息。基于数据集构建倒排索引文件通常十分庞大,压缩倒排索引可以减少空间使用,在相同的内存中驻留更多的信息,加快检索的速度。而现有的倒排索引压缩算法在空间利用、解压性能存在局限性,因此,倒排索引的高效压缩与解压成为一个重要的课题。倒排索引的压缩分为单词压缩和倒排链表的压缩,倒排链表的压缩主要将单词在文档中出现的docID、frequency和positions等信息进行压缩,而这些信息的压缩通常为整数压缩。本文提出并实现了RFMEGC压缩算法对倒排索引中docID的压缩和解压。该算法在RFEGC算法的基础上,在实现docID的压缩编码时,减少除法的计算步骤,从而提高压缩编码速度,并降低倒排索引的文件大小。本文提出并且实现了RLERFEGC压缩算法对倒排索引中docID的压缩和解压算法。该算法在RFEGC压缩算法的基础上,将连续的整数1的序列替换为该序列的长度,然后将该长度使用RFEGC压缩算法进行压缩,最后实现docID的压缩,降低docID压缩文件的整体空间。本文提出并实现了DPRFEGC压缩算法对倒排索引中docID的压缩和解压算法。BRFEGC压缩算法将docID序列分为指定长度的整数序列,然后对整数序列使用RFEGC压缩算法进行压缩,使用定长的整数序列进行压缩,对不同的整数序列,倒排索引的压缩效果会明显不同。DPRFEGC压缩算法使用动态规划,计算整数序列的最优分块方案,根据分块方案使用RFEGC压缩算法对整数序列进行压缩。DPRFEGC压缩算法对不同的整数序列使用不同参数,提高数据的访问效率,加快数据解压速度。实验结果表明,RFMEGC压缩算法在倒排索引docID压缩过程中,压缩效果较好；RLERFEGC压缩算法在倒排索引frequency的压缩中,压缩效果较好；DPRFEGC压缩算法比其他的压缩算法解压速度快。