压缩独特的数据流

Question

我有大量的整数数组。每一个都有几千个整数，每个整数一般都和它前面的一样，或者只有一两位不同。我想尽可能缩小每个阵列以减少我的磁盘 IO。

Zlib 将其缩小到其原始大小的 25% 左右。这很好，但我认为它的算法不是特别适合这个问题。有谁知道可能对此类信息表现更好的压缩库或简单算法？

更新:将 zlib 转换为 xor deltas 数组后，将其缩小到原始大小的 20% 左右。

Answer 1

如果大多数整数确实与前面的相同，并且符号间差异通常可以表示为单个位翻转，那么这听起来像是 XOR 的工作。

以输入流为例:

1101
1101
1110
1110
0110

和输出:

1101
0000
0010
0000
1000

一些伪代码

compressed[0] = uncompressed[0]
loop
  compressed[i] = uncompressed[i-1] ^ uncompressed[i]

我们现在已经将大部分输出减少到 0，即使高位发生变化。您使用的任何其他工具中的 RLE 压缩将在此方面发挥作用。它将在 32 位整数上工作得更好，并且它仍然可以对流中弹出的完全不同的整数进行编码。您省去了自己处理位打包的麻烦，因为所有东西都是整数大小的数量。

当你想解压时:

uncompressed[0] = compressed[0]
loop
  uncompressed[i] = uncompressed[i-1] ^ compressed[i]

这也有一个简单的算法的优点，它会运行得非常非常快，因为它只是 XOR。