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

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编码 - 它存储两个数字之间的差异而不是数字本身.

可变字节编码和增量编码被用作由Google和任何其他处理搜索引擎的公司压缩反向列表索引的核心方法.

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 表示整数的结尾。根据概率分布，比特级更复杂的方案可能更优化。