免责声明：此文未使用任何人工智能撰写。任何错误、尴尬的句子和奇怪的离题内容均为100%有机、自由放养和人类创造的。我捡起了一个我之前放着的难题。在上一篇文章的最后，我扔下了一个难题然后走开，这里它又回来了，因为整个帖子实际上就是我拒绝放手的证明。想象两个文件，每个文件都包含一百万位数字。第一个文件是纯噪音——想象我掷了百万次十面骰子并记录下结果。第二个文件是π（pi）的前一百万位数字。现在从统计学家的角度来看它们：统计每个数字从00到99出现的频率。在这两个文件中，每个数字出现的频率大约是十分之一，因此如果你绘制这两个直方图，就无法区分它们——两个都是扁平的，没有特征。你可以运行任何“这是随机的吗？”的测试，因为两个文件都将通过。依据每个统计测量，这两个文件是相同的：两个都像是纯粹、不可压缩的随机性。然而，有一件事情。第一个文件我可以用三行代码发送给你。我写一个小程序——“计算π（pi），打印一百万位数字”——你就可以完美地再生这个文件。另一个文件我无法压缩，必须逐位发送给你，因为没有比它自己更短的描述。所以整个帖子可以归结为一个问题：如果这两个文件在统计上是相同的，为什么我能压缩一个而无法压缩另一个？问题在于，这个问题没有简单的答案，我认为这正是它有趣的地方。要推进这个问题，我们需要仔细思考“可压缩”这个词实际意味着什么——一旦我们认真思考，这个词就分化成两个非常不同的概念。此帖的大部分内容将探讨这两者之间的区别，并在第二个概念的结尾揭示一个惊喜：一种你始终可以确认存在的可压缩性，但在它不存在时又无法排除的可压缩性。两种压缩方式 我想从一开始就明确一点：这篇文章中的所有内容都是关于无损压缩，这意味着没有任何东西被丢弃，也没有任何东西被近似——我发送给你一个更短的描述，而你可以逐位重建出准确的原始数据。即使在这个严格的规则下，我认为实际上有两个不同的原因导致一个东西可以被压缩，而这篇文章主要是关于识别它们的区别。第一个原因是统计的。有些符号出现得比其他符号更频繁，因此你给常见的符号分配短代码，给稀有符号分配长代码，平均下来你节省了空间。这正是zip文件和霍夫曼编码所做的事，我认为这是大多数人听到压缩时脑海里浮现的那种压缩。第二个原因则与过程有关。即使它的符号看起来分布得非常均匀，这个东西也可能来自一个简单的规则——一个简短的程序。在这种情况下根本没有可以利用的统计冗余，然而这个东西仍然可以被压缩，因为它的短小存在于生成它的过程中，而不是在其符号的频率中。所以这篇文章真正的问题是：统计冗余是唯一的可压缩性吗？而π（pi）将要告诉你答案是否定的。统计类型：熵 从预算构建熵 在我们能够说出π（pi）有何奇怪之前，我们需要明确“统计压缩”实际上测量的是什么，而这个度量有个名字：熵。非正式来说，熵是符号来源中惊讶的平均量。如果一个来源总是发出相同的符号，就一点惊讶都没有——你已经知道将会发生什么了，因此每个新符号对你来说没有任何意义，熵为零。如果一个来源以相等的概率发出十种不同的数字，那么每个新符号都会带来最大的惊讶，因此熵达到最大。大多数来源都处于二者之间：一些符号常见（惊讶小，信息少），一些符号稀有（惊讶大，信息多），熵则是所有这些的平均值，按出现的频率加权。与压缩的联系直接：惊讶正是你必须为之付出比特的东西。无论是可预测的东西你都可以省略，因为接收者可以自行填补，而令人惊讶的东西你必须实际传输。因此，来源的熵以每个符号的比特数衡量，就是你永远可以希望达到的最短平均消息的大小——这是任何无损编码无法低于的下限。这是非正式的分析。然而，我不想只是陈述公式然后继续，因为实际上有一种方法可以推导出来，而我借用这种精神来自Chris Olah美丽的视觉信息理论——以下图片是我对他论点的自己的版本。这是设置。我想以尽可能少的比特发送给你一系列符号，方法是为每个符号分配一个代码字——一串小比特。常见符号应得到短代码；稀有符号则可以长一些，因为我不常