从一张巨型码表到一棵树

上一讲的 Shannon 编码把整条长度 $n$ 的消息映成一个二进制串。理论上最优，工程上不可行：消息共有 $k^n$ 条，码表随 $n$ 指数增长，编码要查表，解码要反查。

Huffman 的做法是把问题降一个维度：只对单个符号编码，得到前缀码，再把符号的码字首尾相接。解码时从左往右走一棵二叉树，读到叶子就切出一个符号。存储和运行时间只与字母表大小 $k$ 有关。

这门课的历史注脚：1951 年，MIT 研究生 David Huffman 为了免修期末考试，在 Fano 教授给的学期论文题目里做出了这个算法。它今天仍是编码理论的基础内容。

本讲要回答两个问题：

1. 怎样找到最优的前缀码？（贪心算法）
2. 最优前缀码到底有多好？（$H\le L\le H+1$）

时间轴

前缀码

前缀码是函数 $\varphi:A\to\{0,1\}^*$，对任意两个不同符号 $a_i\ne a_j$，要求 $\varphi(a_i)$ 不是 $\varphi(a_j)$ 的前缀（两个方向都不允许）。

这比「码字互不相同」更强。例如 $\{0,01\}$ 不是前缀码，因为 $0$ 是 $01$ 的前缀。

树表示

把码字排成二叉树：从根出发，走左孩子记 0，走右孩子记 1，每个符号对应从根到某个节点的路径。

前缀条件等价于：每个符号对应的是叶子，没有符号节点的下方还挂着别的符号。若某个符号在中途，它的码字就会成为后代符号码字的前缀。

反过来，任何一棵所有叶子都标了符号的二叉树（可以有空缺分支，但每个内部节点最多两个孩子）都给出一个前缀码。

解码为什么唯一

收到比特流后，从根开始逐位下行：走左或右，一旦碰到叶子就输出该符号，然后回到根继续。

唯一性由前缀条件保证：假设在某个位置有两种切分方式，一种把当前段读成符号 $x$，另一种读得更早或更晚。若另一种在更早处停下，那么另一个符号的码字是 $\varphi(x)$ 的真前缀；若更晚，则 $\varphi(x)$ 是它的真前缀。两种情况都违反前缀条件。

这就是「即时解码」：不需要看到整条消息，也不需要分隔符，读到叶子就能输出。

问题：最小化期望码长

设符号 $a$ 出现概率为 $p_a$、码长为 $\ell_a$。目标是

$$L=\sum_{a\in A}p_a\ell_a \quad\longrightarrow\quad \min .$$

这里 $L$ 是每个符号的平均码长。若把长度 $n$ 的块整体看成新字母表上的一个符号（共 $k^n$ 个符号），同一个算法就能处理块编码，期望码长随之乘以 $n$。所以先解决单符号问题就够了。

下文的讨论都假定概率两两不同、且合并产生的新符号也不与任何符号并列最小。有并列时算法照常工作，只是论证里要处理「至少并列」的说法。

三条结构引理

思路不是直接构造最优树，而是：假设已经拿到一棵最优树 $T$，反推它必须长什么样。反推出来的约束会强到足以确定整棵树。

所有证明共用同一个动作：交换两个符号的位置。交换不改变码字的集合，只改变哪个符号用哪个码字，因此前缀性质不受影响；只有期望长度会变。

引理 1：最小概率符号在最深层

引理。 设 $b$ 是概率最小的符号，则 $b$ 的码长至少并列最长。

证明。 反设不然。设 $c$ 是最深的符号之一，且 $\ell_b<\ell_c$。交换 $b$ 与 $c$ 的码字，其他符号不变。期望长度的变化只有两项：

$$\Delta L=p_b\ell_c+p_c\ell_b-p_b\ell_b-p_c\ell_c=(p_b-p_c)(\ell_c-\ell_b).$$

由反设 $\ell_c-\ell_b\ge1>0$，且 $p_b<p_c$（$b$ 最小、无并列），故 $\Delta L<0$。

也就是说交换后期望长度严格变小，与 $T$ 的最优性矛盾。因此 $b$ 必须处在最深层。$\square$

引理 2：次小概率符号也在最深层

引理。 设 $d$ 是概率第二小的符号，则 $\ell_d$ 也并列最长。

证明分两步。

第一步：$b$ 的父节点 $P$ 必须有另一个孩子。若 $P$ 只有 $b$ 一个孩子，就把 $b$ 直接挂到 $P$ 的父节点上——由于 $P$ 不对应任何符号（前缀条件），删掉 $P$ 不会丢失信息，而 $b$ 的码长减少 1，期望长度严格下降，矛盾。

设 $P$ 的另一个孩子对应的符号是 $c$，于是 $\ell_c=\ell_b$。

第二步：反设 $\ell_d<\ell_b$。把 $d$ 与 $c$ 的码字交换。由引理 1 的同一计算，

