如何压缩整数序列？

Question

我有一个数组,其中包含-255到+ 255.eg范围内的数据.数组可以是这样的:

  int data[]={234,56,-4,24,56,78,23,89,234,68,-12,-253,45,128};

这里,必须在解压缩时保留顺序,例如在第一个术语234之后,必须来56.

那么,有什么方法可以压缩任何无法观察到任何重复模式的任意数字序列？

Answer 1

范围-255到255表示511个值 - > 9位.如果单独使用符号,则1位用于符号,1位用于值.

您可以将数组编写为字节数组,每个字节值将是相关int的绝对值.

在单独的区域(长或可能是字节数组)中,存储符号位.

Answer 2

如果数据中确实没有模式,则无法使用有用的压缩算法.甚至不打扰尝试!

当然,在这种情况下,因为所有数字都在一个受限制的范围内,所以你的位数确实有一个模式 - 即你的高位全部为0(正)或全1(负).

因此,如果您想要合理有效地压缩(假设您拥有足够长的数字数组以使其值得),则像zip这样的标准压缩算法将起作用.

或者,您可以利用有效使用9位数的事实.因此,您可以通过将数字布置为9位块的长流并将其放入字节数组来推广自己的压缩算法.

Answer 3

在您的情况下（当无法观察到重复模式时），可变长度编码可能会对您有所帮助。

例如，Elias gamma-coding和Exponential-Golomb coding。一般的想法 - 是小数字只需要编码几位。Exp-Golomb 编码用于 H.264/MPEG-4 AVC 视频压缩标准。用它对序列进行编码和解码非常容易，实现这种编码也不是很难。

编码所有整数的方法是建立一个双射，将整数 (0, 1, -1, 2, -2, 3, -3, ...) 映射到 (1, 2, 3, 4, 5, 6 , 7, ...) 在编码之前。

例如：

序列（双射后）[ 0, 2, 5, 8, 5, 2 ]将被编码为 101100110000100100110011-正如您所看到的 - 此序列中没有重复模式，但它仅用 24 位编码。

解码过程简述：

1... -> no leading zeros, zero_bits_count = 0 -> read next 1 bit -> [1]... -> [1] is 1 -> 1 - 1 = 0

011... -> [0] - one leading zero, zero_bits_count = 1 -> read next 2 bits -> [11]... -> [11] is 3 -> 3 - 1 = 2

00110... -> [00] - two leading zeros, zero_bits_count = 2 -> read next 3 bits -> [110]... -> [110] is 6 -> 6 - 1 = 5

等等。