熵和霍夫曼编码

编码

编码的目的是表示一系列符号 ($s_n$)，其中 $s_n$ 取自有限集合 𝒳。

这些符号可以是字母（文本编码）、整数（图像像素值）、音频信号的样本等。需要编码的符号类型并不重要。假设我们知道每个符号的出现概率，并且这些符号是独立生成的。每个符号由其代码表示，代码是一系列位（0或1），其长度可能可变。符号序列通过各个符号代码的串联来表示。

若编码操作是单射的，则称该编码是可解码déchiffrable的。

称一个编码为前缀码code préfixe，当且仅当没有一个编码是另一个编码的前缀。这是编码可解码的充分条件。

记编码为 $φ$，其长度 $|φ|$ 表达如下：$|\phi|=\sum_{k=1}^K p_k\left|\phi\left(x_k\right)\right|$
其中，$p_k$ 是符号 $x_k$ 的出现概率，$|φ(x_k)|$ 是与符号相关的代码字长度。

现存的编码

布莱叶编码（Code Braille）

为了让盲人能够阅读，布莱叶编码用 6 个点（6 位）来表示字母。

莫尔斯电码（Code Morse）

莫尔斯电码通过点和划的序列以及空格来表示字母。可以通过编码将其转换为二进制，点用 1 表示，划用 111 表示（遵循莫尔斯电码的定义），点与划之间用 0 表示，字母之间用 00 表示，单词之间用 000 表示。

ASCII 编码（Code ASCII）

在 ASCII 编码中，字符通过 7 位的序列表示，这足以涵盖大写字母、小写字母、符号和控制字符。

为了编码英语以外的语言所需的字符（如重音符等），存在扩展至 8 位的版本，例如 ISO 8859-15，可用于法语。

UTF-8

Unicode 标准（截至 2023 年）包含 149813 个字符，允许编码大量的字母、特殊字符、表情符号等。UTF-8 编码能够表示这些字符。

编码一个字符所需的位数是可变的，范围为 8 到 32 位。ASCII 编码的字符（西方最常用的）使用 8 位编码，而更罕见的字符则使用更多的位数。

整数的二进制表示（Écriture binaire des entiers）

将 1 到 7 的整数通过其二进制表示编码如图 1 所示。这是一个非前缀码。例如，位序列 101 可以同时表示 (5) 或 (2, 1)。图 2 所示的编码是前缀码（所有等长的编码都是前缀码）。可以通过编码 1 为 00 来简化该编码。整数的编码不一定对应于其二进制表示。

最优编码

在这一节，我们的目的是构建一个最优编码，即最小化编码长度的编码，其定义为：

$|\phi|=\sum_{k=1}^K p_k |\phi\left(x_k\right)|$

即我们要在编码为前缀码的约束下，找到一个长度集合$l_k = \left|\phi\left(x_k\right)\right|$，满足：

$\min _{\left(l_k\right) \in \mathbb{N}^K}|\phi|=\sum_{k=1}^K p_k l_k，s.c. \ préfixw$

处理此问题的第一步是将前缀码的约束替换为对其长度的约束。

克拉夫特-麦克米伦定理 Théorème de Kraft-McMillan

定理：对于一组长度为($l_k$)编码为前缀码，当且仅当以下条件成立时，前缀码满足：
$\sum_{k=1}^K 2^{-l_k} \leq 1$

证明：

正向：通过向下延展每个节点的叶子到最大编码长度 $L$ 来补全树。每个节点编码的叶子数为 $2^{L-l_k}$ 。由于是前缀码，不同节点的叶子集合互不相交，因此最多有 $2^L$ 叶子。于是有:

$\sum_{k=1}^K 2^{L-l_k} \leq 2^L$

两边除以 $2^L$ ，得:

$\sum_{k=1}^K 2^{-l_k} \leq 1$

结论成立。

反向：从一个长度为 $L$ 的完全二叉树出发，假设长度按降序排列。对于每个长度 $l_k$ ，移除 $2^{l_k}$ 个叶子，并将这些叶子分配给对应长度的父节点（长度按降序，每组叶子属于同一子树）。当叶子数量足够时，即满足:

$\sum_{k=1}^K 2^{L-l_k} \leq 2^L$

这种构造是可能的。

根据克拉夫特-麦克米伦定理，原本的问题转化为：

$\begin{aligned}H= & \min _{\left(l_k\right) \in \mathrm{R}^K} \sum_{k=1}^K p_k l_k ，s.c. & \sum_{k=1}^K 2^{-l_k} \leq 1\end{aligned}$

这是一个型如：

$\begin{gathered} \min f(x) ， \text { s.c. } g(x) \leq 0 \end{gathered}$

的问题。局部最优解$x^*$满足以下条件：

$\nabla f\left(x^{\star}\right)+\lambda \nabla g\left(x^{\star}\right)=0$
$g\left(x^{\star}\right) \leq 0$
$\lambda \geq 0$
$\lambda g\left(x^{\star}\right)=0$

根据这些条件，可得对于任意的$k$：

$p_k-\lambda(\log 2) 2^{-l_k}=0$

解得：

$\lambda=\frac{1}{\log 2}, \quad l_k=-\log _2 p_k$

于是有：

$H=\sum_{k=1}^K p_k l_k=-\sum_{k=1}^K p_k \log _2 p_k$

$H$是离散概率分布$(p_k)_k$的熵。

若符号集合均匀分布，$p_k = 1/K$，则有 $H = log_2K$

长度 $l_k$ 可以取实数，因此比原问题中的整数约束更宽松。最优编码长度 $L^{\star}$ 满足以下关系：

$H \leq L^{\star}$

