java - 如何压缩整数序列？

Question

我有一个数组，其中包含 -255 到 +255 范围内的数据。例如，数组可以是这样的：

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

在这里，必须在解压缩时保留顺序，例如在第 1 项 234 之后，必须有 56 来。

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

Answer 1

-255 到 255 的范围表示 511 个值 -> 9 位。如果单独取符号，则符号为 1 位，值为字节。

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

在一个单独的区域（一个长数组，或者可能是一个字节数组）中，存储符号位。

Answer 2

如果数据中确实没有模式，那么有用的压缩算法是不可能的。甚至不要费心尝试！

当然，在这种情况下，因为所有数字都在有限范围内，所以您确实在位中有一个模式 - 即您的高位要么全为 0（正），要么全为 1（负）。

因此，如果您想合理有效地压缩（假设您有足够长的数字数组使其值得），则像 zip 这样的标准压缩算法将起作用。

或者，您可以利用您有效地使用 9 位数字这一事实。因此，您可以通过将数字排列为一长串 9 位块并将其放入字节数组中来推出自己的压缩算法。

Answer 3

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

例如，Elias 伽玛编码和指数哥伦布编码。一般的想法是，小数字只需要很少的比特进行编码。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. 从输入流中读取并计算前导零位（直到找到非零位）-> zero_bits_count

2. 从输入流中读取下一个（ zero_bits_count + 1 ）位 ->二进制

3. 将二进制转换为十进制

4. 返回（十进制 - 1）

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

等等

Answer 4

如果数字本质上是随机且均匀分布的，并且要保留顺序，那么您可以做的最好的事情是每个符号大约 9 位。在 9 位时，将不使用单个 9 位值，即 2 的补码表示中的 -256。这很方便，因为您可以使用它作为结束符号来标记列表的结尾。然后你还编码了列表的长度，无论如何都需要它。