基于有向无环图的倒排链等字长划分压缩算法

姜琨; 刘征; 朱磊; 李晓星

首页> 中文期刊> 《计算机应用》 >基于有向无环图的倒排链等字长划分压缩算法

基于有向无环图的倒排链等字长划分压缩算法

开具论文收录证明 >>

期刊封面封底目录下载 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

在搜索引擎的倒排索引等字长(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期|727-732|共6页
作者
姜琨; 刘征; 朱磊; 李晓星;
展开▼
作者单位

西安理工大学计算机科学与工程学院西安710048;

陕西省网络计算与安全技术重点实验室(西安理工大学) 西安710048;

西安理工大学计算机科学与工程学院西安710048;

陕西省网络计算与安全技术重点实验室(西安理工大学) 西安710048;

西安理工大学计算机科学与工程学院西安710048;

陕西省网络计算与安全技术重点实验室(西安理工大学) 西安710048;

中国人民解放军63785部队西安710043;

展开▼
原文格式 PDF
正文语种 chi
中图分类算法理论;
关键词
倒排索引; 等字长压缩算法; 有向无环图; 最优划分; 动态规划;

相似文献

中文文献
外文文献
专利

1. 基于分区的Elias-Fano-Golomb-Rice倒排索引压缩算法 [J] . 李俊廷 ,瞿有利 . 计算机与现代化 . 2017,第009期
2. 基于指令级并行的倒排索引压缩算法 [J] . 闫宏飞 ,张旭东 ,单栋栋 . 计算机研究与发展 . 2015,第005期
3. 基于64位体系结构的倒排索引压缩算法 [J] . 张旭东 ,孙志明 ,刘亚宁 . 计算机工程 . 2014,第002期
4. 基于主成分分析与栅格划分的点云压缩算法研究 [J] . 付忠敏 ,张星 ,孙志刚 . 计算机与数字工程 . 2017,第012期
5. 基于解空间划分的工艺参数曲面压缩算法 [J] . 李训根 ,罗小华 ,孙玲玲 . 电路与系统学报 . 2009,第001期
6. 倒排文件压缩算法 [C] . 张磊 . 中国科学院计算技术研究所第六届计算机科学与技术研究生学术讨论会 . 2000
7. 基于模式化编码的倒排索引压缩算法研究 [A] . 安兆翔 . 2019

基于有向无环图的倒排链等字长划分压缩算法

摘要

著录项

相似文献

相关主题

期刊订阅