Fast Dictionary-Based Compression for Inverted Indexes 总结

1. 内容复述

Abstract

基于字典的压缩方案提供了快速的解码操作，相比于统计学方法和基于概率的方法，一般应以降低压缩效率为代价。在这篇文章中，我们把基于字典的技术应用于倒排表列的压缩中，结果表明，这些整数序列对于字典方法的匹配表现出高度正则并且与某些类型的字典是匹配良好，能够在压缩效率和压缩效益之间实现一个新的权衡标准。我们通过对两个大型文本集合的文档级倒排索引和大量其他索引压缩实现结果作为参考点论述支撑我们的观察结果。实验证明压缩效率和压缩效益的差距可以大大缩小。

Keywords

倒排索引；效率；压缩；解码

1.1 Introduction

压缩的倒排文件仍然是一个非常重要的数据结构，它支持跨大型文档集合进行高效的基于关键字的查询。对于集合中出现的每个术语t，将构造一个过帐列表，其中包含序列⟨ $d_{t,i}$ ⟩和⟨ $f_{t,i}$ ⟩，其中 $d_{t,i}$ and $f_{t,i}$ 分别是包含t的第i个文档的顺序文档号，以及t在该文档中出现的次数。这些索引支持多种查询方式。
在这项工作中，我们重新讨论了表示序列⟨ $d_{t,i}$ ⟩和⟨ $f_{t,i}$ ⟩的问题。已经开发了一系列广泛的压缩技术[30，40]，最近的工作包括使用基于ANS的压缩[23，24]；对投递列表进行聚类[29]；以及结合众所周知的VByte方法使用通用压缩库[28]。如果主要目标是快速解压缩，我们关注的是这个频谱的效率端，即如何最好地表示压缩形式的序列。这个领域的竞争对手包括Trotman的QMX编解码器[36]；VByte和Simple16字节和字对齐机制[2，39]；以及Zukowski等人的PFOR方法。[45]。

Contribution

我们开发了一种新的压缩方法，DINT，基于整数序列字典。一个关键的概念是固定到固定(fixed-to-fixed)解码，这与之前探索的多变量到固定和固定到变量的方法形成了鲜明的对比。核心思想是每个解码单元消耗一个16位或8位整数码字，并导致从内部码本（字典）到输出缓冲区的固定长度复制操作。这种方法的简单性意味着力解码是快速的。此外，DINT还提供了非常好的压缩效果。效率和有效性的改进组合为已知权衡选择的可用范围提供了一个重要的新参考点。

1.2 Background

我们假设要存储一个整数序列S=⟨ $s_i$ ⟩，其中 $s_i$ ∈∑={1,....|∑|}。（1≤i≤| S|)。对于反向索引压缩，序列由文档标识符 $d_{t_i}$ （我们称之为docid）和与之相关联的频率 $f_{t_i}$ （称之为freqs）组成，其中索引中的每个帖子的格式为⟨ $d_{t,i}$ , $f_{t,i}$ ⟩。这两个组件可以单独存储；完全交错；或者以某种大小的块B存储，然后在较粗的级别上进行交错。通常还将每个投递列表中的docid转换为间隔序列⟨ $d_{t,i}$ − $d_{t，i−1}$ ⟩（假设 $d_t$ ，0=0），并对通过计算前缀和来重构升序序列的解码提出相应的要求。倒排索引数据的一个关键特征是这两个序列都由小值控制。
字节和字对齐的代码。在字节对齐的压缩方法[31，35，39]中，输入整数被划分成7位片段，片段被放在字节中，每个字节有一位空闲。然后，该位用作标记每个整数的最后一个片段的标志，允许通过逐字节移位和掩码操作重新构造编码值。
其他方法。其他最近的工作包括Ottaviano和Venturini[26]，Ottaviano等人。[27]，Wang等人。[38]、Moffat和Petri[23，24]、Pibiri和Venturini[29]。我们在第5节的实验中包括了其中的一些方法。
基于字典的压缩。马丁内斯等人[22]引入了一种基于字典的方法，他们称之为多重可分解。从符号字母表上的概率分布和无记忆源的假设开始，它们构造一组字符串，用以填充某个目标大小的字典，然后使用贪婪解析方法将任何输入序列呈现为整数字典偏移流。它们的字典允许包含作为其他项前缀的序列，并且这些项的最大长度被限制，以便它们可以存储在矩形二维数组中。

表1：两个多可分解字典的例子，宽度为4，覆盖字母{a，b，c，d}，其中符号“a”是高度可能的，符号“b”是中度可能的，而“-”表示不关心的值。最后一列提供每个字符串的长度，并作为字典的一部分存储。在（b）中，索引0用作罕见符号异常的代码。
马丁内斯等人。[22]使用最后一个ℓ+1列作为加速解码的方法。解码过程不是执行一个循环，精确地计算从字典条目到输出缓冲区的正确符号数，并在每次迭代时测试一个保护，而是始终在一个固定的操作中将完整的ℓ+1符号复制到输出缓冲区，然后将输出指针增加由ℓ+第一个复制值。由于消除了最内层嵌套循环中的条件，减少了分支误预测，从而获得了较高的译码速度。建立马丁内斯等人的字典。[22]描述一个过程，该过程根据字符串对应的符号频率所指示的零阶出现概率，暂时地将字符串分配给字典，然后迭代地优化这些估计，收敛到一组提供最佳覆盖率的可变长度字符串。他们为不同的初始符号分布构建一套这样的字典，然后使用它们对64×64像素的灰度图像数据块进行无损编码，为每个块选择一个匹配的字典，并在块的开始通过选择器向解码器指示。

1.3 Base Implementation

我们现在描述了基于字典的压缩在倒排索引数据中的初步应用。然后，在第4节中，介绍了一系列改进。

