10.3 前缀编码、哈夫曼树与决策树

第 10.2 节利用根树中的顺序遍历并计算每个顶点。本节会把权重放到树的叶子上，并提出另一类优化问题：频繁使用的符号或很可能出现的决策结果应当拥有较短的根到叶路径，少见结果则可以使用较长路径。

这个思想把二叉树、第 9 章的概率与贪心算法连接起来。

从符号到比特串

字母表是需要编码的有限符号集合。令

\mathcal A=\{A,B,C,D\}.

一个比特只能是 $0$ 或 $1$ 。比特串是有限个比特组成的序列，例如 $0$ 、 $101$ 或 $1110$ 。记号

\{0,1\}^*

表示所有有限比特串组成的集合，其中包括空串 $\varepsilon$ 。右上角的星号表示“任意有限长度”，不是乘法。

一个二进制编码是函数

C:\mathcal A\to\{0,1\}^*,

它给每个源符号分配一个比特串，这个比特串称为码字。

例如，

C(A)=0, \quad C(B)=10, \quad C(C)=110, \quad C(D)=111.

消息 $ABD$ 的编码是三个码字的连接：

C(A)C(B)C(D)=0\,10\,111=010111.

接收者只能看到连续比特流，因此必须能够恢复码字边界。

前缀编码可以立即解码

如果比特串 $y$ 的开头包含 $x$ 的全部比特，就称 $x$ 是 $y$ 的前缀。例如， $01$ 是 $0110$ 的前缀。

如果任何码字都不是另一个不同码字的前缀，就称这个编码是前缀编码或无前缀编码。

上面的示例编码是前缀编码。解码器读到 $0$ 后，就能确定符号是 $A$ ，因为没有更长码字以 $0$ 开头。若第一位为 $1$ ，解码器继续读取，直到到达 $10$ 、 $110$ 或 $111$ 。

对比下面的编码：

C(A)=0, \quad C(B)=01, \quad C(C)=1.

比特流 $01$ 既可以表示 $B$ ，也可以切分成 $0\mid1$ 而表示 $AC$ 。因为 $0$ 是 $01$ 的前缀，解码产生歧义。

前缀编码就是一棵二叉树

可以用根二叉树表示编码：

每条左边标记 $0$ ，每条右边标记 $1$ ；
源符号只放在叶子上；
从根到符号叶子的边标签依次组成该符号的码字。

为什么符号必须位于叶子？如果符号占据内部顶点，它的根路径就会成为下方所有码字的前缀。只把符号放在叶子上，便能保证无前缀性质。

对于示例编码，各条路径如下：

符号	根到叶决策	码字长度
$A$	左	$1$
$B$	右、左	$2$
$C$	右、右、左	$3$
$D$	右、右、右	$3$

解码时从根沿边前进。每次到达叶子就输出对应符号，再回到根处理后续比特。

用 Kraft 不等式检查容量

设码字长度为 $\ell_1,\ell_2,\ldots,\ell_m$ 。每个二进制前缀编码都满足

\sum_{i=1}^{m}2^{-\ell_i}\le1.

这称为 Kraft 不等式。深度为 $\ell_i$ 的叶子在更深的公共层中占据 $2^{-\ell_i}$ 的分支比例。不同前缀叶子覆盖的分支区域互不重叠，所以比例总和不能超过整棵树。

长度集合 $1,2,3,3$ 满足

2^{-1}+2^{-2}+2^{-3}+2^{-3}=1.

等号表示编码树已经完整使用可用叶子容量。不等式可以检查长度是否可能，但不会自动给符号分配具体比特串。

正在加载交互实验...

操作一台可以编辑码字与比特流的二进制无线电解码器。解码光标会沿树前进，到达叶子时发出符号，并揭示前缀冲突和未完成后缀。学习者需要亲手修复有歧义的码表，而不是只看系统判断。

正在加载概念检查...

正在加载本节练习...

期望码长

假设符号 $s_i$ 出现的概率为 $p_i$ ，其中

p_i\ge0, \qquad \sum_{i=1}^{m}p_i=1.

若其码字长度为 $\ell_i$ ，编码一个随机符号所需的比特数就是离散随机变量。根据第 9 章的期望定义，期望码长为

L=\sum_{i=1}^{m}p_i\ell_i.

把高频符号码字缩短一位，比把低频符号缩短一位更能降低 $L$ 。这正是使用变长编码的动机。

如果题目给出原始频数 $f_i$ 而不是概率，可以定义带权路径长度

W=\sum_{i=1}^{m}f_i\ell_i.

因为 $p_i=f_i/\sum_j f_j$ ，所以

L=\frac{W}{\sum_j f_j}.

对于固定频数表，最小化 $W$ 与最小化 $L$ 是同一个问题。

Huffman 贪心合并算法

对于给定频数，Huffman 编码会构造在所有二进制前缀编码中带权路径长度最小的前缀树。

开始时，每个符号各自成为一个叶子，叶子的权重就是频数。然后重复：

1. 选择当前权重最小的两个根； 2. 让它们成为一个新父结点的两个子结点； 3. 把两者权重之和作为父结点权重； 4. 把新父结点放回集合。