$$\Delta L=(p_d-p_c)(\ell_c-\ell_d).$$

这里 $\ell_c-\ell_d>0$，且 $p_d<p_c$（$d$ 是第二小，$c$ 不是最小），所以 $\Delta L<0$，同样与最优性矛盾。

因此 $\ell_d=\ell_b$，两者都在最深层。$\square$

推论：两者可以互为兄弟

由前两条引理，$b$ 与 $d$ 都在最深层。$b$ 的父节点 $P$ 有另一个孩子 $c$，且 $\ell_c=\ell_b$。把 $b$ 与 $c$ 的位置互换：两者深度相同，期望长度不变，但互换后 $b$ 与 $d$ 共享父节点 $P$。

所以不失一般性，最优树中最小与次小概率的两个符号是兄弟。这一步是后面收缩操作的合法性来源。

收缩与递归

构造子问题

把 $b$、$d$ 从字母表中删去，加入一个新符号 $\alpha$，令

$$p_\alpha=p_b+p_d .$$

其余符号的概率不变。这仍然是一个合法的概率分布。

在树上做同样的操作：删掉 $b$、$d$ 两个叶子，把它们的父节点改成标有 $\alpha$ 的叶子。得到的树记作 $T'$，它是新字母表 $A'$ 上的前缀码。

关键引理：$T'$ 仍是最优的

引理。 若 $T$ 是原问题的最优树，则 $T'$ 是新字母表 $A'$ 上的最优树。

证明。 反设存在更优的树 $S$，期望长度 $L''<L'$。

把 $S$ 中 $\alpha$ 所在的叶子展开成一个小二叉树：父节点下挂 $b$、$d$ 两个叶子。这样得到原字母表 $A$ 上的一棵合法前缀码。

它的期望长度是多少？$S$ 对每个非 $\alpha$ 符号的贡献与之前相同；对 $\alpha$ 的那部分，现在拆成 $b$、$d$ 两个符号，且它们比 $\alpha$ 深一层，所以每遇到一次要多付 1 位。按概率加权，多付的是 $p_b+p_d$。因此展开后的期望长度是

$$L''+p_b+p_d .$$

而 $T$ 是由 $T'$ 做同样的展开得到的，所以

$$L=L'+p_b+p_d .$$

由 $L''<L'$ 得 $L''+p_b+p_d<L'+p_b+p_d=L$，即我们造出了一棵比 $T$ 更好的树，矛盾。$\square$

这个引理是整个算法的支点：原问题的最优解可以由子问题的最优解还原。于是可以反复收缩，直到只剩两个符号；两个符号的树只有一种形状（根下两个叶子），再逐层展开回去。

Huffman 算法

图：合并得到的树、码表与平均码长 2.32。

算法。 维护一个符号集合，每个符号带概率，并记录合并历史：

1. 取出概率最小的两个符号（或合并出的新符号）；
2. 把它们合并成新符号，概率相加，记录「新符号的左孩子、右孩子」；
3. 放回集合，重复，直到只剩一个符号；
4. 从最后的根出发，按合并记录反向展开，左分支标 0、右分支标 1。

运行例子

符号与概率：$a=0.40,\ b=0.05,\ c=0.18,\ d=0.07,\ e=0.20,\ f=0.10$。

反向展开，得到码字：

检查前缀条件：0 与所有以 1 开头的码字分开；100、1010、1011、110、111 互不为前缀（101 不是码字，但 1010 与 1011 在它下面分叉，合法）。

期望码长：

$$L=0.40\cdot1+0.05\cdot4+0.18\cdot3+0.07\cdot4+0.20\cdot3+0.10\cdot3 =0.40+0.20+0.54+0.28+0.60+0.30=2.32 .$$

而这个信源的熵为

$$H=-\sum_a p_a\log_2 p_a\approx2.255 .$$

$2.255\le2.32\le3.255$，落在定理承诺的区间里。

解码示例：比特流 1010 0 110 从根出发，读 1→0→1→0 到叶子，得 $b$；回到根读 0 得 $a$；再读 110 得 $c$。结果是 $bac$。中途在 101 处不会停，因为 101 不是叶子。

Kraft 不等式

定理（Kraft）。 给定正整数 $\ell_1,\dots,\ell_k$，存在一棵叶子深度恰为这些值的二叉树，当且仅当

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

必要性。 深度为 $\ell$ 的节点占用 $2^{-\ell}$ 的「概率质量」：根的质量是 1，每往下一层平分给两个孩子。叶子占用的质量互不重叠，总和不超过 1。

充分性。 把深度从小到大排序，依次在树上找最浅的可用位置放叶子；每放一个深度 $\ell_i$ 的叶子，就把它下方 $2^{-\ell_i}$ 的质量占满。不等式保证轮到每个叶子时仍有空间。补充：课程把完整构造留到习题课，这里只给出要点。

性能：$H\le L\le H+1$

下界

