整数的最佳压缩算法是什么？

Question

我需要一个最好的压缩算法来处理一组随机数。

列表示例：

224.19
225.57
226.09
222.74
222.20
222.11
223.14
540.56
538.96
540.14
540.44
336.45
338.47
340.78
156.73
160.02
158.56
156.23
55.08
56.33
54.88
53.45

我可以跳过小数部分。我有一大串数字，就像上面给出的例子一样，所以需要压缩。

你能推荐些什么吗？

- Waqas

---

这些数字看起来一点也不随机。你可以尝试将它们存储在块中，每个块有一个基数和一个要加到该基数上的数字。 - Sirko

好的随机数是无法被压缩的。 - AlexWien

@Waqas 为什么你想要压缩它们？你能详细解释一下你的问题吗？ - Freak

@Sirko 这些数字是以百万计的，并且它们不太随机，但是它们确实会发生变化。例如，有一些数在 230 到 240 的范围内，下一个模式可能是其他数字范围等等。 - Waqas

@AlexWien 我们有随机数，但它们有模式。例如，(540-545) 有245个数字，(230-240) 有100个数字，(340-350) 有400个数字，等等。 - Waqas

Answer 1

不要使用浮点数，使用整数并带有某种控制字符来表示小数点（如果需要），但如果可以省略，则更好。请参考 变量字节编码。它的优点是对于小整数，您不需要分配64位内存。如果您的数字彼此之间存在某种依赖关系，则可以查看 Delta编码-它存储两个数字之间的差异而不是数字本身。变量字节编码和Delta编码被用作谷歌和任何其他涉及搜索引擎的公司压缩倒排列表索引的核心方法。

- XapaJIaMnu

---

@XapaJlaMnu 感谢您的回答。我们已经应用了差分压缩技术，并获得了平均67％的压缩率。我正在研究将增量编码和可变字节编码应用于差分压缩数据。在应用这些编码后，让我们看看是否会有所改善。 - Waqas

Answer 2

如评论中所述，你的数字远非随机。

首先，因为所有数字都可以用小数点后两位来描述，所以我建议先移除小数点。在压缩时将所有数字乘以100，在解压缩时将其除以100。

其次，我建议通过从上一个数字中减去当前数字来对数字进行增量编码。第一个数字不变。重构很容易完成。最终你会得到：

22419, 138, 52, -335, -54, -9, 103, 31742, -160, 118, 30, -20399,
202, 231, -18405, 329, -146, -233, -10115, 125, -145, -143

进行编码。现在我们正在取得进展。通常情况下，我们有很小的增量，偶尔有大的跳跃。然后使用可变长度整数对它们进行编码。增量的直方图将有助于构建该代码。一个简单的例子是每字节7位，高位为1表示整数结束。在位级别上更复杂的方案可能更优，具体取决于概率分布。

- Mark Adler