只剩一棵树时停止。为每对左右子边标记 $0$ 与 $1$ 。交换左右位置会改变具体码字，却不会改变码长或期望代价。

算法运行过程中，当前集合是一片由局部编码树组成的森林：每次合并连接两个根，并让连通部分数量减少一个。第 11 章的图算法会再次使用森林视角，而 Huffman 的规则很明确——每次合并权重最小的两个根。

一个完整 Huffman 示例

设符号频数为

符号	$A$	$B$	$C$	$D$	$E$	$F$
频数	$45$	$13$	$12$	$16$	$9$	$5$

合并序列为

\begin{aligned} 5+9&=14,\\ 12+13&=25,\\ 14+16&=30,\\ 25+30&=55,\\ 45+55&=100. \end{aligned}

其中一种结果树产生码长

\ell_A=1, \quad \ell_B=\ell_C=\ell_D=3, \quad \ell_E=\ell_F=4.

带权路径长度为

\begin{aligned} W &=45(1)+13(3)+12(3)+16(3)+9(4)+5(4)\\ &=224. \end{aligned}

频数总和为 $100$ ，所以期望码长为

L=\frac{224}{100}=2.24\text{ 比特/符号}.

为什么要合并两个最小权重

在某棵最优满前缀树中，频数最小的两个符号可以放在最深的一对兄弟叶子上。若较重符号位于较轻符号之下，交换二者位置不会增加带权路径长度；较小权重位于更深位置至少不会更差。

把这对兄弟合并成一个临时符号，其权重等于二者之和。较小合并问题的任意最优树都能展开回原问题的最优树。于是形成贪心结构：

\text{选择两个最轻根} \longrightarrow \text{合并} \longrightarrow \text{求解更小实例}.

权重并列时可能得到不同 Huffman 树与码字，但所有合法的并列选择都会保持最优带权代价。

正在加载交互实验...

每一轮亲自选择两个令牌来建造 Huffman 森林。选择合法的最轻对会生长出可见二叉树；昂贵选择仍可撤销，并会显示它造成的代价损失。锻造完成后，系统会导出码字、深度、带权路径长度与每符号期望比特数。

正在加载概念检查...

正在加载本节练习...

前缀编码也是二元决策树

二元决策树在每个内部顶点提出一个“是或否”问题。回答会选择一条子边，叶子给出最终结果。识别一个结果所需的问题数就是对应叶子深度。

若结果 $i$ 的概率为 $p_i$ 、深度为 $d_i$ ，期望提问次数为

E[Q]=\sum_i p_i d_i.

它与期望码长公式完全相同：一条 $0/1$ 编码边就是一次二元决策。因此，当允许任意二元划分问题，而且目标是最小化期望深度时，Huffman 编码也会构造最优二元决策树。

这里有一个重要边界：现实决策问题可能限制允许提出的问题。例如，诊断系统只能使用实际可获得的检测。此时 Huffman 的无限制最优结果是一条比较基准，不一定是可执行的决策流程。

期望深度与最坏情况深度也是不同目标。Huffman 最小化按概率加权的平均值，但罕见结果可能得到很长路径。具有严格最坏响应上限的系统可能需要另一棵树。

第 10 章知识链

1. 树连通且无环，因此任意顶点对之间都有唯一路径。

2. 选择根会建立层级、深度、高度与有序子结点位置。

3. 遍历把树结构变成确定序列与自底向上的计算。

4. 前缀树把根到叶路线变成无歧义比特串。

5. Huffman 合并最小化按概率加权的叶子深度。

第 11 章会从树推广到图。我们将研究不再受唯一路径限制的网络中的环、多条路径、度、连通性、遍历、最短路线与最小代价连接骨架。

10.3 前缀编码、哈夫曼树与决策树

这个思想把二叉树、第 9 章的概率与贪心算法连接起来。

从符号到比特串

字母表是需要编码的有限符号集合。令

\mathcal A=\{A,B,C,D\}.

一个比特只能是 $0$ 或 $1$ 。比特串是有限个比特组成的序列，例如 $0$ 、 $101$ 或 $1110$ 。记号

\{0,1\}^*

表示所有有限比特串组成的集合，其中包括空串 $\varepsilon$ 。右上角的星号表示“任意有限长度”，不是乘法。

一个二进制编码是函数

C:\mathcal A\to\{0,1\}^*,

它给每个源符号分配一个比特串，这个比特串称为码字。

例如，

C(A)=0, \quad C(B)=10, \quad C(C)=110, \quad C(D)=111.

消息 $ABD$ 的编码是三个码字的连接：

C(A)C(B)C(D)=0\,10\,111=010111.

接收者只能看到连续比特流，因此必须能够恢复码字边界。

前缀编码可以立即解码

如果比特串 $y$ 的开头包含 $x$ 的全部比特，就称 $x$ 是 $y$ 的前缀。例如， $01$ 是 $0110$ 的前缀。

如果任何码字都不是另一个不同码字的前缀，就称这个编码是前缀编码或无前缀编码。

对比下面的编码：