对任意前缀码，由 Kraft 不等式记 $K=\sum_i2^{-\ell_i}\le1$。令 $q_i=2^{-\ell_i}/K$，则 $q$ 是一个概率分布。由 Gibbs 不等式（相对熵非负），

$$0\le D(p\parallel q)=\sum_i p_i\log_2\frac{p_i}{q_i} =\sum_i p_i\log_2\big(p_i\,2^{\ell_i}K\big) =(L-H)+\log_2K .$$

最后一步用了

$$\sum_i p_i\log_2\big(p_i2^{\ell_i}\big) =\sum_ip_i\ell_i+\sum_ip_i\log_2p_i=L-H .$$

于是 $L-H\ge-\log_2K$。因为 $K\le1$，有 $\log_2K\le0$，故 $L\ge H$：任何前缀码都不可能低于熵。这与上一讲 Shannon 的下界一致。

上界

构造一组候选码长

$$\ell_i=\left\lceil-\log_2 p_i\right\rceil .$$

先验证 Kraft：因为 $\lceil x\rceil\ge x$，所以 $-\lceil-\log p_i\rceil\le\log p_i$，于是

$$\sum_i2^{-\ell_i}=\sum_i2^{-\lceil-\log_2 p_i\rceil}\le\sum_i2^{\log_2 p_i}=\sum_i p_i=1 .$$

因此这样的树存在。它的期望长度满足

$$\sum_i p_i\ell_i=\sum_i p_i\left\lceil-\log_2 p_i\right\rceil \le\sum_i p_i\left(-\log_2 p_i+1\right)=H+1 .$$

Huffman 码是所有前缀码中最优的，所以它的码长 $L_{\text{Huffman}}\le H+1$。合起来

$$H\ \le\ L_{\text{Huffman}}\ \le\ H+1 .$$

把 $+1$ 摊薄

逐符号编码时，每次都要多付至多 1 位。若把两个符号捆成一个新符号，字母表变成 $k^2$ 个符号，问题仍然是一阶信源。新熵是多少？

$$\begin{aligned} H_2 &=-\sum_{i,j}p_ip_j\log_2(p_ip_j)\\ &=-\sum_{i,j}p_ip_j\log_2 p_i-\sum_{i,j}p_ip_j\log_2 p_j\\ &=-\sum_i p_i\log_2 p_i-\sum_j p_j\log_2 p_j=2H . \end{aligned}$$

于是对成对编码用 Huffman，期望码长满足 $2H\le L_2\le 2H+1$，每符号是 $H\le L_2/2\le H+1/2$。推广到长度 $n$ 的块：$nH\le L_n\le nH+1$，每符号偏差不超过 $1/n$。

这就是对 Shannon 上界的改进：Shannon 给出的误差是 $o(n)$（可能是 $n/\log n$ 或 $\sqrt n$），Huffman 分块把它压到常数 1。

本节结论

• 前缀码 = 码字互不为前缀；等价于符号都在二叉树的叶子上。
• 逐符号编码让编解码从「查指数大的码表」变成「走一棵树」，且解码即时、唯一。
• 最优树的三个结构性质都由交换论证得到：最小概率在最深层、次小概率也在最深层、两者可互为兄弟。
• 把这对兄弟收缩成概率之和的新符号，子问题的最优解能还原原问题的最优解，于是贪心合并成立。
• Kraft 不等式刻画了「哪些码长组合可以实现」。
• Huffman 码满足 $H\le L\le H+1$；分块编码可把 $+1$ 摊成 $+1/n$。

理解检验

1. 为什么前缀码的解码不会有歧义？请用「假设存在另一种切分」的方式说明。

参考答案：设比特流有两种切分方式，在某个位置产生分歧：一种把从当前位置起的一段读成符号 $x$，另一种读成更短或更长的码字 $y$。

• 若 $\varphi(y)$ 更短，则 $\varphi(y)$ 是 $\varphi(x)$ 的前缀，违反前缀条件；
• 若 $\varphi(y)$ 更长，则 $\varphi(x)$ 是 $\varphi(y)$ 的前缀，同样违反。

因此每个位置只有一种合法读法。这与「码字互不相同」不同：仅互不相同只能保证整条消息不撞车，不能保证从左到右即时切分。

2. 用交换论证证明：概率最小的符号必须位于最深层。

参考答案：设 $b$ 概率最小，反设它的码长 $\ell_b$ 不是最长。取一个最深的符号 $c$，则 $\ell_c>\ell_b$。交换两者的码字后，前缀性质不变（变的只是哪个符号占用哪个码字），期望长度变化为

$$\Delta L=(p_b\ell_c+p_c\ell_b)-(p_b\ell_b+p_c\ell_c)=(p_b-p_c)(\ell_c-\ell_b).$$

因为 $p_b<p_c$ 且 $\ell_c-\ell_b\ge1$，所以 $\Delta L<0$，与最优性矛盾。故 $b$ 必须在最深层。

