为什么圆周率的文本表示可以压缩？

Question

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

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

随机十六进制字符串也会被显著压缩。然而，随机字节字符串不会被压缩。

pi字符串只包含字节48到57。如果整数上有前缀代码，则该字符串可能会被严重压缩。本质上，我是在浪费空间，用字节表示9个不同的字符（十六进制字符串是16个）。这是怎么回事？

有人能给我解释一下基本方法是什么，或者给我指出一些来源吗？

Answer 1

除了基思·汤普森（Keith Thompson）的优秀答案外，还有一点与LZMA（XZ格式使用的压缩算法）有关。数字pi不是由单个重复的数字串组成的，但也不是完全随机的。它确实包含在较大序列中重复的数字子串。LZMA可以检测到这些，并且只存储重复子串的一个副本，从而减少压缩数据的大小。

Answer 2

这是一个信息密度的问题。压缩是指删除冗余信息。

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

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

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

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