C(A)=0, \quad C(B)=01, \quad C(C)=1.

比特流 $01$ 既可以表示 $B$ ，也可以切分成 $0\mid1$ 而表示 $AC$ 。因为 $0$ 是 $01$ 的前缀，解码产生歧义。

前缀编码就是一棵二叉树

可以用根二叉树表示编码：

每条左边标记 $0$ ，每条右边标记 $1$ ；
源符号只放在叶子上；
从根到符号叶子的边标签依次组成该符号的码字。

为什么符号必须位于叶子？如果符号占据内部顶点，它的根路径就会成为下方所有码字的前缀。只把符号放在叶子上，便能保证无前缀性质。

对于示例编码，各条路径如下：

符号	根到叶决策	码字长度
$A$	左	$1$
$B$	右、左	$2$
$C$	右、右、左	$3$
$D$	右、右、右	$3$

解码时从根沿边前进。每次到达叶子就输出对应符号，再回到根处理后续比特。

用 Kraft 不等式检查容量

设码字长度为 $\ell_1,\ell_2,\ldots,\ell_m$ 。每个二进制前缀编码都满足

\sum_{i=1}^{m}2^{-\ell_i}\le1.

长度集合 $1,2,3,3$ 满足

2^{-1}+2^{-2}+2^{-3}+2^{-3}=1.

等号表示编码树已经完整使用可用叶子容量。不等式可以检查长度是否可能，但不会自动给符号分配具体比特串。

正在加载交互实验...

正在加载概念检查...

正在加载本节练习...

期望码长

假设符号 $s_i$ 出现的概率为 $p_i$ ，其中

p_i\ge0, \qquad \sum_{i=1}^{m}p_i=1.

若其码字长度为 $\ell_i$ ，编码一个随机符号所需的比特数就是离散随机变量。根据第 9 章的期望定义，期望码长为

L=\sum_{i=1}^{m}p_i\ell_i.

把高频符号码字缩短一位，比把低频符号缩短一位更能降低 $L$ 。这正是使用变长编码的动机。

如果题目给出原始频数 $f_i$ 而不是概率，可以定义带权路径长度

W=\sum_{i=1}^{m}f_i\ell_i.

因为 $p_i=f_i/\sum_j f_j$ ，所以

L=\frac{W}{\sum_j f_j}.

对于固定频数表，最小化 $W$ 与最小化 $L$ 是同一个问题。

Huffman 贪心合并算法

对于给定频数，Huffman 编码会构造在所有二进制前缀编码中带权路径长度最小的前缀树。

开始时，每个符号各自成为一个叶子，叶子的权重就是频数。然后重复：

1. 选择当前权重最小的两个根； 2. 让它们成为一个新父结点的两个子结点； 3. 把两者权重之和作为父结点权重； 4. 把新父结点放回集合。

只剩一棵树时停止。为每对左右子边标记 $0$ 与 $1$ 。交换左右位置会改变具体码字，却不会改变码长或期望代价。

一个完整 Huffman 示例

设符号频数为

符号	$A$	$B$	$C$	$D$	$E$	$F$
频数	$45$	$13$	$12$	$16$	$9$	$5$

合并序列为

\begin{aligned} 5+9&=14,\\ 12+13&=25,\\ 14+16&=30,\\ 25+30&=55,\\ 45+55&=100. \end{aligned}

其中一种结果树产生码长

\ell_A=1, \quad \ell_B=\ell_C=\ell_D=3, \quad \ell_E=\ell_F=4.

带权路径长度为

\begin{aligned} W &=45(1)+13(3)+12(3)+16(3)+9(4)+5(4)\\ &=224. \end{aligned}

频数总和为 $100$ ，所以期望码长为

L=\frac{224}{100}=2.24\text{ 比特/符号}.

为什么要合并两个最小权重

把这对兄弟合并成一个临时符号，其权重等于二者之和。较小合并问题的任意最优树都能展开回原问题的最优树。于是形成贪心结构：

\text{选择两个最轻根} \longrightarrow \text{合并} \longrightarrow \text{求解更小实例}.

权重并列时可能得到不同 Huffman 树与码字，但所有合法的并列选择都会保持最优带权代价。

正在加载交互实验...

正在加载概念检查...

正在加载本节练习...

前缀编码也是二元决策树

二元决策树在每个内部顶点提出一个“是或否”问题。回答会选择一条子边，叶子给出最终结果。识别一个结果所需的问题数就是对应叶子深度。

若结果 $i$ 的概率为 $p_i$ 、深度为 $d_i$ ，期望提问次数为

E[Q]=\sum_i p_i d_i.

第 10 章知识链

1. 树连通且无环，因此任意顶点对之间都有唯一路径。

2. 选择根会建立层级、深度、高度与有序子结点位置。

3. 遍历把树结构变成确定序列与自底向上的计算。

4. 前缀树把根到叶路线变成无歧义比特串。

5. Huffman 合并最小化按概率加权的叶子深度。

第 11 章会从树推广到图。我们将研究不再受唯一路径限制的网络中的环、多条路径、度、连通性、遍历、最短路线与最小代价连接骨架。