1.4.2　如何实现无损压缩

假设Alice需要把一个数据集（可能无限大）从遥远的半人马座星系传输给地球上的Bob，假设如下，图1-15是传输编码数据的示意图。

● ，表示一个标记，词表大小。

● Alice和Bob都有足够的计算资源。

● 假设现在已经传输了，Alice会将下一个编码为后传输给Bob。

● Alice希望最小化传输的数据量S，以比特数量来衡量。

先看一下基准传输方法。由于的可能性有256（词表大小）种，所以可以表示为一个8比特的整数（1字节）。假如，编码后用表示，这时需要传输的数据量为8比特（）。

图1-15　传输编码数据

另外，Alice要将上面的传输步骤写成一份新的代码，在传输数据之前给到Bob。这样传输一个大小为n的数据集的代价可以表示为

　　（1-1）

接下来从信息论角度解释一下基准的信息量。

基准方法对于的分布没有先验知识，因此其概率分布是一个离散均匀分布。此时信息量表示为

　　（1-2）

因此，可被看作信息量。

提示　信息论的创始人克劳德·艾尔伍德·香农（Claude Elwood Shannon）定义了信息量的概念，信息量被用来衡量一个离散随机变量的不确定性。假设服从概率分布，且有一个词汇表，那么的信息量就是用比特数来表示的，公式表示为

　　（1-3）

这意味着，一个“事物”的信息量取决于它出现的概率。

我们可以任意选择一个词汇表，比如二进制数据，它可以很容易地被分成8比特的字节。每字节有0～255，共256种可能的取值，所以需要用8比特来表示1字节。这里其实有一个隐含的假设：0～255每个取值出现的概率都是相等的，也就是满足如下关系。

　　（1-4）

事实上，的最大值就是在是均匀分布时取到的。当是1字节时，比特。也就是说，如果不是均匀分布，那么可以用少于8比特的编码来表示1字节。这就是各种“压缩”算法的理论基础。

在介绍了基准方法之后，接下来介绍基于神经网络的无损压缩方法。

假设我们想要利用一个自回归神经网络来实现压缩，以如下场景为例。

Alice首先把一个自回归神经网络（如GPT）的训练代码发送给Bob。这个网络的输入是，输出是下一个数据的概率分布。注意，网络的“大小”是由决定的，但网络的权重是由初始化并不断训练得到的。可以把网络的参数看作的一个函数。图1-16是概率分布的示意图（纵坐标为概率，示意图中的概率为参考示例，无实际意义）。

图1-16　当前传输数据的概率分布

虽然网络的权重是由Alice和Bob各自独立地初始化和训练的，但是由于他们使用相同的方法和随机种子，导致他们的初始权重相同，并会随着数据的传输而保持同步更新，因此是的函数。

假设Alice已经把发送给了Bob，现在她要把编码成并发送给Bob。由于此时Alice和Bob根据相同的代码和相同的数据训练了相同的网络，因此他们对的概率分布也有相同的预测。为简便起见，便省略条件部分，直接写作。

考虑使用算术编码的二分查找法来把编码成，假设取值为0、1、2、3的概率分别为0.2、0.25、0.22、0.175。如果要把编码成，可以用以下区间查找的选择来表示。每一次的区间选择都有两种可能的结果：左区间（向左）或右区间（向右）。

如果使用1表示向右，0表示向左，那么查找过程便可以表示为一个长度为3的动作序列。

● 。

● 刚好可以用一个3比特的二进制数字表示。

Alice将这个动作序列编码为一个3比特的二进制数字，发送给Bob。

● 等价于二分查找的次数。

● 在这个例子里，。

Bob收到后，得到的过程如下所示。

（1）Bob也预测得到分布。

（2）根据代表的动作序列，复现二分查找的过程，得到0.687 5这个有限精度的实数。

（3）找到这个实数所在的区间是第4个区间，则Bob解码。

这样一来，Alice就将把按照Alice和Bob共同掌握的概率分布编码成，并且把它无损地传输给Bob。Bob也可以按照同样的概率分布把解码为。这个过程比基准方法节省了很多传输的数据量。原本需要传输8比特，现在只需要传输3比特。图1-17是整个过程的示意图。

图1-17　算术编码的二分查找过程