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

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

我可以跳过小数部分。我有一个巨大的数字列表，就像上面给出的例子一样，这就是为什么它需要被压缩。

你能推荐一些东西吗？

Answer 1

不要使用浮点数，如果需要，可以使用带有某种控制字符的整数来表示小数点，但如果你可以跳过它，那就更好了。

看看可变字节编码。它的优点是您不需要为小整数分配 64 位内存。

如果您的数字彼此之间存在某种依赖性，您可以查看Delta 编码- 它存储两个数字之间的差异，而不是数字本身。

可变字节编码和增量编码被谷歌和任何其他与搜索引擎打交道的公司用作压缩倒排列表索引的核心方法。

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 位，高位是一个表示整数结束的位。取决于概率分布，比特级更复杂的方案可能更优化。