快速压缩

一次处理4个数字的压缩。可扩展以优雅地处理数百、数千，甚至更多。

该算法专为需要内存压缩（例如面向数据的设计）的用例而设计。

也就是说，它被设计用于数据量随时间变化很大的用例，并且经过微调，即使那个数字意外地很低，也能表现得很好。

该算法和实现经过优化，以在压缩和解压缩时非常快速，适用于实时应用程序。

在您的应用程序中使用此压缩的优点预计将是

• 通过降低数据占用，提高速度来减少缓存未命中
• 减少内存占用

注意，这些说法尚待验证

压缩方案

该方案一次压缩4个数字，通过采用空值抑制、差分和偏移编码。

一个字节，总是第二个字节将用于经典的4个数字组varint编码。例如，1个字节存储4个整数的长度，执行空值抑制。我们还执行自定义差分编码：最初4个数字将被排序。然后我们存储到第一个数字的字节大小偏移量（偏移量 $ \in {0, 0xff, 0xffff, 0xffffff }$）。对于剩余的数字 $n+1$，我们只对数字 $n$ 进行编码。

该方案每组4个数字至少占用$(2+4)$字节，但少于$(2+16)$字节。

排序顺序编码

排序顺序可以表示为{0, 1, 2, 3}的排列。我们需要2位来存储第一个索引。我们需要 $ \lceil log_2(3) \rceil =2 $ 位来存储第二个索引（可以是4个中的3个）。我们需要1位来编码第三个数字（只有2种选择）。我们不需要编码最后一个位置，这个信息是冗余的。

编码顺序使用字节的前5位，如下所示： [000aabbc] 其中a编码第一个索引，以此类推。

存储初始偏移量

我们还有4位来存储我们的偏移量。这意味着我们有8个偏移量选项。位到偏移量的映射如下

$$ 000_b \mapsto 0_x $$ $$ 001_b \mapsto ff_x $$ $$ 010_b \mapsto fff_x $$ $$ 011_b \mapsto ffff_x $$ $$ 100_b \mapsto fffff_x $$ $$ 101_b \mapsto ffffff_x $$ $$ 110_b \mapsto fffffff_x $$ $$ 111_b \mapsto ffffffff_x $$

这些位 xy 存储在排序顺序相同的字节中，如下所示：0xyaabbc

改进

执行 delta 编码后，数字的最大长度受到严重限制。

我的直觉是，由于排序 delta 编码，我们永远不需要为每个数字使用 4 个字节。待办事项：证明这一点并证明最大字节数。

第二个表示排序顺序的数字编码比其他数字的熵要低。

我认为我可以使用最后一个数字来编码 64 位数字。