3. 为什么 $b$ 的父节点必须有另一个孩子？这一条在证明中起什么作用？

参考答案：若父节点 $P$ 只有 $b$ 一个孩子，那么 $P$ 不对应任何符号（否则违反前缀条件）。把 $b$ 直接挂到 $P$ 的父节点上，删掉 $P$，树仍是合法前缀码，而 $b$ 的码长减少 1，期望长度严格下降——矛盾。

这条结论的作用是：$P$ 的另一个孩子 $c$ 与 $b$ 深度相同，于是得到一个「与 $b$ 同深度」的符号，可以拿来和次小概率符号 $d$ 做交换，从而证明 $d$ 也在最深层；进一步把 $b$ 换到 $c$ 的位置，就让 $b$ 与 $d$ 成为兄弟。

4. 设最优树 $T$ 收缩后得到 $T'$，证明 $T'$ 是子问题的最优解，并说明为什么 $L=L'+p_b+p_d$。

参考答案：反设子问题存在更优树 $S$，期望长度 $L''<L'$。把 $S$ 中 $\alpha$ 所在的叶子展开成父节点下挂 $b$、$d$ 的结构，得到原问题的一棵合法前缀码。

在这个展开中，除 $\alpha$ 外的符号贡献不变；遇到 $\alpha$ 的地方原本在那里结束，现在要多走一层才到 $b$ 或 $d$，所以期望长度增加 $p_b+p_d$。故展开后的长度为 $L''+p_b+p_d$。

同理，$T$ 由 $T'$ 展开而来，长度 $L=L'+p_b+p_d$。于是 $L''+p_b+p_d<L'+p_b+p_d=L$，即存在比 $T$ 更优的树，与 $T$ 最优矛盾。

关系式 $L=L'+p_b+p_d$ 的直观含义：合并让子问题少算了一层的贡献，展开时再把这层补回来。

5. 对例子 $a=.40,b=.05,c=.18,d=.07,e=.20,f=.10$ 执行一遍 Huffman 算法，验证 $L=2.32$，并说明它与熵的关系。

参考答案：合并顺序为 $b+d=.12$，再 $f+.12=.22$，再 $c+e=.38$，再 $.22+.38=.60$，最后 $.40+.60=1$。

反向展开得码字 $a=0$、$f=100$、$b=1010$、$d=1011$、$c=110$、$e=111$，长度分别为 $1,3,4,4,3,3$。于是

$$L=.40(1)+.05(4)+.18(3)+.07(4)+.20(3)+.10(3)=2.32 .$$

熵为 $H=-\sum p\log_2 p\approx2.255$。所以 $H\le L\le H+1$ 成立。$L$ 比 $H$ 高约 $0.065$，远小于 1——这个例子恰好落在区间靠下的位置，因为概率分布比较接近 2 的负幂。

6. 用 Kraft 不等式证明「取 $\ell_i=\lceil-\log_2 p_i\rceil$ 一定可行」，并据此推出 $L\le H+1$。

参考答案：因为 $\lceil x\rceil\ge x$，所以 $-\lceil-\log_2 p_i\rceil\le\log_2 p_i$，从而

$$\sum_i2^{-\ell_i}=\sum_i2^{-\lceil-\log_2p_i\rceil}\le\sum_i2^{\log_2p_i}=\sum_i p_i=1 .$$

Kraft 不等式保证存在对应的二叉树。它的期望长度为

$$\sum_i p_i\lceil-\log_2p_i\rceil\le\sum_i p_i(-\log_2p_i+1)=H+1 .$$

Huffman 码在所有前缀码中最优，所以它的长度不超过这棵树，即 $L_{\text{Huffman}}\le H+1$。

7. 为什么把符号两两打包能把 $+1$ 的损失减半？推广到 $n$ 个符号是什么结论？

参考答案：打包后字母表有 $k^2$ 个符号，概率为 $p_ip_j$。其熵为

$$H_2=-\sum_{i,j}p_ip_j\log_2(p_ip_j)=-\sum_ip_i\log_2p_i-\sum_jp_j\log_2p_j=2H,$$

最后一步分别对 $j$ 与 $i$ 求和并用 $\sum p=1$。对这个问题用 Huffman，得到 $2H\le L_2\le2H+1$，除以 2 得每符号 $H\le L_2/2\le H+1/2$。

长度 $n$ 的块同理：熵为 $nH$，码长满足 $nH\le L_n\le nH+1$，每符号误差不超过 $1/n$，随 $n$ 趋于 0。这正是把 Shannon 的 $o(n)$ 改进为常数 1 的方式。

8. Huffman 码已经是最优前缀码，为什么还可能需要 Shannon 的结论？

