为什么可以压缩 pi 的文本表示？

Question

随机字符串应该是不可压缩的。

pi = "31415..."
pi.size  # => 10000
XZ.compress(pi).size  # => 4540

一个随机的十六进制字符串也被显着压缩。但是，随机字节字符串不会被压缩。

pi的字符串只包含字节48到57。加上整数的前缀代码，这个字符串可以被大量压缩。本质上，我通过以字节表示我的 9 个不同字符（或 16 个，在十六进制字符串的情况下）来浪费 space。这是怎么回事？

有人可以向我解释一下底层方法是什么，或者给我指出一些来源吗？

Answer 1

这是信息密度的问题。压缩就是去除冗余信息。

在字符串"314159"中，每个字符占8位，因此可以有2⁸或256个不同的值中的任何一个，但这些值中只有10个是实际使用。即使是非常简单的压缩方案也可以使用每个数字 4 位来表示相同的信息；这被称为二进制编码的十进制。更复杂的压缩方案可以做得更好（十进制数字实际上是 log₂10，或大约 3.32 位），但以存储一些允许解压缩的额外信息为代价。

在一个随机的十六进制字符串中，每个8位字符有4个有意义的位，所以压缩近50%应该是可以的。字符串越长，您越接近 50%。如果您事先知道该字符串仅包含十六进制数字，则可以将其压缩 50%，但当然会失去压缩其他任何内容的能力。

在一个随机的字节串中，没有压缩的机会；您需要每个字符的全部 8 位来表示每个值。如果它真的是随机的，尝试压缩它可能会稍微扩展它，因为需要一些额外的信息来指示输出是压缩数据。

解释压缩工作原理的细节超出了这个答案的范围和我的专业知识。

Answer 2

除了在较大序列中重复的 , there's another point that's relevant to LZMA (which is the compression algorithm that the XZ format uses). The number pi does not consist of a single repeating string of digits, but neither is it completely random. It does contain substrings of digits 之外。 LZMA 可以检测到这些并仅存储重复子字符串的单个副本，从而减少压缩数据的大小。