论文简介：

毕业论文-倒排索引中位置信息的压缩方法研究，共42页，16851字
摘 要
大型搜索引擎系统每秒都在响应着数量巨大的用户请求。用户希望能够在上百亿的网页中找到相关的信息。但伴随着检索信息量的膨胀，搜索引擎在底层数据存储上的负担日益增加。同时，用户对检索返回结果的精确度要求也越来越高，这就要求搜索引擎对底层数据采取更细致的处理。
搜索引擎的底层数据结构是倒排索引。在搜索引擎的不断发展及优化下，倒排索引的位置信息越来越重要。存储倒排索引位置信息的空间几乎等同于倒排索引文档信息以及频率信息的总和，其I/O开销对总体性能有很大影响。
本文主要探讨倒排索引位置信息的压缩算法，减少其在存储空间上的代价，从而降低I/O开销来保证查询检索的效率。本文选取了一些典型的整数列表压缩算法对数据集倒排索引位置信息进行测试，结果表明Simple-16算法不仅有着不错的压缩效果，更在解压速度上有着明显的优势。之后本文又对Simple-16算法进行了符合数据集特征的改进，使其效果得到了进一步的提升。
关键词： 搜索引擎； 倒排索引位置信息； Simple-16编码；

目 录
摘 要 I
Abstract II
目 录 III
1. 绪论 1
1.1研究背景 1
1.2本文主要工作 2
1.3本文组织结构 2
2. 背景知识介绍 4
2.1倒排索引简介 4
2.2倒排索引的存储 5
2.3倒排索引压缩算法简介 7
2.3.1 无参压缩算法 8
2.3.2 带参压缩算法 11
2.3.3 字/字节对齐压缩算法 12
2.3.4 文本相关的压缩算法 13
2.4压缩效果与解压效率 14
3. 压缩算法的分析与优化 15
3.1 Simple-16算法简介 15
3.2 Simple-16针对位置信息的改造 16
3.2.1 倒排索引位置信息特征 16
3.2.2 数据集结构整理 17
3.2.3 数据集位置信息分析和利用 19
3.3.4 改进的Simple-16算法NewSimple-16 23
3.3 压缩算法的比较 27
4. 实验验证 28
4.1 实验环境 28
4.1.1 程序环境 28
4.1.2 数据集介绍 28
4.2 实验结果 28
4.3 实验分析 30
5. 总结和展望 32
参考文献 33
致谢 35

本文主要工作
本文首先研究了现有的倒排索引压缩算法，以及它们在压缩效果、解压效率上的特点。包括无参的Elias code，带参的Golomb(Rice) code，文本相关算法，以及字/字节对齐的压缩算法，VByte，PForDelta，Simple-16等。
在了解了各算法特性之后，根据压缩效果与解压效率的均衡，选择符合要求的算法对数据集倒排索引信息进行压缩解压测试。其中按字/字节压缩算法在压缩效果与解压效率的均衡上有十分好的优势。
本文通过反复试验，测试了Rice code等常用算法，最终选择了按字/字节压缩算法中的Simple-16算法，对数据集中倒排索引位置信息进行压缩。实验获得了较好的压缩效果的同时也获得了很高的解压速率。之后，又根据数据集倒排索引位置信息的特点对Simple-16算法进行了有针对性的改进，取得了较之前更好的压缩效果。

本文组织结构
本文组织结构如下：
第一章：绪论。本章介绍了研究背景和本文的主要工作，并展示本文的层次结构。
第二章：背景知识介绍。本章介绍了倒排索引其数据结构特性，第二节中，展示倒排索引的存储特点。在第三节中，介绍了现有的适用于倒排索引的压缩算法。并在最后一节展示了倒排索引压缩效果与解压效率之间的关系。
第三章：压缩算法的分析与优化。本章首先介绍了现有压缩算法压缩效果与解压效率的关系特性对实际数据集处理的影响。接下来，本章选择了一种Simple-16算法作为数据集的压缩算法对数据集进行处理，同时对Simple-16算法进行了进一步的介绍与分析。在第二节中，展示了Simple-16算法针对数据集倒排索引位置信息的优化与改进方案。
第四章：本章通过实验，对所选出并且改进的算法进行了测试与评估，同时对实验结果进行了具体的分析与解释。
第五章：工作总结与展望。总结整个探究过程的经验，对倒排索引的压缩方法进行更深一步的探究与展望。

论文文件预览：
共1文件夹，1个文件，文件总大小：611.08KB，压缩后大小：529.52KB

• 毕业论文-倒排索引中位置信息的压缩方法研究
• 毕业论文-倒排索引中位置信息的压缩方法研究.docx  [611.08KB]