参考答案：两者回答不同的问题。Huffman 给出单符号、可实现的最优前缀码，但它的最优性只在「逐符号前缀码」这一类里成立；若允许对整块消息做任意单射编码（不要求前缀结构），理论上还能再省一点，Shannon 定理刻画的正是这个更大类的最优值 $nH\pm o(n)$。

此外，Huffman 的 $H+1$ 界需要知道概率分布、并在分布变化时重建树；Shannon 的结论不依赖具体算法，用来判断「还值不值得改进」。两者互补：Huffman 给构造，Shannon 给极限。

与前后课的关系

上一讲证明熵是任意块编码的渐近极限，但构造不可实现；本讲给出可实现且最优的前缀码，并把损失从 $o(n)$ 收紧到常数 1。

下一讲转向噪声信道：发送的比特可能被翻转，编码的目标从「更短」变成「更可靠」。Shannon 第二定理会用随机编码与典型性说明，只要码率低于信道容量，错误概率就能压到任意小。再往后两讲会用 Hamming 码与 Reed–Solomon 码给出具体的纠错构造。

From a giant table to a tree

Shannon's construction from the previous lecture maps a whole length-$n$ message to one binary string. It is asymptotically optimal but impractical: there are $k^n$ messages, so the codebook grows exponentially, and both encoding and decoding require searching it.

Huffman drops a dimension: encode one symbol at a time, using a prefix code, and concatenate the codewords. Decoding walks a binary tree from the root and emits a symbol whenever it hits a leaf. Storage and running time depend only on the alphabet size $k$.

A historical footnote from the lecture: in 1951, MIT graduate student David Huffman developed this algorithm for a term paper, partly to avoid a final exam that Bob Fano had offered him. It is still a cornerstone of coding theory.

Two questions organize the lecture:

1. How do we find the optimal prefix code? (A greedy algorithm.)
2. How good is it? ($H\le L\le H+1$.)

Timeline

Prefix codes

A prefix code is a function $\varphi:A\to\{0,1\}^*$ such that for distinct symbols $a_i\ne a_j$, neither $\varphi(a_i)$ is a prefix of $\varphi(a_j)$ nor the reverse.

This is stronger than requiring distinct codewords. For example $\{0,01\}$ is not a prefix code, since $0$ is a prefix of $01$.

Tree representation

Lay the codewords out as a binary tree: walk left for 0 and right for 1 from the root, and each symbol corresponds to the path to some node.

The prefix condition is equivalent to: every symbol sits at a leaf, with no other symbol below it. If a symbol appeared at an internal node, its codeword would be a prefix of every descendant's codeword.

Conversely, any binary tree whose leaves are labelled with the symbols (some branches may be missing, but every internal node has at most two children) yields a prefix code.

Why decoding is unique

Given a bit stream, start at the root and descend one bit at a time. On reaching a leaf, emit that symbol and return to the root.

Uniqueness follows from the prefix condition. Suppose two parsings disagree at some position: one reads the next segment as symbol $x$, the other as a codeword $y$ of different length. If $\varphi(y)$ is shorter, it is a proper prefix of $\varphi(x)$; if longer, $\varphi(x)$ is a proper prefix of $\varphi(y)$. Both violate the condition.

This gives instantaneous decoding: no separators and no lookahead are needed; a symbol is emitted as soon as a leaf is reached.

The problem: minimize expected length

Let symbol $a$ have probability $p_a$ and codeword length $\ell_a$. The objective is

$$L=\sum_{a\in A}p_a\ell_a \quad\longrightarrow\quad \min .$$

Here $L$ is the average length per symbol. If length-$n$ blocks are treated as single symbols over an enlarged alphabet of size $k^n$, the same algorithm applies and the expected length scales by $n$. So solving the one-symbol problem suffices.

Throughout, probabilities are assumed distinct, and merged symbols are assumed not to tie with existing ones. Ties require only "at least tied" wording; the algorithm is unchanged.

Three structural lemmas

The strategy is not to construct the optimal tree directly but to assume one exists and derive what it must look like. The constraints turn out to be strong enough to determine the tree.

Every proof uses the same move: swap two symbols' positions. A swap leaves the set of codewords untouched, so prefix-freeness is preserved; only the expected length changes.

Lemma 1: the least likely symbol is deepest

Lemma. If $b$ has the smallest probability, then its codeword is at least tied for longest.

Proof. Suppose not. Let $c$ be a deepest symbol with $\ell_b<\ell_c$. Swap the codewords of $b$ and $c$, leaving all others fixed. Only two terms change:

$$\Delta L=p_b\ell_c+p_c\ell_b-p_b\ell_b-p_c\ell_c=(p_b-p_c)(\ell_c-\ell_b).$$

By assumption $\ell_c-\ell_b\ge1>0$ and $p_b<p_c$ (with no ties), so $\Delta L<0$.

The swap strictly shortens the code, contradicting optimality. Hence $b$ lies at the deepest level. $\square$

Lemma 2: the second least likely symbol is also deepest

Lemma. If $d$ has the second smallest probability, then $\ell_d$ is also maximal.

