（1.西安理工大学计算机科学与工程学院，西安 710048；2.陕西省网络计算与安全技术重点实验室（西安理工大学），西安 710048；3.中国人民解放军63785部队，西安 710043）

0 引言

不断增长的互联网网页规模给搜索引擎系统的倒排索引存储带来了持续的挑战和研究需求［1-2］。近年来，大量互联网应用的蓬勃发展更使搜索引擎系统待索引的数据规模进一步增加［3］。一般来说，倒排索引包括倒排文件和词典文件，倒排文件包含着一串被压缩的倒排项信息：文档号（docid）和词频（freq），其中文档号可以转换为更小的d-gap 整数序列。倒排索引压缩的目的就是采用尽可能接近最优位（bits）数的码字存储原来以一个机器字长表示的倒排信息整数，同时保证对码字解压的无歧义和高效性。倒排索引压缩技术的优势在于可以降低压缩数据的存储开销和传输开销，从而实现对海量压缩倒排索引数据的快速内存查询访问［4-5］。因此，倒排索引压缩技术一直以来都是提升海量倒排索引数据存储和查询性能的必要手段和研究热点。

目前，倒排索引压缩算法中被广泛研究和采用的是字对齐压缩算法，该类型算法又可以分为参照框架（Frame Of Reference，FOR）类型压缩（如：FOR、PFOR（Patched FOR）、OPT-P4D（OPTimzed PForDelta）等算法）和等字长（Fixed Word-Aligned，FWA）类型压缩（如：S9、S16、S8b 等）两类［6-7］。本文所研究的FWA 类型压缩算法在保证每个被压缩整数位宽小于其填充模式的限制条件下，所采用的整数序列“贪心”划分策略将尽可能多的相邻整数存储在32q（q为正整数）位的机器字内。研究表明，FWA 类型算法的优势在于：1）在给定的机器字长内存储模式更加细化，可以缓解倒排链中异常数字导致的分块位宽的浪费问题；……