数据压缩

现在，我们通过建立信息压缩的基本极限，为熵的定义增添内容。数据压缩可以通过为数据源中最常见的结果分配简短的描述，并为不太常见的结果分配较长的描述来实现。例如，在摩尔斯电码中，最常用的符号用一个点表示。在本章中，我们将找到随机变量的最短平均描述长度。

我们首先定义瞬时码的概念，然后证明重要的Kraft不等式，该不等式断言指数化的码字长度分配必须类似于概率质量函数。然后，初等微积分证明预期描述长度必须大于或等于熵，这是第一个主要结果。接着，香农的简单构造表明，对于重复描述，预期描述长度可以渐近地达到该界限。这确立了熵作为有效描述长度的自然度量。本文提供了用于寻找最小预期描述长度分配的著名霍夫曼编码程序。最后，我们证明霍夫曼码是竞争最优的，并且它需要大约H次公平抛硬币来生成一个熵为H的随机变量样本。因此，熵是数据压缩的极限，也是随机数生成所需的位数(bits)，而从许多角度来看，达到H的编码都是最优的。