压缩唯一的数据流

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位整数上工作得更好,它仍然可以编码流中突然出现的完全不同的整数.你节省了处理自己打包的麻烦,因为一切都是一个int大小的数量.

当你想要解压缩时:

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

这也是一个简单算法的优点,它将真正,非常快地运行,因为它只是异或.

Answer 2

你考虑过游程编码吗？

或者尝试这样:您可以存储数字之间的差异,而不是自己存储数字.1 1 2 2 2 3 5变为1 0 1 0 0 1 2.现在,您必须编码的大多数数字都非常小.要存储一个小整数,请使用8位整数,而不是在大多数平台上编码的32位整数.这就是4的因素.如果你确实需要为更大的间隙做好准备,请指定8位整数的高位来说"这个数字也需要接下来的8位".

您可以将其与行程编码相结合,以获得更好的压缩率,具体取决于您的数据.

这些选项都没有特别难以实现,并且它们都运行得非常快且内存非常少(与bzip相反).