倒排索引是信息检索系统的重要组成部分之一,被用于维护数十亿文档并对大量查询操作进行响应。随着当前互联网数据量的不断增加,倒排索引的体积也不断攀升。倒排索引压缩算法可以提高信息检索系统的性能,减少索引的空间占用,加快查询处理速度,因而成为了重要的研究对象。模式化编码相比传统的位编码具有解码速度快,压缩效果好的优点,因而被广泛应用于倒排索引压缩中。本文针对模式化编码中的字节对齐编码算法、固定比特编码算法以及字对齐编码算法进行深入研究,主要工作如下:(1)本文对字节对齐编码和固定比特编码的特点进行剖析,并以此为基础提出了 PVU编码压缩算法。算法以字节对齐编码为基础,引入了固定比特编码中的分区思想,使用“模式区-长度区-编码区”的三层存储结构对字节对齐编码中的二层结构加以改进。算法代替以字节为最小存储单位的单一方式,设计了多种最小存储单位供各分区选取最优的压缩模式,从而提高了全局压缩率。针对PVU编码的分区策略进行研究,将编码分区问题转换为图论中的最短路径问题,设计并实现了动态规划求解编码最优分区的方法,并提出了分区优化的OptPVU编码。(2)分析DocID序列经预处理后的取值分布特征,以字对齐编码Simple Family为基础,融合游程编码加以改进,提出了 Simple21编码压缩算法。算法包含21种编码模式,当序列包含大量连续0值时,Simple21编码相比其它Simple Family编码有效减少了占用空间。Simple21编码还通过将模式标识符和压缩编码分割的方式,增加了编码的最大存储长度,扩大了算法的可用范围。(3)本文提出并实现了 PVU编码、分区优化的OptPVU编码以及Simple21编码三种倒排索引压缩算法,并与Golomb编码、Elias-Delta编码,Variable Byte编码、Stream VByte编码、NewPFD编码和Simple9编码进行了对比实验。实验结果表明,Simple21编码在压缩率和解码速度方面均优于其它压缩算法,是实验中综合效果最优的编码方案。PVU编码、OptPVU编码相比字节对齐编码VByte和Stream VByte,在压缩率上取得了明显的优势。与固定比特编码NewPFD相比,PVU编码与NewPFD编码具有相似的压缩效果,而经分区优化的OptPVU编码则取得了比NewPFD编码更好的压缩率和解码速度。