Proof, in two steps.

First, the parent $P$ of $b$ must have another child. If $P$ had only $b$, detach $b$ and attach it to $P$'s parent. Since $P$ carries no symbol (prefix-freeness), deleting it loses nothing, while $b$'s codeword shortens by one, strictly improving $L$ — a contradiction.

Let $c$ be the symbol at $P$'s other child, so $\ell_c=\ell_b$.

Second, suppose $\ell_d<\ell_b$. Swap the codewords of $d$ and $c$. The same computation gives

$$\Delta L=(p_d-p_c)(\ell_c-\ell_d).$$

Here $\ell_c-\ell_d>0$ and $p_d<p_c$ (since $d$ is second smallest and $c$ is not the smallest), so $\Delta L<0$, again contradicting optimality.

Hence $\ell_d=\ell_b$, and both sit at the deepest level. $\square$

Corollary: they can be made siblings

By the two lemmas, both $b$ and $d$ are deepest. The parent $P$ of $b$ has another child $c$ at the same depth. Swap the positions of $b$ and $c$: depths are equal, so $L$ is unchanged, and now $b$ and $d$ share the parent $P$.

Thus without loss of generality, the two least likely symbols are siblings in an optimal tree. This is what makes the contraction below legitimate.

Contraction and recursion

Building the subproblem

Delete $b$ and $d$ from the alphabet and add a new symbol $\alpha$ with

$$p_\alpha=p_b+p_d ,$$

leaving all other probabilities unchanged. This is still a valid distribution.

Do the same on the tree: remove the leaves $b$ and $d$ and turn their parent into a leaf labelled $\alpha$. The resulting tree $T'$ is a prefix code on the new alphabet $A'$.

Key lemma: $T'$ is still optimal

Lemma. If $T$ is optimal for the original problem, then $T'$ is optimal for the reduced alphabet $A'$.

Proof. Suppose some tree $S$ is better, with expected length $L''<L'$.

Expand the leaf holding $\alpha$ in $S$ into a small subtree with $b$ and $d$ as children. This yields a valid prefix code on the original alphabet $A$.

What is its expected length? The contributions of all symbols other than $\alpha$ are unchanged. Wherever $\alpha$ appeared, the code now continues one level deeper to reach $b$ or $d$, so the expected length grows by exactly $p_b+p_d$. The expanded length is therefore

$$L''+p_b+p_d .$$

The original tree $T$ is obtained from $T'$ by the same expansion, so

$$L=L'+p_b+p_d .$$

Since $L''<L'$, we get $L''+p_b+p_d<L'+p_b+p_d=L$: a tree better than $T$, a contradiction. $\square$

This lemma is the hinge of the algorithm: the optimum of the original problem can be recovered from the optimum of the subproblem. So contract repeatedly until two symbols remain; a two-symbol tree has only one shape (a root with two leaves), then expand back level by level.

Huffman's algorithm

Figure：The merged tree, the code table, and the average length 2.32。

Algorithm. Maintain a set of symbols with probabilities and a record of merges:

1. Take the two symbols (or merged symbols) of smallest probability.
2. Merge them into a new symbol whose probability is the sum, recording "left child, right child".
3. Put it back and repeat until one symbol remains.
4. Expand the merge record from the root, labelling left branches 0 and right branches 1.

Running example

Symbols and probabilities: $a=0.40$, $b=0.05$, $c=0.18$, $d=0.07$, $e=0.20$, $f=0.10$.

Expanding back gives the code:

Prefix check: 0 is separated from every codeword starting with 1; $100,1010,1011,110,111$ are pairwise prefix-free (101 is not a codeword, but 1010 and 1011 branch below it, which is allowed).

The expected length is

$$L=0.40(1)+0.05(4)+0.18(3)+0.07(4)+0.20(3)+0.10(3)=2.32 .$$

The entropy of the source is

$$H=-\sum_a p_a\log_2 p_a\approx2.255 .$$

So $2.255\le2.32\le3.255$, inside the promised interval.

Decoding example: the stream 1010 0 110 walks 1→0→1→0 to a leaf, giving $b$; back at the root, 0 gives $a$; then 110 gives $c$. The message is $bac$. We never stop at 101, because 101 is not a leaf.

The Kraft inequality

Theorem (Kraft). Given positive integers $\ell_1,\dots,\ell_k$, a binary tree with leaves at exactly these depths exists if and only if

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

Necessity. A node at depth $\ell$ occupies $2^{-\ell}$ of the total "mass": the root has mass 1, and each level splits its mass equally between two children. Leaves occupy disjoint mass, so the total is at most 1.

Sufficiency. Sort the depths increasingly and place leaves at the shallowest available positions; a leaf at depth $\ell_i$ consumes all mass below it. The inequality guarantees that space remains when each leaf is placed. Note: the lecture defers the full construction to recitation; this is only a sketch.

