algorithm - 实现动态位域

Question

关键是在下面的问题中会发生什么。

-int 数组的元素，比方说 5、5、6、7、9 位长(它们不同)。

我如何对其进行编码，使其占用 32 位而不是通常的 160 位？

我还想说，在另一边(解码端)我不知道每个元素有多大。那么，如果我收到这样的数据，我怎么可能解码，或者换句话说，我如何才能以一种可以轻松解码的方式进行初始编码？

Answer 1

如果事先知道这些数字中的位分布，那就很简单:只需将数组中每个元素的位放在结果 int 中的正确位置，就像这样(例如在 C++ 代码中):

unsigned int encoded = (val[0]) | (val[1] << 5) | (val[2] << 10) |
              (val[3] << 16) | (val[4] << 23);

...假设 val 是一个 int 数组，它包含 5、5、6、7 和 9 位长的数字。解码同样简单:

int decoded[5];
decoded[0] = encoded & 0x1F;
decoded[1] = (encoded >> 5) & 0x1F;
decoded[2] = (encoded >> 10) & 0x3F;
decoded[3] = (encoded >> 16) & 0x7F;
decoded[4] = (encoded >> 23);

如果事先不知道位长，唯一已知的事实是，它们的位长加起来是 32，那么，对于一般情况，不可能将它们编码成最大值32位；因为您已经需要这些位数来存储实际数字；但是您还必须知道编码数字的位长度；为此，您需要额外的存储空间。这一切都是有效的，前提是这些数字不是多余的并且可以被压缩。

当然有办法使每个整数短于 4 个字节；根据要处理的数字的确切属性，一种或另一种算法可能更适合；以下是一些可能的算法的简短列表:

• 如果您知道整数的最大长度为 9 位，则可以使用上面显示的简单方法，但偏移量为 9 来存储数字；使用这种方法，5 个值将减少到 45 位。
• 在每个元素之前有一个长度指示符是另一种可能性(如 Robert Rouhani 所建议)
• 另一个例子是在 this question 中提出(使用 Dlugosz' Variable-Length-Integer )
• 您也可以使用 Variable-length quantity .

前两种方法的缺点是它们只能表示固定的最大位数。这种处理属于压缩领域，要进行更理论化的分析，请务必阅读有关该主题的一些文献；这里特别感兴趣的是Universal Codes ，正如 Kaganar 的评论中指出的那样；上面列表中的最后两个算法就是这样的通用代码。对于 5、5、6、7 和 9 位的 5 个值的示例输入，它们应该使您降低到 48 位(对于 4 个小于 8 位的值，4 次 8 位，对于 9 位，1 次 16 位数字)。这两种方法相对于列表中其他方法的优势在于它们适用于任意大数；可能还有其他更适合您目的的 Universl 代码，请确保也检查其他的。