字典。有两个因素使倒排索引数据具有高度的显著性。首先，有很长的“1”序列（几乎总是字母表中最频繁的符号），这为使用频繁符号异常创造了机会，即在正常机制之外处理长的重复序列。如第5节所示，在典型的反向索引序列中，超过三分之一的docid和freq是“1”s，经济地处理这些是一个关键要求。第二，docid间隙的字母表非常大，达数百万，不可能考虑为每个符号提供一个码字，甚至作为一个单独的符号。相反，必须使用罕见的符号异常，这是一种特殊代码，表示下一个符号必须从未压缩整数的次流中获取。图1显示了2048个docid间隙的典型提取中出现的重复频繁子序列的示例。每个彩色矩形表示在索引中多次出现的序列，因此可以表示为相对于65536个这样的序列的字典的码字。在这个典型片段中，只有三个docid间隙非常罕见，它们被编码为异常，而不是通过字典。

图片说明
如图1所示：从大型文本集合中单个术语的发布列表中分析2048个docid间隙的典型序列，8个大小为B=256的块，每行跨越64个docid。长串的“1”以最深的蓝色显示；其他阴影表示长度为1、2、4、8和16的频繁出现的子序列，并根据字典进行编码。第九行和第十行中的三个红色方块是docid间隙，在集合中比较少见，必须将它们编码为异常，因为它们不会出现在字典中。