反过来，存在一个前缀码（Shannon 编码） $\phi^{\dagger}$ 的长度为 $l_k^{\dagger}=\left\lceil l_k\right\rceil$ ，满足：

$L^{\dagger}<H+1$

虽然这不一定是最优编码，但保证了最优编码长度 $L^{\star}$ 满足如下界限：

$H \leq L^{\star}<H+1$

霍夫曼编码：构建最优编码

前一部分确认了存在一个长度不超过$H+1$的最优编码，但未提供其构造方法。霍夫曼算法能够保证构造出一个最优编码。

霍夫曼算法

霍夫曼算法以递归方式构建编码 $\phi$ 。它接收符号列表 $\left(x_1, \ldots, x_K\right)$ 及其对应的概率 $\left(p_1, \ldots, p_K\right)$ 作为输入。

当 $K=2$ 时，给两个符号 $\left(a_1, a_2\right)$ 分配编码:
$\phi\left(a_1\right)=0, \quad \phi\left(a_2\right)=1$
当 $K>2$ 时，假设符号 $\left(a1, \ldots, a_K\right)$ 按概率降序排列 $\left(p_1, \ldots, p{K-1}, pK\right)$ 。将符号 $\left(a{K-1}, aK\right)$ 合并为一个新符号 $z$ ，其概率为 $p{K-1}+pK$ 。对于新符号集合 $\left(a_1, \ldots, a{K-2}, z\right)$ 构建霍夫曼编码 $\phi^{\star}$ 。然后设置：
$\phi\left(a_k\right)=\phi^{\star}\left(a_k\right) \text { (对于 } k \leq K-2 \text { ), } \phi\left(a_{K-1}\right)=\phi^{\star}(z) 0, \quad \phi\left(a_K\right)=\phi^{\star}(z) 1$

例如

最优性证明

引理：对于一组给定的符号及其概率，总可以找到一个最优编码，使得概率最小的两个符号是兄弟节点。

证明:

假设 $x$ 和 $y$ 是概率最小的两个符号，但它们不是兄弟节点。如果它们位于同一深度的不同分支，可以交换分支，使其成为兄弟节点，而不改变编码长度。于是存在一个满足条件的最优编码。
假设 $l_x>l_y$ 。如果 $x$ 没有兄弟节点，可以将其上移一层，此时编码不是最优的。如果 $x$ 有兄弟节点（符号或子树），则可以将其与 $y$ 交换，从而减少编码长度。唯一的可能是 $x$ 和 $y$ 作为兄弟节点，并具有相同的长度，从而保留最优性。

通过递归证明。当 $K=2$ 时，结论显然成立。
假设对于 $K-1$ 个符号结论成立。霍夫曼算法为 $K$ 个符号生成了编码 $\phiK$ 。同时，存在一个满足最优条件的编码 $\psi_K$ 。在这两种情况下，符号 $x$ 和 $y$ 是兄弟节点（即它们的编码长度相同）。通过将这两个符号在 $\phi_K$ 中合并为一个符号 $z$ ，可以得到 $K-1$ 个符号的霍夫曼编码 $\phi{K-1}$ 。同样，在最优编码 $\psiK$ 中进行合并，也可以得到 $K-1$ 个符号的编码 $\psi{K-1}$ 。对于这两种情况，有以下等式成立:

$\begin{aligned} & \left|\phi_K\right|=\left|\phi_{K-1}\right|+p_x+p_y \\ & \left|\psi_K\right|=\left|\psi_{K-1}\right|+p_x+p_y \end{aligned}$

由此可得：

$\left|\phi_K\right|=\left|\phi_{K-1}\right|+p_x+p_y, \quad\left|\psi_K\right|=\left|\psi_{K-1}\right|+p_x+p_y$

实际上， $K$ 个符号的编码是通过向 $z$ 的编码添加一个比特来重新找到 $x$ 和 $y$ 的编码，这在平均意义上增加了 $p_x+p_y$ 的长度。

由于对于 $K-1$ 个符号的霍夫曼编码是最优的，得出：

$\left|\phi_{K-1}\right| \leq\left|\psi_{K-1}\right|$

从而可以推导出:

这证明了霍夫曼算法对 $K$ 个符号的最优性。

基于块的霍夫曼编码

为了更接近熵，可以对符号块进行编码，而不是单独对每个符号编码。此时，每个符号的平均长度上限为：

$H+\frac{1}{N}$

$N$是块的长度

局限性

霍夫曼编码的局限性包括以下需求：

必须知道符号的概率。
必须传递编码信息。
或者必须传递概率信息。
或者必须预先固定编码（例如，在某些压缩标准中）。

其他编码方法：

算术编码（Code arithmétique）

这种方法可以在不需要构造块（因此避免代码复杂性随块大小增长而增加）的情况下达到理论压缩界限。
Lempel-Ziv 编码

一种基于字典的编码方法，将符号流分割为由先前观察到的序列和符号组成的片段。它还可以达到压缩界限，并能考虑符号间的相关性。

PNG 格式

PNG 格式是一种无损压缩的图像存储格式。像素通常通过 8 位或 16 位表示，支持 1 至 4 个通道（灰度、RGB、透明度）。

算法的两个步骤包括：

预测步骤：用于降低熵。
DEFALTE 编码：结合 Lempel-Ziv 和霍夫曼编码的方法。

不同的预测方法

可以使用以下几种预测方法：

0：无过滤，直接编码原始像素强度值。
1：编码当前像素与像素 A 的差值。
2：编码当前像素与像素 B 的差值。
3：编码当前像素与像素 A 和 B 平均值（向下取整）的差值。
4：编码当前像素与 A、B 或 C 中最接近 $A+B−C$ 值的像素的差值。

其中，预测方法对每一行是固定的。