《表3 Simple-9中采用的9种填充模式》

  提示：宽带有限、当前游客访问压缩模式

本系列图表出处文件名：随高清版一同展现

《倒排索引压缩算法研究综述》

1. 获取 高清版本忘记账户？点击这里登录

1. 下载图表忘记账户？点击这里登录

Simple系列:该系列压缩算法最初由Anh和Moffat提出，包括Simple-9压缩算法[33]及其改进压缩算法如Carryover-12、Slide等[34-37]，其基本思想是将尽可能多的整数压缩在一个单一的32位机器字中．如表3所示，Simple-9压缩算法使用4比特作为状态位来描述其余28个数据位，形成9种可能的数据位填充模式．每种填充模式为每个被压缩的整数分配固定的比特宽度．解压阶段通过状态位确定填充模式来提取数据位存储的所有整数．压缩和解压过程采用硬编码方式来降低循环的次数．Simple系列压缩算法中每次可压缩的整数个数因采用的填充模式不同而不同．因此，Simple系列压缩方法实际上是依据填充模式对倒排链表进行“贪心”划分（left-greedy partition）并分别压缩．为了将更多的整数压缩到一个机器字中并降低固定比特宽度带来的位宽浪费，研究人员提出了众多具有更为丰富的数据填充模式的改进算法，包括Carryover-12、Slide、Simple-16、Simple-8b等[33-37]．尤其是Simple-8b作为对Simple-9在64位机器字上的改进，采用4比特的状态位来描述60位数据位的不同填充模式[35].Simple-8b因为采用64位机器字对压缩序列进行处理，增加了单次可编码的整数个数．故Simple-8b相比Simple-9能够明显减少CPU分支判断的次数，所以其压缩和解压速度都好于Simple-9算法．