学位论文 > 优秀研究生学位论文题录展示

基于倒排索引的压缩算法性能研究

作　者: 潘胜一
导　师: 万健
学　校: 杭州电子科技大学
专　业: 计算机软件与理论
关键词: 倒排索引索引压缩索引压缩算法性能评测搜索引擎 Lucene
分类号: TP391.3
类　型: 硕士论文
年　份: 2009年
下　载: 80次
引　用: 2次
阅　读: 论文下载

内容摘要

在这个信息爆炸的时代,每天都会产生成千上百万的新信息,反映在因特网上,是网页数量的急剧增长。如何在巨量级的信息集合中,高效的定位、查找所需的目标信息,这使得搜索引擎成为当今最热门的技术之一,也对搜索引擎的性能提出了更高的要求。搜索引擎的索引结构与它的性能密切相关,倒排索引是搜索引擎使用最为广泛的索引保存形式,它将“关键词”作为搜索的起始,追踪包含该关键词的众多信息源。在倒排索引中把关键字(term)映射到包含该关键字的文档集合,对于每一个关键字,记录包含该关键字的文档标识,文档内频率以及文档内位置信息:term->( f d ,t, d i, [ p0 ,…p freq?1 ])……。本文所进行的索引压缩算法的研究是在该索引结构基础上进行的。采用索引压缩技术不仅能够减小索引的容量,同时也能提高查询性能。其优势在于压缩后的索引需要的存储空间较少,并且压缩后的数据能更好的利用通信带宽,相比未经压缩的数据,每秒能传输更多的信息量。基于快速解压的方案,传输和解压压缩后数据的总时间代价比传输未经压缩的数据时间代价要小的多。在检索过程中,通常在内存中对倒排列表进行缓存,可提升查询响应的性能,在缓存容量相等前提下,能容纳更多以压缩形式存放的倒排信息,从而提升缓存的命中率及查询响应速度。本文所作的是在开源信息检索系统Lucene上,实现Variable-Byte、Simple9、PForDelta详尽评测,关注文档号、频率、位置信息在Lucene的word-level倒排索引中压缩存放。近年来有一些新的压缩算法提出,但还没有文章在基于Java环境,流行通用,影响广泛的Lucene中来评测实验算法。本文的工作主要有1)改进具有最快解压速度PForDelta的实现,在保证不降低算法解压速度的前提下,提升了算法的位使用率,并加以实验验证。2)探讨在Java环境由if-then-else结构导致的分枝预测对Java程序的性能影响,在JVM中运行的程序弱化了分枝预测带来的性能损害。3)接着修改Lucene的索引结构,研究数据存放是否间隔分布对算法压缩比率和解压性能的影响。4)在本文的最后全面比较算法的压缩比率及关键字和短语查询性能,对实验结果进行分析。从实验结果可以看出,在各个数量级的文档集合上,Variable-Byte表现最为稳定,并且在基于跳跃机制的短语查询中有最好的表现。Simple9有最好的压缩比率,但由于Java环境对分枝预测性能损害的弱化,其查询性能比其他两个算法要差。PForDelta在解压代码的关键区域去除if-then-else程序结构的基础上,获得了最快的关键字查询时间。当保证数值的非间隔分布后,Simple9和PForDelta的关键字查询有5%—8%的提升。由于跳跃查找的机制,在短语查询中批量解压的Simple9和PForDelta表现不佳,但随着倒排列表的增长,PForDelta短语查询的性能逐渐提升。

全文目录

摘要  5-7
ABSTRACT  7-11
第1章绪论  11-15
  1.1 选题背景  11
  1.2 选题意义  11-12
  1.3 研究内容及相关工作  12-13
  1.4 论文的内容结构  13-15
第2章 Lucene 中的倒排索引  15-24
  2.1 倒排索引的阐述  15-16
  2.2 倒排索引的构建技术  16-17
  2.3 Lucene 中的索引架构  17-23
    2.3.1 Lucene 的特点及相关阐述  17-18
    2.3.2 Lucene 功能结构分析  18-20
    2.3.3 Lucene 索引文件构建  20-23
  2.4 本章小结  23-24
第3章倒排索引的压缩算法  24-35
  3.1 压缩算法综述  24-25
  3.2 Variable-Byte 编码  25-26
    3.2.1 算法分析  25-26
    3.2.2 算法实现  26
  3.3 Simple9 编码  26-28
    3.3.1 算法分析  26-28
    3.3.2 算法实现  28
  3.4 PForDelta 编码  28-34
    3.4.1 算法分析  28-30
    3.4.2 算法实现  30
    3.4.3 算法的改进及实验  30-34
  3.5 本章小结  34-35
第4章影响算法性能的因素  35-41
  4.1 基于Lucene 的实验部署  35
  4.2 if-then-else 构造对Java 程序的影响  35-38
    4.2.1 Lucene 的奇偶校验策略  35-36
    4.2.2 分支构造的影响评测  36-38
  4.3 数值间隔分布对压缩算法的影响  38-40
  4.4 本章小结  40-41
第5章索引压缩算法的综合性能研究  41-49
  5.1 算法的压缩比率  41-44
    5.1.1 实验结果比较  41-42
    5.1.2 算法压缩比率差异探讨  42-44
  5.2 算法关键字查询性能  44-45
  5.3 算法短语查询性能  45-48
    5.3.1 短语查询机制  45-47
    5.3.2 性能分析  47-48
  5.4 本章小结  48-49
第6章总结与展望  49-51
  6.1 论文总结  49-50
  6.2 研究展望  50-51
致谢  51-52
参考文献  52-55
附录  55-56
中文详细摘要  56-60

基于倒排索引的压缩算法性能研究

内容摘要

全文目录

相似论文