罕见的符号例外。要查看稀有符号异常的用法，请考虑表1（b）中所示的字典，其中只提供了两个单例代码。使用此表，相同的示例字符串⟨a aa b aabc a a aa b⟩将被解析为⟨aaab、aa、b、－、c、aaaa、b⟩，并编码为整数序列⟨7、3、2、0、c、6、2⟩，总共使用6×3+1×2=20位，其中假定“c”（在转义码字“0”之后）所需的罕见符号异常需要两位超过四个符号的字母表。在这个小例子中，总的来说成本略有降低，主要是因为字典中出现了字符串“aaab”。但是一般的原则是有效的：字典中包含的长序列越多，我们希望达到的压缩率就越高。
索引压缩中使用的大符号字母表意味着使用多个异常选项是有意义的：代码“0”表示对应的修补符号是1到2b之间的b位值，其中，与之前一样，b是每个码字的位宽度，字典是2b个条目；代码“1”表示相关的修补值是2b+1到22b范围内的2b位值；依此类推。例如，当nb=16时，两个罕见的异常代码覆盖32位整数的空间；如果b=16，则使用四个罕见的符号异常代码字，并且将输入视为64位整数的空间。
频繁的符号异常。为了处理长时间运行的“1”，添加了更多的异常代码，包括长度为B、B/2、B/4、。，2海里。其中第一个覆盖了整个区块，所有的“1”都是非常经济的；如果需要的话，短距离的（仅）“1”可以被常规的非异常代码覆盖。因此，对于b=Ψ=16配置，将为异常保留六个字典槽—两个罕见的符号异常代码和四个频繁的符号异常代码—为常规字典条目保留65530个代码字。
频率估计。组成字典的2b序列集应该根据被压缩的数据进行裁剪，这样字典就可以存储一些非常有用的子序列。为了计算子序列的频率，采用区间抽样方法，以L=2k≥Ψ的均匀间隔检验源序列，并提取每一长度的样本∏′？？{1,2,4。，在那一点。一个长度序列的频率随着L/Ψ′的增加而增加。例如，如果Ψ′=2和L=8，则在输入序列中每8个符号提取一个2符号前缀，并且该2符号组合的频率增加4。为了减少计数时间，可以使L相对较大，例如L＝1024，并且为了减少累积计数的数据结构所需的空间，可以采用基于保留的方法[19，37]。这两种技术都产生了序列频率的估计，而不是精确的计数。但拥有精确的计数并不一定更有用，因为从源序列中解析的任何特定因素可能包括部分或所有其他字典字符串，从而影响这些计数。在表2和第5节中报告的试验中，使用了L=Ψ′的穷举取样。
字典构造。一般来说，当相对于字典进行编码时，构建一个最小化消息长度的字典的问题是NP-hard[34]。因此，我们不寻求最优解，而是考虑两种启发式方法来选择用来填充字典的2b序列集。两种方法都假设每个观测到的序列S的长度| S |已被估计为出现频率[S]次。第一种方法——我们称之为减少静态体积，或DSV——选择提供最大覆盖体积的目标集合，其中覆盖体积被计算为目标频率和长度的乘积，而不考虑序列之间可能的相互作用。也就是说，给每个候选序列一个| S |×freq[S]的分数，并且使用得分最大的序列集合来构成字典。一个更细致的分析导致了我们探索的第二个启发。假设某个序列S被认为放在字典中。考虑到S现在是候选词，它的上半部分（表示S1，长度为| S |/2）和下半部分（表示ds2，也表示长度为| S |/2，其值为S1 S 2）似乎已经在字典中了。这是因为（假设间隔采样）freq[S1]≥freq[S]和（通过对称，但不保证）freq[S2]≥freq[S]。如果s1和s2已经在字典中，那么通过将S添加到字典中生成的保存仅为freq[S]，因为每个S实例将使用一个码字，而不是两个。同样的论点也可以归纳应用，在考虑单重态时会出现基本情况。不将它们包含在字典中的真正成本只是使用罕见的符号异常所产生的成本差异。因此，我们考虑的填充字典的第二个启发式是降低静态频率或DSF，选择具有最高频率估计的序列，而不考虑长度。作为第二个排序键，要断开连接，我们按减小长度| S |排序。请注意，这个归纳论点也是为什么我们关注一组受限的目标长度{1，2。，Ψ/2，Ψ}，其中，对于某些k，Ψ= $2^k$ 。

set output <- 0  
while output < B do
    set codeword <- get_code()
    if codeword < 6 then 
            if codeword < 2  then
                use get_code() to access and copy
                    excep_lens[codeword] codes to output
                   set output <- output + 1
            else 
                bulk copy excp_lens[codeword] "1"s to output
                    from an array containning 2^b "1"s
                set output <- output + excep_lens[codeword]
       else 
        set index <- start[codeword]
        copy l symbols from dictionary[index] to output
        set output <- output + length[codeword]

图2：如上述代码，一个块的解码过程。函数get_code（）将输入序列中的nextb位作为整数值返回；数组length[]是指对应目标序列的length[]，可以存储为start[]数组的一个组件（见图3）；固定数组excep_lens[]包含与b和Ψ的选择相匹配的值。例如，当b=Ψ=16和b=256时，excep_lens[]={1,2,256,128,64,32}。

我们还探索了自适应选择启发式算法，动态更新序列的频率计数，这些序列在提交到字典时是较长字符串的前缀和后缀，其思想是保持更精确的频率估计。在一些测试情况下观察到压缩效率的小幅度提高，但在其他情况下观察到小幅度损失；总体而言，我们无法始终优于DSF方法。其他用于填充字典的改进机制将成为未来研究的目标，注意到我们在这里面临的问题与用于索引压缩的重配对压缩技术[16]相似[7]；Apostolico和Lonardi[3]还考虑了识别有用子序列的问题。
解码。标准的访问单元是一个由B整数组成的块，我们在整个调查过程中使用B=256；也就是说，每个发布列表被划分为固定长度的块，剩余的元素使用一个辅助机制表示。只有不到5%的帖子是用这种方式编码的。每个整数块表示为一个或多个码字的集合，每个码字都是ab位二进制代码。
解码算法的动作如图2所示，其中假设b＝1＝16，码字“0”和“1”表示罕见的符号异常，码字“2”。“5”表示频繁的符号异常。如果b或Ψ是可变的，则可能需要进行小的更改，但请注意，罕见的符号异常码字和频繁的符号异常码字应始终在代码空间中组合在一起，以便单个条件足以达到主情况，指字典中的符号序列的标准码字（步骤14）。

选择参数。为了建立完整实现的可能参数组合，我们使用Gov2文档集合（见表5）和DSV字典构造启发式，对变量b（每个码字的位）和Ψ（字典条目的最大长度，整数）进行了初步探索。表2列出了总索引大小（以GiB为单位）；可以看出，一旦确定了合适的字典，有几种组合b和Ψ提供了良好的压缩效果，其中b=16和Ψ=16组合略优于其他组合。第5节提供了该数据集上以及第二个集合上的其他方法的基线压缩率，以及解码速度测量。作为一个单独的初步参考点，相同数据的VByte索引占用11.85gib，并且需要两倍以上的空间。

复制固定长度字符串。为了进一步推动基于固定长度字典的压缩，表3显示了在解码同一个Gov2数据集的序列时使用Linux perf实用程序收集的统计信息。在左边的一对列中，复制过程是通过一个由变量控制的循环执行的，该变量将正确数量的符号从字典复制到输出；在右边的一对列中，始终复制一个常量Ψ符号，其中。在编译时修复。复制固定数量的字节可以更好地利用指令缓存，并导致更高的指令吞吐量（指令/周期）和更少的缓存和分支未命中。总的来说，提取每个解码整数所需的时间减少到大约三分之二，如果复制过程是由复制更少字节的循环控制的话，这将大大减少。解码速度分析。影响时序译码的两个参数时间：m，每个码字的解码整数的平均数，以及c，与每个码字相关联的复制操作的开销。对每个码字解码更多的值会增加吞吐量；另一方面，在单个解码操作期间复制更少的字会更快。这意味着，使用更小（更大）的值可以减少（增加）单个拷贝操作的成本，但也需要更多（更少）的操作来解码序列。为了量化这种行为，表4使用Gov2的DOCID和FREKS序列报告了测量值forc，并将其作为一个函数。预测的解码时间以c/m纳秒/整数计算，并在标题为“实际”的列中提供对测量的解码成本的合理估计。

图片说明
表2:Gov2集合的完整文档级索引（docid和freq组合，包括块访问开销和字典空间）的总索引大小（GiB），使用块大小B=256项和DSV字典构造方法。

图片说明

表3:LinuxPerf工具报告的性能计数，在使用矩形字典解码Gov2的索引序列时，比较可变长度复制和恒定长度复制（当Ψ=16时）。

图片说明

图3：表1（b）中所示字典的打包布局，其中“4”和“3”。start[]中每个元素的第一个数字是序列长度。所有结尾的“不在乎”符号都已被修剪，如果字典序列是另一个较长序列的前缀，则字典序列已被删除。例如，当输入的码字是3时，字典中的四个整数[4。7] 复制到输出，然后输出指针递增2。在本图中，没有对频繁的符号例外做出规定。

图片说明

表4：使用带矩形字典的DINT-DSF和b=16对Gov2序列进行解码时，每个码字的解码整数平均数m；基于每个码字测量的解码时间c，预测和实际解码时间，单位为纳秒/整数。

1.4 进一步的改进

本节描述了对第3节中提出的初始方案的一些改进。

压缩字典结构。第3节中使用的矩形字典和表1所示的矩形字典在空间方面可能很昂贵，特别是如果长度目标相对较少，或者不同目标的前缀和后缀之间有明显重叠。为此，我们考虑减少字典所需空间的方法，注意所需空间越小，就越有可能主要保留在缓存中。为了减少字典所需的内存，可以使用图3所示的压缩格式。现在，目标长度从序列中分离出来，多个目标可以在单个合并字典字符串中指示相同的起始位置。打包字典既可以避免未使用的尾随符号，也可以让彼此作为前缀的目标共享空间。在数组start[]的每个字典偏移量内，每个字典条目的length[]组件（见图2）作为一个单字节字段存储，允许区分具有相同起点的序列，这种排列只要b≤24且Ψ<256就有效。通过start[]的间接寻址意味着在图2中的每个最里面的循环中需要一个额外的数组解引用操作，外加一个mask/shift序列来提取start[codeword]的两部分，但是净成本是适中的，并且可能需要节省空间。矩形形式的一个Ψ=16和B=16字典需要4×216×（16+1）=4.25 MiB；压缩形式的需求可以减少到大约1 MiB。详细结果见第5节。

利用字符串重叠。除了前缀匹配和尾随的不在乎之外，还可以进一步节省开支。例如，通过策略性的重新排序和重叠，图3中的TwelveSymolDictionary[]数组可以进一步压缩为6个符号“baaab”，因为表1（b）中列出的每个目标都作为子序列出现在其中。一个最小长度超序列的识别问题是NP难的。但是简单的贪心近似算法可以提供一个常数因子内的最优解[4，15]。我们采用的方法考虑了序列的初始集合，确定一个序列的前缀和另一个序列的后缀之间可能的最长匹配，并用它们的重叠连接替换这两个序列。每一个这样的步骤将集合中的序列数量减少一个，并确保出现一个序列，其中嵌入了每个原始序列。例如，从表1（b）中的序列开始，第一个循环结合“aaaa”和“aaab”形成“aaaab”。

最佳块解析。基于字典的压缩实现通常使用贪婪的从左到右的解析，在每个编码步骤使用最长的匹配字典条目。但在这里考虑的情况下，很容易为每个块确定最佳解析，因为每个字典序列或频繁符号异常都有一个代价，而每个罕见符号异常也有一个固定代价，这个代价只取决于它的值。图4显示了块的前缀如何与非循环有向图中的节点相对应，以及字典条目如何是将块的一个前缀扩展到更长前缀的边。在这个图中，从源到汇的最短路径描述了一个最优的解析，并且可以通过从左到右的迭代标记过程来计算，该过程将源的成本分配为零，然后通过每个节点发出的边将暂定成本向前推。每个节点可能存在的少量边（如果目标长度限制为2的幂次，则最大值为log2ó+1）使得该过程仅比更常见的贪婪方法慢一些，对于n个整数的列表，复杂性为O（nlogó），因此，如果将Ψ视为常数，复杂性为O（n）。

多重字典。以Moffat和Petri[23]为例，也可以使用多个字典。例如，如果输入符号被假定为介于1和232-1之间的整数，则使用32个字典允许在由⌊log2max⌋建立的上下文中处理每个块，其中max是块中的最大值。根据块的最大值对块进行分层，并根据为该最大值专门创建的字典对每个块进行编码，这提供了明显的好处。例如，max<4的块很可能与max<1024的块生成完全不同的字典，即使“1”可能仍然是最常见的符号。然而，这是有代价的——每个额外的字典都必须在解码操作期间存储，这既增加了内存开销，也增加了缓存未命中的可能性。出于这个原因，其他成本更低的分类也可能是可取的。在第5节中，我们使用映射上下文=⌈log2log2max⌉（当max=1时取log20=0），创建一组六个不同的上下文（0。5）限制值为2、4、1625665536和232。一旦创建了字典套件，编码器要么使用相同的映射来确定在对每个块进行编码时要使用哪个上下文，要么对所有上下文执行详尽的搜索，以确定最小化压缩大小的上下文。不管是哪种方式，每个编码块都有一个选择器作为前缀，指示使用哪个字典。在DINT实现中，选择器（稍微浪费）存储为一个字节整数。有第二种方法可以使用多个词典，这是通过使用b和Ψ的替代组合。例如（见表2），为每个上下文同时考虑b=16和b=8字典可能是有益的，预期（比如）上下文较小的块可以由256元素字典和相应的8位码字更紧凑地处理。同样，选择器用于指示在任何特定块中使用的上下文。此选项不需要额外的内存空间，因为任何上下文的b=8字典都是b=16字典的确切前缀。如前所述，当多个上下文正在使用时，内存消耗可能成为一个问题。如果是这样，则可以使用一组不同的start[]数组来索引单个共享dictionary[]数组，而不是单独存储每个dictionary（请参见图3），使用前面描述的启发式方法将上下文的完整序列重叠存储。最后，在本节中，注意Moffat和Petri[24]在确定上下文时使用块中值作为第二个因素，在使用熵编码器时获得较小的压缩增益。字典编码器也有这种可能，但这里使用的代码词远不是基于熵的，而且所需的字典每个都要大一个数量级，可能会侵蚀可以预期的节省。

图片说明

图4：最佳解析比贪婪解析需要更少的码字的示例。序列“aadbaaaa”是相对于表1（b）中所示的字典来表示的。每个节点下面的成本是从原点到该点的最短路径的长度。图底部显示的解析代价为5；而上面显示的贪婪解析需要6个码字。在这两种情况下，都假定“d”需要一个罕见的符号异常（rse）码字，然后是标识所需符号的补丁码字。

1.5 实验

我们现在给出了基于一系列公共软件的详细实验结果和新的DINT法的实现

数据集和方法论。我们使用包含426 GiB文本的标准Gov2集合；和CCNEWS，CommonCrawl1的免费新闻子集的英文子集，包括2016年1月9日至2018年3月30日期间的新闻文章，遵循Petri和Moffat的方法[28]。两个集合的发布列表都是从Indri搜索引擎中提取的，以确保可重复性，使用的文档排序是从Dhulipala等人的递归图对分重新排序技术派生的。[11] （而不是更常见的URL排序）。每个索引被视为两个整数流，一个包含文档标识符（docid）之间的间隙，另一个包含文档频率（freq）内的间隙，以通常的方式将这两个流拆分为每个术语的过账列表段。这两个数据集的统计数据见表5。所有压缩结果都是针对完整索引的，没有应用停止或其他缩减机制，并且覆盖所有过帐；大小以GiB为单位报告，速率以位/整数为单位。如果需要块大小，则使用B=256，后面的部分块使用Interp[25]表示。对于DINT给出的所有压缩效率结果都包括相应字典的开销。

实现和硬件。所有的实验都基于DS2i框架[26, 27 ]，使用C++ 14实现的方法，并用G++7.2.0编译（使用所有优化）在配备有512 GIB RAM和英特尔Xeon 6144处理器的服务器上，使用32 KIB的L1高速缓存、1024 KIB的L2高速缓存和25344 KIB的L3高速缓存。实验框架和所有代码都可以在https://github.com/jermp/dint。

压缩效果。表6给出了组成这两个集合的索引的四个整数流的基线压缩效率结果，使用了一系列先前的机制，包括：varent GB[10]；varent-G8IU[33]；QMX[36]；Simple16[1]；Opt PFOR[41]；PEF[26]；Clust EF[29]；和Interp[25]。测试的ansversion为每个docid和freq使用一组64个二维med max上下文[24]。表6还包括新的DINT方案，使用了第3节中讨论的两种字典构造机制，贪婪解析，为每个集合的每个流（即，总共四个字典，每个流一个）提供一个字典，并且b=16和Ψ=16（见表2）。可以看出，使用这些标准设置，DINT产生的压缩率比Simple16要好，并且可以与PT PFORapproach获得的压缩率相媲美。两种字典构造机制的效率略有不同，DSF方法与DSV启发式方法相比具有较小但一致的优势。

顺序解码速度。表7比较了DINT的解码速度（使用使用b=16的DSF过程构造的压缩字典，两个值为Ψ）和一系列其他索引压缩方法（包括屏蔽VByte[32]和流VByte[18]的简化机制），这些方法是通过按顺序解码整个索引来测量的。实验的最终结果是，与提供可比或更好效果的方法（表6）相比，DINT更快，并且与速度相似的方法相比，DINT提供更好的压缩效果。Moffat和Petri[23，24]报告ANS解码的速度；根据它们测量的相对性，它将是表7中倒数第二位的；并且基于Pibiri和Venturini[29]，Clust-EF机制的解码速度可能比PEF方法慢，它也位于表的上部（这两种实现方式都与用于生成表7的顺序解码测试线束不兼容）。
注意，一旦序列频率估计被收集，DINT字典的形成和编码是非常快的，并且我们在这个版本的工作中不报告编码时间。

字典性能。图5总结了图1中已经说明的模式，并分别显示了原始索引、压缩索引和字典中目标长度的分布。例如，大约20%的压缩码字是罕见的符号异常，仅占实际Gov2索引中docid的2%；而38%的docid可由频繁的符号异常处理，仅占实际码字的1%。freqs字典匹配比docids流中的长，从而导致更高的压缩率。

最佳解析。表8的第二行显示了使用最佳解析所带来的额外收益。这种增益是以编码时间的少量增加为代价的，但对解码时间没有影响。

多次上下文操作。表8的第三行显示了当每个流总共使用六个字典时产生的额外压缩增益，条件是通过映射上下文=⌈log2log2max⌉每个块中的最大值。每个块需要一个单字节选择器，这部分抵消了增益，但即使如此，还是有一个整体的好处。在第四行中，每个流再添加六个字典，allowingb=8操作（仍然是用Ψ=16）分块，这提供了一个优势。b=8和b=16字典之间的选择是通过使用两个选项测试压缩块来实现的。又一次取得了一致的成果。在第五行中，基于每个块对所有12个可用上下文进行详尽的测试压缩搜索，从而减慢解码时间，但不会以任何方式影响解码吞吐量。进一步的小压缩增益出现。

表9显示了所考虑的各种组合的字典成本。使用压缩字典进行解码比使用矩形字典进行解码更快，因为它的内存占用更为紧凑，但是重叠字符串以进一步节省空间会丢失压缩排列的对齐特性，并增加解码成本。使用多个上下文会导致稍好的压缩，但会由于内存增加和缓存未命中的数量增加而降低解码吞吐量。

图片说明

表5:Gov2和CCNEWS集合的列表、公告和文档数。

图片说明
表6：使用一系列压缩技术的两个测试集合的docid和freq的总索引大小（GiB）和压缩率（每整数位数）。这两个DINT实现都使用b=16和Ψ=16、单个字典和贪婪解析。行是通过减小总索引大小来排序的。

图片说明

表7：在完整索引上测量的顺序解码吞吐量，单位为纳秒/整数。两个数据行都使用b=16和压缩字典。行是通过提高Gov2上docid解码的速度来排序的。

图片说明

图5：使用DSF方法和参数sb=16，Ψ=16，Gov2的docid和freq与每个目标大小相关联的整数、码字和字典条目的百分比。

图片说明

表8:DOCID和FREQ的总索引大小（GiB）和压缩率（每整数位数），使用b=16和Ψ=16。第一行使用带贪婪解析的DINT-DSF；然后添加四个增强，在倒数第二行中，总共使用12个上下文进行最佳解析和穷举搜索，以确定每个块最便宜的上下文。在最后一行，字典索引被假定为输入到一组12个最优熵编码器。除了最后一行（灰色数字）包含计算值而不是测量值之外，这些结果可以直接与表6进行比较。

图片说明
表9:Gov2不同方案和相应解码速度的字典空间（MiB）。在三个“×1”行中，一个字典用于docid，另一个用于freq。在“×6”行中，每个流使用六个字典，其中（最后一行）所有六个字典组合成一个dictionary[]数组，并维护六个start[]数组。

1.6 Conclusions

图6结合表6和表7总结了新的DINT方法的相对性能。当以这种方式呈现时，很明显，我们基于字典的技术代表了反向索引压缩的一个重要的新方法，接近最快解码方法的速度，同时接近最佳方法在所需空间方面的压缩效果。验证吞吐量增益（如第5节所示）是否转化为现实的设置是未来工作的一个明确的领域。我们还计划探索成本较低的频率估计技术，并量化最佳压缩所需精确计数的程度。
除了我们已经取得的巨大进展之外，表8的最后一行显示字典索引流仍然具有大量冗余。熵码的应用将为指数压缩带来更重要的折衷选择，我们也计划探索这种可能性。

2. 主要贡献

论文的主要贡献是开发了一种新的压缩方法，DINT，基于整数序列字典。一个关键的概念是固定值到固定值(fixed-to-fixed)解码，这与之前探索的许多变量到固定值和固定值到变量的方法形成了鲜明的对比。核心思想是每个解码单元消耗一个16位或8位整数码字，并导致从内部码本（字典）到输出缓冲区的固定长度复制操作。这种方法的简单性意味着DINT解码是快速的。此外，DINT还提供了非常好的压缩效果。效率和有效性的共同改善为已知权衡选择的可用范围提供了一个重要的新参考点。基于字典的技术代表了反向索引压缩的一个重要的新方法，接近最快解码方法的速度，同时接近最佳方法在所需空间方面的压缩效果。验证吞吐量增益（如第5节所示）是否转化为现实的设置是未来工作的一个明确的领域。并对未来提出展望，计划探索成本较低的频率估计技术，并量化最佳压缩所需精确计数的程度，为倒排索引的研究提供了新的思路。

3. 论文的长处和短处

本论文的长处在于提供了大量的图表，在原理的介绍和解释上很清晰，措辞上严谨、层次分明而且条理清晰。其次在选题方面很新颖，目前对于倒排索引的研究正处在初级阶段。本文总结了前人的方法，取其精华去其糟粕，创新地提出了自己的方法。此外，提供了大量的数据和表格作为支撑，对优化方法的效率有着强有力的证明。最后还对未来的发展方向进行了设想，对于当前领域的研究者来说有着重要的指导作用。

缺点而言，本文没有对算法的复杂度做过多的证明。实际上，由于本科阶段学习了大量算法和参加算法竞赛，我对于时间复杂度的敏感程度比较强。曾经我不重视理论证明，但是在运筹学课程上我的老师指导我，即使在大量的数据下你的算法效率能够保证正确，如果没有严格的理论证明，说服力不是很强。本文对于算法的复杂度描述得比较简单，虽然一些道理很浅显（如最佳块解析里面如果是2的幂次则最大长度为 $log_2l + 1$ ），如果能引入一些证明过程，我认为结果会更具有说服力。

4. 收获

（1）倒排索引及其优化

在阅读这篇论文的时候，虽然饱含着浓厚的兴趣，但是其实在搜索引擎方面的了解其实不多。我对于倒排索引的理解层面仅仅停留在“有所耳闻”的层面。现在，我对于倒排索引更加了解，倒排索引就是记录每个词条出现在哪些文档，及在文档中的出现位置。在拥有大规模索引数据的搜索引擎中，倒排索引被证明是一种非常高效地数据结构。
其次，本文介绍了许多倒排索引的压缩方法，重点介绍了基于字典的压缩方法，在传统的字典压缩方法上提出了字符串重叠、最佳块解析、多重字典等优化方案。一开始对于我来说这些都是很陌生的领域，通过这篇论文我接触到了这些领域，拓宽了视野，理解倒排索引的设计思想，基于字典、字节对齐的压缩思想，以及论文提到的优化思想能够对我们算法思维进行很好的锻炼，并尝试着将这些思想应用到其他领域中。

（2）英文文献的阅读技巧

在此之前，我阅读的文献大多是中文，如果是英文文献也是篇幅较短的。但是这次的论文考核所给的篇幅是我阅读过的文献里面篇幅最长的。我对于阅读长篇的英文文献不是很擅长，没有相关的经验，特别是这篇论文里充满着学术知识，出现了大量的专业名词，引用了大量的外文期刊。如果想要完全理解这篇论文需要花费大量的时间。我自己一开始阅读的时候是一段一段的读，然后对于不懂的词进行查阅。但是一段一段读下来，发现自己已经忘记前面的内容，效率非常低。

我在向前辈请教后，学会了抓住重点进行阅读，使用高效的翻译软件，先对全篇进行一个大致了解，重点阅读摘要和结论部分。再通过对全篇进行一个粗略的翻译，这样后面再看的时候由于是中文，能够快速的回忆起内容，大大提高了效率。此外，由于这些顶级论文通常是学术界具有丰富经验的教授们所著，在水平上远远高出于我，有时候一些内容对我来说不是很好理解。针对这些问题，我的做法是在知网上查阅有关的硕博论文，硕博论文在深度和阅读难度上比较容易接受。通过硕博论文对基本内容进行一个大致了解后，再阅读本篇论文，不仅收获更多，效率也会大大提高。

（3）代码复现的经验

虽然我在做项目的时候接触过 Github 上的一些开源代码，但是在 Github 上克隆项目进行代码复现是第一次，因为平时编程环境都是在Windows下，所以这次的代码复现有些生疏，经验不足。主要原因在于：

Linux 和 Windows 的 C++有一些区别，调用的API不同，对boost和cmake使用经验较少。
论文的代码风格和类型偏工程类，代码风格跟我自己平时刷题的C++代码有所不同，阅读起来不太习惯。不过自己的C++基础比较扎实，所以这方面影响其实不大。
对于Linux下开发经验较少，仅在开发在线判题系统的时候有过接触。

通过本次代码复现的经历，我克服了以上的困难，积累了宝贵的经验，相信以后复现代码的时候会更加得心应手。

（4）集思广益

在我以前的学习圈子里，大家似乎对于倒排索引都不是很了解，通过学习本次论文并分享到我的博客上，有不少算法爱好者向我提出他们关于倒排索引和基于字典压缩的看法。一定程度上，我向身边的人普及了这个领域的研究，另一方面，在跟他们的交流中，我往往能感受到其他人不同角度的思路，这对于我理解和研究搜索引擎具有重大的意义。

5. 论文的没有解释清楚的地方

首先，上述缺点中提到的，我认为论文在时间复杂度的证明方面篇幅较少，没有很好的解释算法的时间复杂度。
其次，我认为实验说明为什么采用新闻文章作为数据集（新闻数据可能存在着热点，会大量出现一些关键词）、遵循的 Petri 和 Moffat的方法原理没有写清楚，虽然给出了文献参考，但是从读者的角度不是很方便理解，也没有解释为什么要采用这个方法原理。文档排序为什么使用Dhulipala等人的递归图派生，这样做的原理和思路没有解释清楚。总体而言，数据集方面可以进行更详细的描述，让读者觉得数据的来源具有较强的随机性，这样更有说服力。

6. 代码复现

此代码复现过程我也放在自己的博客上面，获得了一定的阅读量和点赞数

6.1 安装cmake (>= 2.8):

$ sudo apt install cmake

6.2 安装boost

$ apt-cache search boost
$ sudo apt-get install libboost-all-dev

搜到所有的boost库,然后安装相应的库

6.3 clone 项目

$ git clone https://github.com/jermp/dint

6.4 Building the code

$ git submodule init
$ git submodule update
$ mkdir build
$ cd build
$ cmake .. -DCMAKE_BUILD_TYPE=Release
$ make -j[number of jobs] // 这里我采用 make -j2

注：这一步原本采用单核2GB的学生机，因为实在跑不动，临时租了一个四核8GB的服务器

6.5 建立索引

$ Usage ./create_freq_index:
$       <index_type> <collection_basename> [output_filename] [--check]

$ ./create_freq_index single_rect_dint ../test/test_data/test_collection single_rect_dint.bin // 矩形字典(1)
$ ./create_freq_index single_packed_dint ../test/test_data/test_collection single_packed_dint.bin // 对齐/压缩字典(2)
$ ./create_freq_index multi_packed_dint ../test/test_data/test_collection multi_packed_dint.bin // 多次对齐/压缩字典(3)
$ ./queries single_packed_dint and single_packed_dint.bin < ../test/test_data/queries //performes the boolean AND queries contained in the data file queries over the index serialized to single_packed_dint.bin.(4)

6.6 结果分析

（1）矩形字典

root@iZbp13o6yrkkck8a5gw2e4Z:~/dint/build# ./create_freq_index single_rect_dint ../test/test_data/test_collection single_rect_dint.bin
2020-06-26 14:56:57: building or loading dictionary for docs...
2020-06-26 14:56:57: DONE
2020-06-26 14:56:57: building or loading dictionary for freqs...
2020-06-26 14:56:57: DONE
2020-06-26 14:56:57: Processing 10000 documents...

0%   10   20   30   40   50   60   70   80   90   100%
|----|----|----|----|----|----|----|----|----|----|
***************************************************

2020-06-26 14:56:57: Encoded 113306 sequences, 3327520 postings
2020-06-26 14:57:00: Usage distribution for docs:
rare: 2 (0.00305176%)
entries of size 1: 6539(9.97772%)
entries of size 2: 21422(32.6874%)
entries of size 4: 24429(37.2757%)
entries of size 8: 10441(15.9317%)
entries of size 16: 2698(4.11682%)
freq.: 5 (0.00762939%)
2020-06-26 14:57:00: Usage distribution for freqs:
rare: 2 (0.00305176%)
entries of size 1: 833(1.27106%)
entries of size 2: 8114(12.381%)
entries of size 4: 24011(36.6379%)
entries of size 8: 18225(27.8091%)
entries of size 16: 14346(21.8903%)
freq.: 5 (0.00762939%)
2020-06-26 14:57:00: single_rect_dint collection built in 2.59589 seconds
{"type": "single_rect_dint", "worker_threads": 4, "construction_time": 2.59589, "construction_user_time": 2.56776}
<TOP>: 12749754
    m_params: 5
    m_endpoints: 101096
        m_bits: 101088
    m_lists: 3735725
    m_docs_dict: 4456456
        m_table: 4456456
    m_freqs_dict: 4456456
        m_table: 4456456
2020-06-26 14:57:00: Documents: 2470345 bytes, 5.93919 bits per element
2020-06-26 14:57:00: Frequencies: 1265380 bytes, 3.04222 bits per element
2020-06-26 14:57:00: Index size: 0.0118741 [GiB]
{"type": "single_rect_dint", "size": 12749754, "docs_size": 2470345, "freqs_size": 1265380, "bits_per_doc": 5.93919, "bits_per_freq": 3.04222}

（2）对齐/压缩字典

root@iZbp13o6yrkkck8a5gw2e4Z:~/dint/build# ./create_freq_index single_packed_dint ../test/test_data/test_collection single_packed_dint.bin
2020-06-26 15:12:54: building or loading dictionary for docs...
2020-06-26 15:12:54: DONE
2020-06-26 15:12:54: building or loading dictionary for freqs...
2020-06-26 15:12:54: DONE
2020-06-26 15:12:54: Processing 10000 documents...

0%   10   20   30   40   50   60   70   80   90   100%
|----|----|----|----|----|----|----|----|----|----|
***************************************************

2020-06-26 15:12:54: Encoded 113306 sequences, 3327520 postings
2020-06-26 15:12:56: Usage distribution for docs:
2020-06-26 15:12:56: Usage distribution for freqs:
2020-06-26 15:12:56: single_packed_dint collection built in 2.16824 seconds
{"type": "single_packed_dint", "worker_threads": 4, "construction_time": 2.16824, "construction_user_time": 2.13624}
<TOP>: 7154382
    m_params: 5
    m_endpoints: 101096
        m_bits: 101088
    m_lists: 3735725
    m_docs_dict: 1268264
        m_offsets: 262152
        m_table: 1006112
    m_freqs_dict: 2049276
        m_offsets: 262152
        m_table: 1787124
2020-06-26 15:12:56: Documents: 2470345 bytes, 5.93919 bits per element
2020-06-26 15:12:56: Frequencies: 1265380 bytes, 3.04222 bits per element
2020-06-26 15:12:56: Index size: 0.00666304 [GiB]
{"type": "single_packed_dint", "size": 7154382, "docs_size": 2470345, "freqs_size": 1265380, "bits_per_doc": 5.93919, "bits_per_freq": 3.04222}

（3）多次对齐/压缩字典

root@iZbp13o6yrkkck8a5gw2e4Z:~/dint/build# ./create_freq_index multi_packed_dint ../test/test_data/test_collection multi_packed_dint.bin
2020-06-26 15:14:02: building or loading dictionary for docs...
2020-06-26 15:14:02: DONE
2020-06-26 15:14:02: building or loading dictionary for freqs...
2020-06-26 15:14:02: DONE
2020-06-26 15:14:02: Processing 10000 documents...

0%   10   20   30   40   50   60   70   80   90   100%
|----|----|----|----|----|----|----|----|----|----|
***************************************************

2020-06-26 15:14:02: Encoded 113306 sequences, 3327520 postings
2020-06-26 15:14:21: Usage distribution for docs:
2020-06-26 15:14:21: Usage distribution for freqs:
2020-06-26 15:14:21: multi_packed_dint collection built in 19.1152 seconds
{"type": "multi_packed_dint", "worker_threads": 4, "construction_time": 19.1152, "construction_user_time": 19.0864}
<TOP>: 13890400
    m_params: 5
    m_endpoints: 96248
        m_bits: 96240
    m_lists: 3006531
    m_docs_dict: 5804848
        m_start_offsets: 32
        m_offsets: 567252
        m_table: 5237564
    m_freqs_dict: 4982752
        m_start_offsets: 32
        m_offsets: 605364
        m_table: 4377356
2020-06-26 15:14:21: Documents: 1981821 bytes, 4.76468 bits per element
2020-06-26 15:14:21: Frequencies: 1024710 bytes, 2.4636 bits per element
2020-06-26 15:14:21: Index size: 0.0129364 [GiB]
{"type": "multi_packed_dint", "size": 13890400, "docs_size": 1981821, "freqs_size": 1024710, "bits_per_doc": 4.76468, "bits_per_freq": 2.4636}

（4） Vroom environment

vroom主要用来测试编码解码的速度，收我们对所有收集的序列进行编码：

./encode single_packed_dint ../test/test_data/test_collection.docs --dict dict.test_collection.docs.single_packed.DSF-65536-16 --out test.bin

得到下列结果：

root@iZbp13o6yrkkck8a5gw2e4Z:~/dint/build# ./encode single_packed_dint ../test/test_data/test_collection.docs --dict dict.test_collection.docs.single_packed.DSF-65536-16 --out test.bin
2020-06-26 16:29:15: ./encode single_packed_dint ../test/test_data/test_collection.docs --dict dict.test_collection.docs.single_packed.DSF-65536-16 --out test.bin
2020-06-26 16:29:15: preparing for encoding...
2020-06-26 16:29:15: encoding docs...

0%   10   20   30   40   50   60   70   80   90   100%
|----|----|----|----|----|----|----|----|----|----|
***************************************************
2020-06-26 16:29:16: encoded 113306 lists
2020-06-26 16:29:16: encoded 3327520 integers
2020-06-26 16:29:16: 0.00227213 [GiB]
2020-06-26 16:29:16: bits x integer: 5.86547
{"filename": "../test/test_data/test_collection.docs", "num_sequences": "113306", "num_integers": "3327520", "type": "single_packed_dint", "GiB": "0.00227213", "bpi": "5.86547"}
2020-06-26 16:29:16: writing encoded data...
2020-06-26 16:29:16: DONE

再对它们解码

$ ./encode single_packed_dint ../test/test_data/test_collection.docs --dict dict.test_collection.docs.single_packed.DSF-65536-16 --out test.bin

最后得到以下结果：

root@iZbp13o6yrkkck8a5gw2e4Z:~/dint/build# ./decode single_packed_dint test.bin --dict dict.test_collection.docs.single_packed.DSF-65536-16
2020-06-26 21:33:59: ./decode single_packed_dint test.bin --dict dict.test_collection.docs.single_packed.DSF-65536-16
2020-06-26 21:33:59: Dictionary memory: 1.20951 [MiB]
2020-06-26 21:34:00: decoding...
2020-06-26 21:34:00: elapsed time 0.0188706 [sec]
2020-06-26 21:34:00: 5.67106 [ns] x int
2020-06-26 21:34:00: 176333826 ints x [sec]
{"filename": "test.bin", "num_sequences": "113306", "num_integers": "3327520", "type": "single_packed_dint", "tot_elapsed_time": "0.0188706", "ns_x_int": "5.67106", "ints_x_sec": "176333826"}

（5）结果比较

基于上述的实验结果，可以列出下表

Index	docs[bpi]	freqs[bpi]
single_rect	5.93919	3.04222
single_packed	5.93919	3.04222
multi_packed	4.76468	2.4636

发现代码复现结果跟作者所做的实验结果相差不大。部分偏差主要来自于运行环境上的区别：

作者的配置: Intel i7-7700, 3.6GHz, Linux 4.4.0, 64bits 个人电脑
我的配置: 4核 CPU, 8GB 内存 Ubuntu 20.04 64bits 云服务器

7. 总结和未来设想

互联网信息的不断丰富所带来的索引数据的持续增加，倒排索引压缩技术能有效降低索引数据的存储和传输开销，因此，倒排索引压缩技术的研究具有重要的意义。我通过阅读国内外相关研究的论文，发现许多倒排索引压缩技术评估和优化工作主要关注对整数序列的压缩，但是对于现有倒排索引压缩算法在搜索引擎系统应用中存在的倒排链表磁盘分段存储、多类倒排信息交错压缩和压缩数据自索引结构等实际情况没有做过多深入的研究。针对倒排索引压缩算法在存储和查询应用中存在的实际问题展开理论方法研究与性能测试。
这些问题的解决有助于推动机器字对齐压缩算法在倒排索引存储和查询中的广泛应用，有利于解决海量磁盘压缩索引数据的快速查询访问问题，对提升各类搜索引擎的系统性能和服务质量具有重要的实际意义。从我阅读的文献来看，倒排索引压缩算法当前和未来的研究方向主要有以下几个方面：
（1）利用新的指令集架构优化倒排索引压缩算法，从而进一步提升压缩和解压性能。我在参与算法竞赛的时候曾经接触过指令集的相关优化，普通个人电脑一般一秒内能够运算次数大约是1e8级别。因此，一般来说 $O(n^2)$ 级别的时间复杂度算法一秒内只能运算1e4规模的数据，但是在加入指令集的优化下，能够在一秒内用 $O(n^2)$ 的算法运算1e6的数据。由此可以看出，随着处理器技术的不断发展，新的SIMD指令集（SSE或者AVX指令集）或者计算单元（GPU芯片或者芯片加速器）等的更新能够带来新的指令集并行化策略，对倒排索引压缩算法的性能优化具有重大意义。通过汇编指令级别来设计整数序列的存储布局，并利用内存和寄存器载入策略、指令集的比特位操作等技术能够提升倒排索引整数序列的并行化压缩和解压处理性能。
（2）倒排索引压缩算法实际应用上，由于支持随机访问的压缩倒排链表可以减少不必要的内存数据加载，提升搜索引擎中压缩倒排索引的查询性能；另外还可以在倒排链表的求交操作（如SvS算法）中根据AND查询策略来调整或者改进压缩算法。搜索引擎查询中对不同倒排链表或者倒排链表数据段访问频率不同，可以根据访问频率调整压缩方式，实现更加细粒度的性能调节，在权衡索引大小、压缩速度和解压速度等性能指标的基础上，得到更好的时空效率。
（3）在传统的数据压缩领域利用新技术和新理论提升倒排索引的算法性能甚至代替倒排索引。如本文提到的利用Plurally Parsable 理论基于词典的倒排索引压缩，南开-百度联合实验室上面论文提到的Context-free Grammar（文法压缩），甚至利用BitFunnel代替倒排索引。