一种高效的倒排索引存储结构_邓攀.pdf

ComputerEngineeringandApplications计算机工程与应用2008，44（31）149一种高效的倒排索引存储结构邓攀，刘功申DENGPan，LIUGong-shen上海交通大学信息安全工程学院，上海200240DepartmentofInformationSecurity，ShanghaiJiaotongUniversity，Shanghai200240，ChinaE-mail：[e-mail]，LIUGong-shen.Effectivestoragestructureofinvertedindex.ComputerEngineeringandApplications，2008，44（31）：149-152.Abstract：Invertedindexisthecorecomponentofaninformationretrievalsystem，thestoragestructureofitplaysacrucialroleineffectandefficiencyofretrieval.Inthispaper，accordingtothefrequenciesdistributionofChinesevocabularyandthecurrenthardwareandsoftwareenvironment，theauthorsintroduceaneffectivestoragestructureofinvertedindexthatcansavethediskusageandimprovetheefficiencyofretrieval，aswellassupportingrealtimeupdateanddelete.Keywords：invertedindex；dictionary；capacity；add-onblock摘要：倒排索引是信息检索系统的核心部分，其存储结构对检索的效率和效果起着至关重要的作用，根据汉语词汇的频率分布情况和当前的软硬件环境，提出一种高效的倒排索引结构，在一定程度上能够节省磁盘空间，提高检索效率，并且支持增量更新和删除。关键词：倒排索引；词典；容量；追加块DOI：10.3778/j.issn.1002-8331.2008.31.043文章编号：１００２－８３３１（２００8）31-0149-04文献标识码：Ａ中图分类号：TP3111引言可见，国内外针对倒排索引优化的研究主要出发点有3在当前的网络环境下，信息量和用户量都爆炸式的增长，个：（1）通过压缩技术减小索引在外存上的体积。（2）对倒排表这给大规模信息检索系统的准确高效的提供服务带来了很大内容的组织方式进行优化，减少需要访问的倒排表内容。如词的压力，而倒排索引是信息检索系统的核心部分，其组织方式频降序，插入同步点。（3）对倒排表的磁盘存储结构进行管理，和存储结构对信息检索系统得性能有很大影响，因此，除了改尽量减小磁盘的IO次数。进检索算法之外，优化倒排索引的存储结构成为一个很受关注当前通用的计算机存储介质中。主存读写效率比较高，存的课题。取时间在几十到100ns之间，但是存储容量有限。辅存一般由FScholer和JZobel等人提出倒排表根据文档号增序组一个或数个磁盘驱动器组成，其存储容量比较大，但是读取效织，通过倒排索引的数据压缩技术，希望通过减小索引文件体率相对较低。由于倒排索引文件规模比较大，磁盘上的倒排文积减小磁盘访问的开销。MPersin等人提出倒排索引按照词频件不可能一次性全部载入主存。根据磁盘访问的特性，磁盘访降序组织，结合向量空间模型检索方法减少对索引数据的访问问时间的主要决定因素在于磁盘寻道和旋转延迟时间，此项占和处理。文献[3]描述了用关系型数据库组织倒排索引的方法，用时间要比主存访问时间大4~5个数量级。由此可见，设计合这对简化检索系统的开发有很好的帮助，也能够通过数据库的理的存储结构，尽可能减小磁盘的寻址次数是减小磁盘访问时并行等技术在一定程度上提升系统性能，但是它很难针对索引间的重点。数据的结构特性进行细粒度的优化，灵活性上有所欠缺。文献[5]提出了一种支持即时更新的倒排索引组织方法，通过增加附大规模中文文本数据集的词频分布近似遵循zipf分布[8]。加索引文件适时更新实现。文献[6]提出了一种基于可扩展散列依照这种分布，只有小部分词是常用词，其倒排表所占用的空表的倒排索引结构。开源搜索引擎框架Lucene的索引结构设间比较大，增长很快，而大部分的词是不常用词，其倒排表占用计为属于一定数量文档集的倒排表占用一个存储块的组织形的空间比较小，增长也比较缓慢。根据以上情况，本文提出对倒式，每个存储块都有自己的词典，检索时需要对所有的存储块排表的存储原则：大