计算机应用

作者：姜琨, 刘征, 朱磊, 李晓星

单位：1. 西安理工大学 计算机科学与工程学院, 西安 710048;2. 陕西省网络计算与安全技术重点实验室(西安理工大学), 西安 710048;3. 中国人民解放军 63785部队, 西安 710043

关键词：倒排索引,等字长压缩算法,有向无环图,最优划分,动态规划

基金：国家自然科学基金资助项目（61602374）；陕西省自然科学基础研究计划项目（2016JQ6041）。

在搜索引擎的倒排索引等字长（FWA）类型压缩算法中，倒排链的“贪心”分块划分策略和码字信息的交错存储使算法难以达到最优的压缩效果。针对上述问题，提出了一种基于有向无环图（DAG）的FWA划分压缩算法。首先，考虑到互联网网页聚类特性带来的倒排链小数字信息，设计了一种数据区为64位分块的新型FWA压缩格式。该压缩格式通过4位的指示区将数据区划分为16种适合于连续小数字压缩的存储模式，并将倒排链每个分块的指示位和数据位分类存储，从而保证了较好的批量解压性能。其次，在新压缩格式的基础上提出一种基于DAG描述的倒排链FWA划分压缩方法——固定字对齐划分（WAP）算法。该算法利用DAG将倒排链分块划分问题归结为单源最短路径（SSSP）问题，并考虑FWA压缩格式中数据区存储模式的限制条件来确定SSSP问题的结构形式和递归定义。然后，给出了采用动态规划求解SSSP问题并形成最优划分向量的伪码和算法复杂度，并对S9、S16、S8b等传统FWA算法的原有存储模式进行了基于DAG的划分优化，把优化前后的算法的计算复杂度进行比较分析。最后，使用仿真整数序列数据和文本检索会议（TREC） GOV2网页索引数据进行压缩性能实验。实验结果表明，相较于传统FWA类型算法，基于DAG的FWA划分算法在通过批量解压和划分优化技术提升算法的压缩率和解压速度同时，对连续小数字整数序列进行压缩时能够获得比传统参照框架（FOR）类型算法更高的压缩率。

来源：2021年第3期

《计算机应用》期刊编辑部

查看计算机应用杂志2021年第3期