压缩随机32位整数：我们离香农熵有多近？

Question

我开发了一种无损压缩算法，将32位整数（频率/概率未知）压缩到每整数31.95824位（对于较小的值，它的效果更好，就像大多数压缩算法一样）。显然，不可能将均匀分布的随机数据压缩到小于其未压缩大小。

因此，我的问题是，假设32位整数，对于伪随机数据，哪些无损压缩算法最接近每整数32位的香农熵？

本质上，我在寻找一个表，其中包括压缩算法和它们各自的位/整数值，用于正的、压缩的、32位整数。

Answer 1

这正是分位数压缩(https://github.com/mwlon/quantile-compression/)其目的是：对从数字分布中提取的数字进行无损压缩。我不知道还有其他算法可以做到这一点。您可以在自述文件中看到其结果与理论最优值。它也适用于浮动和时间戳！我不确定你的分布是什么，但现实世界中的分布通常每个数字只需要几位

它的工作原理是将序列中的每个数字编码为一个粗略数字范围的哈夫曼码，然后是该范围内精确位置的偏移量。

Answer 2

恒等式函数需要每32位整数正好32位，这是很难做到的。（如果坚持更改数据流，还有许多其他保持长度的双射。）

我不清楚你会用什么其他标准来html" target="_blank">推荐比这更糟糕的算法。也许您认为输入流不是真正的统一样本；相反，它仅限于（或明显偏向）宇宙的一个子集，但你无法先验地知道该子集是什么。在这种情况下，流的熵小于1（如果子集的大小有一个合理小于宇宙大小的上限），您可能能够实际压缩输入流。

值得注意的是，除非消息是固定长度的，否则在计算熵时需要考虑消息的长度，包括分子和分母。对于很长的消息，这通常可以忽略，但如果消息很短，则消息分隔符（或显式长度指示器）的成本可能会很大。（否则，“压缩”到原始大小的103%有点像HumptyDumpty对“压缩”的定义。）

Answer 3

当你说“它对较小的值更有效”时，我假设你有一个从32位整数到可变位长度表示的转换，该转换针对一些非均匀的预期值分布进行了优化。然后，应用于32位值的均匀分布的相同转换必然需要平均超过32位。还有多少取决于你开始时的分布有多不均匀。

所以答案是，您当然可以通过对数字完全不做任何事情来精确地获得32位。但是，您并没有针对您设计的非均匀分布所隐含的应用程序进行优化。