如何压缩一系列整数？

Question

我是一位有用的助手，可以为您进行文本翻译。

我有一个包含在-255到+255范围内数据的数组。例如，该数组可能像这样：

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

在这里，解压缩时必须保留顺序，例如在第一个术语234之后，必须出现56。

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

- Debadyuti Maiti

---

这正是zip、gz以及其他压缩工具解决的问题。 - Alexander Kjäll

使用通用的压缩算法，例如Zip。 - nhahtdh

除了范围之外，你有关于数字序列的任何信息吗？如果它是在该范围内基本随机、均匀分布，并且需要保留顺序，那么你能做到的最好的是每个条目约9位。 - Mark Adler

Answer 1

-255到255的范围意味着有511个值-> 9位。如果将符号单独考虑，则为1位用于符号和1个字节用于值。

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

在单独的区域（长整型或字节数组）中存储符号位。

- SJuan76

---

这是编码而不是压缩；唯一的压缩方式是消除冗余。 - Nahuel Fouilleul

如果我可以给评论点个踩，我会这么做。不必纠结：输出的比输入的占用更少的位吗？是的。 - J. Holmes

@NahuelFouilleul 压缩只是编码以使用更少的空间；除此之外，这并没有消除冗余吗？他正在消除每个值不需要的23个额外位 - 这是我所知道的冗余的定义。 - obataku

Answer 2

如果数据中真的没有任何模式，那么一个有用的压缩算法是不可能存在的。别浪费时间了！

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

标准的压缩算法比如zip会因此而工作，如果你想要相对有效地压缩（假设你有足够长的数字数组使其值得）。

或者，你可以利用你实际上使用的9位数字这一事实。因此，你可以通过将数字布置成一个长的9位块流，并将其放入一个字节数组中来编写自己的压缩算法。

- mikera

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. 从输入流中读取并计算前导零位数（直到找到非零位）->zero_bits_count
2. 从输入流中读取下一个(zero_bits_count+1)位 -> binary
3. 将binary转换为十进制数
4. 返回 (decimal-1)

1... -> 没有前导零，zero_bits_count = 0 -> 读取下一个 1 位 -> [1]... -> [1] 是 1 -> 1 - 1 = 0

011... -> [0] - 一个前导零，zero_bits_count = 1 -> 读取下一个 2 位 -> [11]... -> [11] 是 3 -> 3 - 1 = 2

00110... -> [00] - 两个前导零，zero_bits_count = 2 -> 读取下一个 3 位 -> [110]... -> [110] 是 6 -> 6 - 1 = 5

等等。

- stemm

---

但在这个范围内 [0, 2, 5, 8, 5, 2]，所有数字都小于16。因此，每个数字需要4位。即总共需要6*4=24位。那么，压缩在哪里呢？ - Debadyuti Maiti

如果值是均匀分布的，那么可变长度编码将使数据每个值扩展到大于9位。只有当较小的值比较大的值更有可能出现时，可变长度编码才会有用。 - Mark Adler

@Debadyuti Maiti 我同意Mark Adler的观点。这只是一种压缩序列的方法，其中有许多小值（但也存在大值）。在这种情况下，与使用预定义长度的编码相比，这将更好（因为您需要扩展大值的代码长度，并且它也会应用于小值）。 - stemm

@Debadyuti Maiti 另一个例子：使用“可变长度”编码[0,2,5,8,5,2,255,3,4,20] ->将被编码为“60位”序列。但如果您决定为每个值使用固定长度的位串->您将需要“8位每个值”（因为值为255）。并且[0,2,5,8,5,2,255,3,4,20]将被编码为“80位”序列。只有当小值频繁出现时才会获得好处。 - stemm

Answer 4

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

- Mark Adler