1

我有一个向量，我在其中保存一个递增的数据。通常，向量的每个元素都是一个 64 位长的变量。但是，两个连续元素之间的差异很可能非常小，因此例如我们可以有一个如下的序列。

1, 34, 37, 42, 45, 1098, 1200, 1211, 1938

压缩此数据的最佳方法是什么。只保留差异是否理想，并有一个标题字节来定义差异有多大，无论它只是一个字节、字、双字等，还是有更好的方法来压缩这种增量数据？

编辑

我需要在线压缩，即同时将数据放入向量中。您可以假设一个动态扩展的向量。

4

2 回答 2

4

当增量通常很小时，这是一个非常简单的策略：

  1. 如果增量<2**7，则将其作为最高位设置为零的单个字节发出：

    0xxxxxxx

  2. 否则，如果增量 <2**14，则将其作为两个字节发出，最高位分别为 1 和 0：

    1xxxxxxx 0xxxxxxx

  3. 以明显的方式将其扩展到更大的增量。第八位设置为 1 表示“等待，还有更多”。零表示“整数结束”。

我记得在某些 RFC 或 RFC 中看到为 bigints 建议了这种编码方案internet-draft，但我现在似乎无法检索它。或者，您可以重用 UTF-8 编码方案来改进错误检测，但代价是编码效率较低（如果您想超越 64 位整数，您可能必须对其进行扩展）。

于 2012-06-21T09:47:46.747 回答
0

听起来你需要一些东西（正如你自己已经说过的那样），比如差分调制。也许这会给你一些灵感：http ://en.wikipedia.org/wiki/Differential_pulse-code_modulation

于 2012-06-21T09:47:26.830 回答