Performance: $H\le L\le H+1$

Lower bound

For any prefix code, Kraft's inequality gives $K=\sum_i2^{-\ell_i}\le1$. Set $q_i=2^{-\ell_i}/K$; then $q$ is a probability distribution. Gibbs' inequality (nonnegativity of relative entropy) gives

$$0\le D(p\parallel q)=\sum_i p_i\log_2\frac{p_i}{q_i} =\sum_i p_i\log_2\big(p_i\,2^{\ell_i}K\big) =(L-H)+\log_2K .$$

The last step uses

$$\sum_i p_i\log_2\big(p_i2^{\ell_i}\big) =\sum_ip_i\ell_i+\sum_ip_i\log_2p_i=L-H .$$

So $L-H\ge-\log_2K$, and since $K\le1$ we have $\log_2K\le0$, hence $L\ge H$: no prefix code can beat entropy, matching Shannon's converse from the previous lecture.

Upper bound

Propose the codeword lengths

$$\ell_i=\left\lceil-\log_2 p_i\right\rceil .$$

First check Kraft. Since $\lceil x\rceil\ge x$, we have $-\lceil-\log p_i\rceil\le\log p_i$, so

$$\sum_i2^{-\ell_i}=\sum_i2^{-\lceil-\log_2 p_i\rceil}\le\sum_i2^{\log_2 p_i}=\sum_i p_i=1 .$$

A tree with these depths therefore exists. Its expected length satisfies

$$\sum_i p_i\ell_i=\sum_i p_i\left\lceil-\log_2 p_i\right\rceil \le\sum_i p_i\left(-\log_2 p_i+1\right)=H+1 .$$

Huffman's code is optimal among all prefix codes, so $L_{\text{Huffman}}\le H+1$. Together,

$$H\ \le\ L_{\text{Huffman}}\ \le\ H+1 .$$

Amortizing the $+1$

Encoding one symbol at a time costs at most one extra bit per symbol. Bundle two symbols into one: the alphabet becomes $k^2$ symbols and the source is still first order. Its entropy is

$$\begin{aligned} H_2 &=-\sum_{i,j}p_ip_j\log_2(p_ip_j)\\ &=-\sum_{i,j}p_ip_j\log_2p_i-\sum_{i,j}p_ip_j\log_2p_j\\ &=-\sum_ip_i\log_2p_i-\sum_jp_j\log_2p_j=2H . \end{aligned}$$

Huffman on pairs gives $2H\le L_2\le2H+1$, i.e. $H\le L_2/2\le H+1/2$ per symbol. For blocks of length $n$: $nH\le L_n\le nH+1$, so the per-symbol gap is at most $1/n$.

This improves Shannon's bound: Shannon's error was $o(n)$ (possibly $n/\log n$ or $\sqrt n$), while blocked Huffman reduces it to the constant 1.

What this lecture establishes

• A prefix code has no codeword a prefix of another; equivalently, all symbols sit at leaves of a binary tree.
• Symbol-by-symbol coding replaces an exponentially large table with a tree, giving unique and instantaneous decoding.
• Three exchange arguments fix the shape of an optimal tree: least likely and second least likely symbols are deepest, and can be made siblings.
• Contracting that pair into a symbol with summed probability preserves optimality, which justifies greedy merging.
• The Kraft inequality characterizes which length profiles are realizable.
• Huffman satisfies $H\le L\le H+1$; blocking amortizes the $+1$ to $+1/n$.

Comprehension check

1. Why is prefix-code decoding unambiguous? Explain by assuming an alternative parsing.

Reference answer: Suppose two parsings disagree at some position: one reads the next segment as symbol $x$, the other as a codeword $y$ of different length.

• If $\varphi(y)$ is shorter, it is a prefix of $\varphi(x)$, violating prefix-freeness;
• if $\varphi(y)$ is longer, $\varphi(x)$ is a prefix of $\varphi(y)$, also a violation.

So only one parsing is legal at every position. Distinctness of codewords alone would only prevent whole-message collisions; it would not allow splitting a stream on the fly.

2. Use an exchange argument to show that the least likely symbol must be deepest.

Reference answer: Let $b$ have the smallest probability and suppose its length $\ell_b$ is not maximal. Pick a deepest symbol $c$, so $\ell_c>\ell_b$. Swapping their codewords preserves prefix-freeness (only which symbol occupies which codeword changes), and the expected length changes by

$$\Delta L=(p_b\ell_c+p_c\ell_b)-(p_b\ell_b+p_c\ell_c)=(p_b-p_c)(\ell_c-\ell_b).$$

Since $p_b<p_c$ and $\ell_c-\ell_b\ge1$, $\Delta L<0$, contradicting optimality. Hence $b$ is at the deepest level.

3. Why must the parent of $b$ have another child, and what role does this play?

