基于模式化编码的倒排索引压缩算法研究

发布时间：2023-08-18 18:07

　　倒排索引是信息检索系统的重要组成部分之一,被用于维护数十亿文档并对大量查询操作进行响应。随着当前互联网数据量的不断增加,倒排索引的体积也不断攀升。倒排索引压缩算法可以提高信息检索系统的性能,减少索引的空间占用,加快查询处理速度,因而成为了重要的研究对象。模式化编码相比传统的位编码具有解码速度快,压缩效果好的优点,因而被广泛应用于倒排索引压缩中。本文针对模式化编码中的字节对齐编码算法、固定比特编码算法以及字对齐编码算法进行深入研究,主要工作如下:(1)本文对字节对齐编码和固定比特编码的特点进行剖析,并以此为基础提出了 PVU编码压缩算法。算法以字节对齐编码为基础,引入了固定比特编码中的分区思想,使用“模式区-长度区-编码区”的三层存储结构对字节对齐编码中的二层结构加以改进。算法代替以字节为最小存储单位的单一方式,设计了多种最小存储单位供各分区选取最优的压缩模式,从而提高了全局压缩率。针对PVU编码的分区策略进行研究,将编码分区问题转换为图论中的最短路径问题,设计并实现了动态规划求解编码最优分区的方法,并提出了分区优化的OptPVU编码。(2)分析DocID序列经预处理后的取值分布特征,以...

【文章页数】：71 页

【学位级别】：硕士

【文章目录】：
致谢
摘要
ABSTRACT
1 引言
    1.1 课题研究的背景和意义
    1.2 课题研究的内容和目标
    1.3 论文组织结构
2 倒排索引及其相关技术介绍
    2.1 倒排索引
    2.2 倒排索引的预处理方案
        2.2.1 D-Gap编码
        2.2.2 文档标识符分配技术
    2.3 模式化编码压缩
    2.4 模式化编码压缩算法
        2.4.1 Variable Byte编码
        2.4.2 Stream VByte编码
        2.4.3 Binary Packing编码
        2.4.4 PForDelta编码
        2.4.5 Simple Family编码压缩算法
    2.5 本章小结
3 PVU编码压缩算法
    3.1 PVU编码压缩算法
        3.1.1 PVU编码压缩算法的基本原理
        3.1.2 PVU编码压缩算法的模式选择
    3.2 PVU编码压缩算法的编码过程
    3.3 PVU编码压缩算法的解码过程
    3.4 PVU编码压缩算法实例
    3.5 PVU编码压缩算法的分区优化策略
    3.6 本章小结
4 Simple21编码压缩算法
    4.1 DocID序列取值分布研究
    4.2 Simple21编码压缩算法的基本原理
    4.3 Simple21编码压缩算法的编码过程
    4.4 Simple21编码压缩算法的解码过程
    4.5 本章小结
5 实验和分析
    5.1 实验评价指标
        5.1.1 倒排索引编码实验评价指标
        5.1.2 倒排索引解码实验评价指标
    5.2 实验环境
        5.2.1 实验数据集
        5.2.2 实验运行环境和相关工具
    5.3 倒排索引压缩算法编码实验与分析
    5.4 倒排索引压缩算法解码实验与分析
    5.5 本章小结
6 总结与展望
    6.1 研究工作总结
    6.2 对后续工作的展望
参考文献
作者简历及攻读硕士学位期间取得的研究成果
学位论文数据集



本文编号：3842686