数据的压缩编码

\(\newcommand{\E}{\mathbb{E}}\)\(\newcommand{\X}{\mathcal{X}}\)现在我们要开始讨论熵的意义，为此我们依然要回到数据的压缩编码这一核心概念上。

首先我们要严格地定义编码。在这里，我们默认是用二进制进行编码。事实上，我们将要证明的所有结论对于一般的\(\mathcal{D}\)进制而言都是成立的。在信息论中对数的底数并不重要，我们的结论并不是依赖于底数的。我们定义对随机变量\(X\)的编码就是\(\X\to \{0,1\}^*\)的映射\(C\)，\(X\)的每个取值对应着一个有限01串。进一步，如果\(C\)是一个单射，也即如果任意不同的取值对应不同的01串，我们就称\(C\)是一个nonsingular(非奇异的)的编码方式。对于nonsingular的编码方式，只需要在相邻字符间加上逗号或其它分隔符，就能够通过编码后的串唯一解码出原始的字符串。但在实际应用中，使用分隔符并不是一种高效的做法。如果我们能够保证所有编码后的字符不存在其中一个串是另一个串的前缀的情况，那么我们无需分隔符就可以唯一的解码。我们称这样的编码方式为前缀码(Prefix Code)或即时码(Instantaneous Code)，这样的编码方式是自带标点(Self-punctuating)的。

Kraft Inequality

当我们要求编码方式必须是前缀码时，我们就不能总是采用最短的可用字符串了。例如如果同时采用\(0\)和\(1\)作为编码，那就不可能使用任何其它串了。也就是说，对于\(|\X|=n\)，如果把需要编码的字符编码后的长度排成一列\(\ell_1,\ell_2,\cdots,\ell_n\)，这些长度肯定要满足某些约束。例如当\(|\X|=3\)时，\(\{1,1,2\}\)肯定不是一个可行的前缀码编码方式，而\(\{1,2,2\}\)的确是可行的。

思考编码问题的一个最常见方法就是把编码放到前缀树上去思考。在这里，前缀树是一棵二叉树。记\(\ell_{\max}\)是编码最长的字符，那么这一定是一棵深度不超过\(\ell_\max\)的树。对于前缀树而言，只有叶节点能够作为编码的终点。前缀树可以看作去除了某些子树后的满二叉树。一棵深度为\(\ell_\max\)的满二叉树，那么第\(k\)层恰好有\(2^k\)个节点，在第\(\ell_\max\)层有\(2^{\ell_\max}\)个节点。对于长度为\(\ell_i\)的编码，由于它一定没有后代，所以相较于满二叉树在第\(\ell_\max\)层会损失共\(2^{\ell_{\max}-\ell_i}\)个节点。而每个\(\ell_i\)的后代都是互不重叠的，因此在最后一层上总的损失节点数就是\(\sum\limits_{i=1}^{n}2^{\ell_\max-\ell_i}\)，它一定不超过\(2^{\ell_\max}\)。这样我们就得到了不等式\(\sum\limits_{i=1}^{n}2^{-\ell_i}\leq 1\)。这称为Kraft Inequality。

而一旦我们得到了一个满足Kraft Inequality的序列\(\ell_1,\cdots,\ell_n\)，那么我们可以直接在01前缀树上构造出一个合法的前缀编码。把\(\ell_1,\cdots,\ell_n\)从小到大排序，从满二叉树出发，依次找到字典序最小的深度为\(\ell_i\)的节点，移除它的后代，不断重复如上操作即可。

另一种理解Kraft Inequality的方法是二进制小数。假设第\(i\)个二进制编码记为\(y_1y_2\cdots y_{\ell_i}\)，我们可以把它与二进制小数\(0.y_1y_2\cdots y_{\ell_i}\)对应。由于不存在与它有相同前缀的编码，我们可以视为这个小数独占了区间\([0.y_1y_2\cdots y_{\ell_i},0.y_1y_2\cdots y_{\ell_i}+2^{-\ell_i})\)。这恰好是一个长度为\(2^{-\ell_i}\)的区间。由于所有编码对应的区间互不重叠，一定有\(\sum\limits_{i=1}^{n}2^{\ell_i}\leq 1\)。这样我们就再一次得到了Kraft Inequality。而在这种证明中，即便编码数量是无穷（但是可数）的，这个不等式依然成立。因此，我们得到了更广义的在可数意义下的Kraft Inequality。

最优编码问题

