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

《基于倒排索引的压缩算法性能研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、杭州电子科技大学硕士学位论文基于倒排索引的压缩算法性能研究姓名：潘胜一申请学位级别：硕士专业：计算机软件与理论指导教师：万健20091001杭州电子科技大学硕士学位论文摘要在这个信息爆炸的时代，每天都会产生成千上百万的新信息，反映在因特网上，是网页数量的急剧增长。如何在巨量级的信息集合中，高效的定位、查找所需的目标信息，这使得搜索引擎成为当今最热门的技术之一，也对搜索引擎的性能提出了更高的要求。搜索引擎的索引结构与它的性能密切相关，倒排索引是搜索引擎使用最为广泛的索引保存形式，它将“关键词”作为

2、搜索的起始，追踪包含该关键词的众多信息源。在倒排索引中把关键字（term）映射到包含该关键字的文档集合，对于每一个关键字，记录包含该关键字的文档标识，文档内频率以及文档内位置信息：term->（fd,t,di,[p0,…pfreq−1]）……。本文所进行的索引压缩算法的研究是在该索引结构基础上进行的。采用索引压缩技术不仅能够减小索引的容量，同时也能提高查询性能。其优势在于压缩后的索引需要的存储空间较少，并且压缩后的数据能更好的利用通信带宽，相比未经压缩的数据，每秒能传输更多的信息量。基于快速解压的

3、方案，传输和解压压缩后数据的总时间代价比传输未经压缩的数据时间代价要小的多。在检索过程中，通常在内存中对倒排列表进行缓存，可提升查询响应的性能，在缓存容量相等前提下，能容纳更多以压缩形式存放的倒排信息，从而提升缓存的命中率及查询响应速度。本文所作的是在开源信息检索系统Lucene上，实现Variable-Byte、Simple9、PForDelta详尽评测，关注文档号、频率、位置信息在Lucene的word-level倒排索引中压缩存放。近年来有一些新的压缩算法提出，但还没有文章在基于Java环境

4、，流行通用，影响广泛的Lucene中来评测实验算法。本文的工作主要有1）改进具有最快解压速度PForDelta的实现，在保证不降低算法解压速度的前提下，提升了算法的位使用率，并加以实验验证。2）探讨在Java环境由if-then-else结构导致的分枝预测对Java程序的性能影响，在JVM中运行的程序弱化了分枝预测带来的性能损害。3）接着修改Lucene的索引结构，研究数据存放是否间隔分布对算法压缩比率和解压性能的影响。4）在本文的最后全面比较算法的压缩比率及关键字和短语查询性能，对实验结果进行分

5、析。从实验结果可以看出，在各个数量级的文档集合上，Variable-Byte表现最为稳定，并且在基于跳跃机制的短语查询中有最好的表现。Simple9有最好的压缩比率，但由于Java环境对分枝预测性能损害的弱化，其查询性能比其他两个算法要差。PForDelta在解压代码的关键区域去除if-then-else程序结构的基础上，获得了最快的关键字查询时间。当保证数值的非间隔分布后，Simple9和PForDelta的关键字查询有5%—8%的提升。由于跳跃查找的机制，在短语查询中批量解压的Simple9和

6、PForDelta表现不佳，但随着倒排列表的增长，PForDelta短语查询的性能逐渐提升。I杭州电子科技大学硕士学位论文关键词：倒排索引；索引压缩；索引压缩算法；性能评测；搜索引擎；LuceneII杭州电子科技大学硕士学位论文ABSTRACTIntheeraofinformationexplosion,tensofmillionsofnewinfoisgeneratedintheinternet,whichleadstorapidincreasementofwebpages.Howtoeffic

7、ientlylocateandfindtarget-infoinmassiveleveldataset?Itmakessearchenginebecomeoneofthemostpopulartechniquesandputforwardhigherrequirementsforsearchengine’sperformance.Forsearchengine,theindexstructureiscloselyrelatedtotheperformance;invertedindexisthem

8、ostcommonlyusedbysearchenginetorepresentindex.Invertedindexregards“term”asthebeginningofsearch,tracesnumerousinformationsourcescontainingthatterm.Ininvertedindex,oneperterm,recordingtheidentifiersofthedocumentscontainingthatterm,frequenciesand