Reference answer: If the parent $P$ had only $b$, then $P$ carries no symbol (otherwise prefix-freeness fails). Detaching $b$ and attaching it to $P$'s parent deletes $P$, keeps a valid prefix code, and shortens $b$'s codeword by one, strictly improving $L$ — a contradiction.

The consequence is that $P$'s other child $c$ has the same depth as $b$. That gives a symbol at $b$'s depth to swap with the second least likely symbol $d$, proving $d$ is also deepest; swapping $b$ into $c$'s position then makes $b$ and $d$ siblings.

4. Let $T$ be optimal and $T'$ its contraction. Prove $T'$ is optimal for the subproblem, and explain why $L=L'+p_b+p_d$.

Reference answer: Suppose a better tree $S$ exists for the subproblem, with $L''<L'$. Expand the leaf holding $\alpha$ into a parent with children $b$ and $d$; this is a valid prefix code for the original alphabet.

The contributions of all symbols other than $\alpha$ are unchanged. Where $\alpha$ used to end, the code now descends one more level to reach $b$ or $d$, so the expected length increases by exactly $p_b+p_d$. The expanded length is $L''+p_b+p_d$.

Likewise $T$ comes from expanding $T'$, so $L=L'+p_b+p_d$. Then $L''+p_b+p_d<L'+p_b+p_d=L$, giving a tree better than $T$, contradicting optimality.

The identity means: contraction removes one level's contribution from the subproblem, and expansion adds it back.

5. Run Huffman's algorithm on $a=.40,b=.05,c=.18,d=.07,e=.20,f=.10$, verify $L=2.32$, and relate it to entropy.

Reference answer: The merges are $b+d=.12$, then $f+.12=.22$, then $c+e=.38$, then $.22+.38=.60$, then $.40+.60=1$.

Expanding back gives $a=0$, $f=100$, $b=1010$, $d=1011$, $c=110$, $e=111$ with lengths $1,3,4,4,3,3$. Hence

$$L=.40(1)+.05(4)+.18(3)+.07(4)+.20(3)+.10(3)=2.32 .$$

The entropy is $H=-\sum p\log_2p\approx2.255$, so $H\le L\le H+1$ holds. The gap is about $0.065$, far below 1, because the probabilities are close to negative powers of two.

6. Use Kraft to show that $\ell_i=\lceil-\log_2 p_i\rceil$ is always realizable, and derive $L\le H+1$.

Reference answer: Since $\lceil x\rceil\ge x$, we have $-\lceil-\log_2p_i\rceil\le\log_2p_i$, hence

$$\sum_i2^{-\ell_i}=\sum_i2^{-\lceil-\log_2p_i\rceil}\le\sum_i2^{\log_2p_i}=\sum_ip_i=1 .$$

Kraft guarantees the tree. Its expected length is

$$\sum_ip_i\lceil-\log_2p_i\rceil\le\sum_ip_i(-\log_2p_i+1)=H+1 .$$

Huffman is optimal among prefix codes, so $L_{\text{Huffman}}\le H+1$.

7. Why does pairing symbols halve the $+1$ loss? What is the general statement for blocks of $n$?

Reference answer: After pairing, the alphabet has $k^2$ symbols with probabilities $p_ip_j$, and its entropy is

$$H_2=-\sum_{i,j}p_ip_j\log_2(p_ip_j)=-\sum_ip_i\log_2p_i-\sum_jp_j\log_2p_j=2H,$$

using $\sum p=1$ in each sum. Huffman on pairs gives $2H\le L_2\le2H+1$, so per symbol $H\le L_2/2\le H+1/2$.

For blocks of length $n$, entropy is $nH$ and $nH\le L_n\le nH+1$, so the per-symbol error is at most $1/n$, tending to zero. This is how Shannon's $o(n)$ becomes a constant 1.

8. Huffman's code is already optimal among prefix codes. Why might Shannon's theorem still be needed?

Reference answer: They answer different questions. Huffman gives an implementable, optimal prefix code, but optimality holds only within the class of symbol-by-symbol prefix codes. If arbitrary injective block codes are allowed (no prefix structure), a little more can be saved in principle, and Shannon's theorem describes that larger class with the value $nH\pm o(n)$.

Huffman's $H+1$ bound also requires knowing the distribution and rebuilding the tree when it changes; Shannon's result does not depend on any algorithm and tells us whether further improvement is even possible. They are complementary: Huffman gives constructions, Shannon gives limits.

Relation to neighbouring lectures

The previous lecture proved entropy is the asymptotic limit for arbitrary block codes but gave an unimplementable construction; this lecture provides an implementable optimal prefix code and tightens the loss from $o(n)$ to the constant 1.

The next lecture turns to noisy channels: transmitted bits may flip, so the goal changes from "shorter" to "more reliable". Shannon's second theorem uses random coding and typicality to show that below channel capacity the error probability can be driven arbitrarily low. The two lectures after that give concrete correction schemes: Hamming codes and Reed–Solomon codes.