在编码时，我们不仅要保证解码不能有歧义，还要使得编码的长度尽可能短。这里的长度指的是在统计词频后期望意义下的最短。例如在英文中e出现的概率最高，我们就希望e被编码得尽量短；q出现的概率低，我们就可以让q有相对较长的编码。设字母表的概率分布函数为\(p\)，第\(i\)个字符的出现概率为\(p_i\)，被编码长度为\(\ell_i\)。则我们要选取合适的\(\ell_i\)的分布，最小化\(L=\sum\limits_{i=1}^{n}p_i\ell_i\)。

由于\(\ell_i\)的分布必须满足Kraft Inequality，而一旦满足了Kraft Inequality就是一个可行的编码。因此这其实就是一个不等式约束下的凸优化问题：在约束\(\sum\limits_{i=1}^{n}2^{-\ell_i}\leq 1\)下最小化\(L=\sum\limits_{i=1}^{n}p_i\ell_i\)。对于这个问题，可以根据KKT条件直接求解。但方便起见我们先用Lagrange条件在等式取紧\(\sum\limits_{i=1}^{n}2^{-\ell_i}=1\)时求出\(L\)的最小值，再证明任何编码都不可能比这个最小值更小。

根据Lagrange乘数法，\(L(\ell,\lambda)=\sum\limits_{i=1}^{n}p_i\ell_i+\lambda\left(\sum\limits_{i=1}^{n}2^{-\ell_i}-1\right)\)。于是\(\dfrac{\part L}{\part \ell_i}=p_i-\lambda\cdot 2^{-\ell_i}\ln 2=0\)。因此\(2^{-\ell_i}=\dfrac{p_i}{\lambda\ln 2}\)是个定值。代入\(\sum\limits_{i=1}^{n}2^{-\ell_i}=1\)，得到\(\dfrac{\sum p_i}{\lambda \ln 2}=1\)，也即\(\lambda = \dfrac{1}{\ln 2}\)。由此解得\(2^{-\ell_i}=p_i\)，也就是说第\(i\)个字符应当被编码成长度为\(\ell_i=\log_2 \dfrac{1}{p_i}\)的串。这恰好是熵的定义中出现的项。如果我们重新写出期望的编码长度的式子，恰好得到\(L=\sum\limits_{i=1}^{n}p_i\log_2\dfrac{1}{p_i}\)。这就是\(H(X)\)的定义！我们还要进一步验证任何编码方式得到的\(L\)都不可能比\(H(X)\)更小。\(L-H(X)=\sum\limits_{i=1}^{n}p_i\ell_i+\sum\limits_{i=1}^{n}p_i\log p_i\)\(=\sum\limits_{i=1}^{n}p_i\log( p_i 2^{\ell_i})\)。记\(c=\sum\limits_{j=1}^{n}2^{-\ell_i}\)，\(r_i=\dfrac{2^{-\ell_i}}{c}\)，则\(r_i\)构成了某个概率分布\(q\)。\(L-H(X)=\sum\limits_{i=1}^{n}p_i\log \left(\dfrac{p_i}{2^{-\ell_i}}\cdot \dfrac{c}{c}\right)=\sum\limits_{i=1}^{n}p_i\log \left(\dfrac{p_i}{2^{-\ell_i}/c}\cdot \dfrac{1}{c}\right)\)\(=\sum\limits_{i=1}^{n}p_i\log\dfrac{p_i}{r_i}-\log c\)\(=D(p||r)-\log c\)。根据Kraft Inequality，\(c\leq 1\)，因此\(-\log c\geq 0\)。而根据信息不等式，相对熵\(D(p||r)\geq 0\)也成立。综上，\(L\geq H(X)\)始终成立。

所以我们看到，熵的含义就是最优编码的期望编码长度。当然，\(\ell_i=-\log p_i\)不一定是整数。这个等号只有在\(X\)的所有分布密度都是\(2\)的幂次时才能取到。一个自然的问题时，既然对于一般的分布等号总是无法取到，我们能否给出一个\(L\)的上界？（在AEP一节中我们已经给出\(H(X)+\epsilon\)作为上界，但当时并没有要求编成前缀码）下面我们证明，只需向上取整取\(\ell_i=\left\lceil-\log p_i\right\rceil\)就能得到上界\(L\leq H(X)+1\)。根据\(-\log p_i \leq \ell_i \leq -\log p_i+1\)，两边同时乘以\(p_i\)得到\(-p_i\log p_i\leq p_i\ell_i\leq -\log p_i+p_i\)。累加得到\(\sum\limits_{i=1}^{n}-p_i\log p_i=\)\(H(X)\leq\)\(\sum\limits_{i=1}^{n}p_i\ell_i=L\)\(\leq \sum\limits_{i=1}^{n}-p_i\log p_i+\sum\limits_{i=1}^{n}p_i\)\(=H(X)+1\)。