压缩随机32位整数：我们能逼近香农熵到何种程度？

嘿，很高兴看到你自己开发了无损压缩算法，这个31.95824比特的平均压缩率挺有意思的！针对你问的伪随机数据（毕竟均匀分布的话理论上没法压缩到32比特以下），我整理了几个能尽可能逼近香农熵的算法，它们在处理这类接近均匀分布的数据时，额外开销极小：

• LZ77/LZ78变种（如Deflate）：虽然这类算法通常靠捕捉重复模式压缩，但面对均匀伪随机数据时，因为找不到可复用的序列，它会直接以近乎原始比特的方式编码，仅添加极少的元数据，平均每个整数的开销几乎能紧贴32比特。
• 自适应Huffman编码：和需要预统计概率的静态Huffman不同，自适应版本会在编码过程中动态调整码表。对于均匀分布的伪随机数据，最终码表会趋近于等长编码，每个整数的编码长度非常接近32比特，额外的调整开销微乎其微。
• 算术编码：从理论上来说，算术编码能达到香农熵的极限。哪怕是处理均匀分布的32位整数序列，优化后的算术编码实现只会引入极其微小的额外比特开销，几乎可以忽略不计。
• LZ4：这个算法主打高速压缩/解压，同时在处理无模式的伪随机数据时，它的“直通”模式会直接输出原始数据，仅添加极少的帧头信息，平均下来每个整数的开销几乎就是32比特，额外成本极低。

要特别说明的是：根据香农熵编码定理，完全均匀的伪随机数据是不可能被无损压缩到32比特以下的，上面这些算法的核心优势在于它们的额外冗余（比如码表、帧头、编码 overhead）非常小，能尽可能地贴近32比特的原始尺寸，不会带来不必要的膨胀。

内容的提问来源于stack exchange，提问作者Jacob G.