整数时间序列压缩

Question

是否有一个众所周知的用于（正）整数流/时间序列压缩的记录算法，它将：

• 具有可变位长度
• 致力于三角洲

我的输入数据是来自传感器（更具体地说是 Arduino 读出的 TMP36）的温度测量值流。物理上不可能在测量之间发生大的跳跃（传感器的时间常数）。因此，我认为我的压缩算法应该适用于增量（设置流开始的基础，然后仅与下一个值不同）。因为间隙是有限的，所以我想要可变的位长度，因为低于 4 的差异适合 2 位，低于 8 适合 3 位等等...但是在流中告诉下一个增量的位大小和例如，仅处理 3 位增量并仅在较大时才告知大小。

知道还有什么算法可以解决问题吗？

Answer 1

使用可变长度整数对值之间的增量进行编码，并将其提供给zlib进行压缩。

Answer 2

您可以使用带有 delta 或 delta of delta 编码的整数压缩方法，如TurboPFor Integer Compression中使用的那样。如果增量值非常小，也可以使用伽玛编码。

Answer 3

首先存在不同的格式。我首先要做的一件事就是去掉这个标志。当考虑压缩时，标志通常会分散注意力。我通常使用的方案是每个正值都是 2*v，每个负值都是 2*(-v)-1。所以 0 = 0、-1 = 1、1 = 2、-2 = 3、2 = 4...。

由于使用该方案，您没有像 0b11111111 = -1 这样的内容，前导位都消失了。现在你可以考虑如何压缩这些符号/数字。您可以做的一件事是创建一个代表性样本并使用它来训练静态霍夫曼代码。这应该在您的片上限制范围内是可能的。另一种更简单的方法是使用霍夫曼码来确定位长度并将这些位写入流。所以 0 = 位长 0, -1 = 位长 1, 2,3 = 位长长度 2, ... 。通过使用霍夫曼代码来描述这个位长度，你就变成了非常紧凑的文字。

我通常使用混合物。我使用最频繁的符号/值作为原始值，并通过使用实际值的位长度+位模式来使用不那么频繁的数字。这样您就可以保持紧凑，并且不必处理过多的表（64 位长度可能只有 64 个符号）。

还有其他方案，例如前导位，例如每个字节的第一位（或最高位）标记该值的最后一个字节，因此只要设置该位，就会有另一个字节表示整数。如果为零，则为该值的最后一个字节。

我通常为此目的训练静态霍夫曼代码。它很简单，您甚至可以将编码和解码变成源代码/从您的代码中生成源代码（只需创建 ifs/switch 语句并将表作为数组写入代码中）。

Answer 4

解决这个问题的当前技术水平是pcodec。它压缩整数等数值序列，通常比其他方法至少提高 30% 的压缩率。它会自动检测并应用最佳的增量编码顺序作为内置功能。

CLI 示例：

pcodec compress \
  --csv my.csv \
  --col-name my_col \
  out.pco

Rust API 示例：

let my_nums: Vec<i64> = ...
let bytes: Vec<u8> = pco::standalone::auto_compress(&my_nums);
println!("compressed down to {} bytes", bytes.len());

由于您的数据来自温度传感器，因此您的数据应该非常平滑，您甚至可以考虑高于 1 的 delta 阶（例如 delta 阶 2 是“delta-of-delta”）。