哈夫曼编码让不同字符之间代码长度不同，保证经常出现的字符的代码要短。

Prefix Code

浅层定义：没有字符代码是别的字符代码的前缀。

定义：for a set $S$S of letters, a prefix code is a function $\gamma$γ that maps each letter $x \in S$x∈S to some sequence of zeros and ones, in such way that for distinct $x, y \in S$x,y∈S, the sequence $\gamma(x)$γ(x) is not a prefix of the sequence $\gamma(y)$γ(y).

Optimal Prefix Codes

假设对于任意一个字母 $x \in S$x∈S, $f_x$fx​ 代表字母 $x$x 出现的频率。

• 假设总共有 $n$n 个字母，其中 $n f_x$nfx​ 个字母是 $x$x.
• $\sum_{x\in S} f_x = 1$∑x∈S​fx​=1

用 $|\gamma(x)|$∣γ(x)∣ 表示 $\gamma(x)$γ(x) 的长度，那么
$\text{encoding length}=\sum_{x \in S} n f_x |\gamma(x)| = n \sum_{x \in S} f_x |\gamma(x)|$encoding length=∑x∈S​nfx​∣γ(x)∣=n∑x∈S​fx​∣γ(x)∣

定义： the average number of bits required per letter $ABL(\gamma)=\sum_{x \in S} f_x |\gamma(x)|$ABL(γ)=∑x∈S​fx​∣γ(x)∣

目标：minimize $ABL(\gamma)$ABL(γ)

算法设计

A binary tree $T$T with the number of leaves equal to the size of the alphabet $S$S, and we label each leaf with a distinct letter in $S$S.

定理 (4.27): The encoding of $S$S constructed from $T$T is a prefix code.
证明：（反证法）
若 $\gamma(x)$γ(x) 是 $\gamma(y)$γ(y) 的 prefix，the path from the root to $x$x would have to be a prefix of the path from
the root to $y$y
但是，这等同于说 $x$x would lie on the path from root to $y$y
与 $x$x 是 leaf 矛盾

$ABL(T) = \sum_{x \in S} f_x \cdot \text{depth}_T(x)$ABL(T)=∑x∈S​fx​⋅depthT​(x)

定理 (4.28): The binary tree corresponding to the optimal prefix code is full.
证明：（exchange argument）
Let $T$T denote the binary tree corresponding to the optimal prefix code, and suppose it contains
a node $u$u with exactly one child $v$v.
$\quad$
Convert $T$T into a tree $T'$T′ by replacing node $u$u with $v$v.
分两类情况讨论：
1.$\; u$u 是 root: 删除 $u$u, 并将 $v$v 变成 root。
2.$\; u$u 不是 root:
$\quad$ 令 $w$w 为 $u$u 的 parent in $T$T.
$\quad$ 删除 $u$u，并让 $v$v 成为 $w$w 的 child.
$\quad$ 这个改变 decrease the number of bits needed to encode any leaf in the subtree rooted at node $u$u,
$\quad$ and it does not affect other leaves
$\quad \; \therefore ABL(T')<ABL(T)$∴ABL(T′)<ABL(T)
$\quad$ 与 optimality of $T$T 矛盾

定理 (4.29): 假设已知 optimal binary tree $T^*$T∗。Suppose that $u$u and $v$v are lives of $T^*$T∗, such that $depth(u) < depth(v)$depth(u)<depth(v). Further, suppose that in a labeling of $T^*$T∗ corresponding to an optimal prefix code, leaf $u$u is labeled with $y\in S$y∈S and leaf $v$v is labeled with $z \in S$z∈S. Then, $f_y \geq f_z$fy​≥fz​.
证明：用 exchange argument 证明，交换 $u, v$u,v 的 label。

定理 (4.30): Consider a leaf $v$v in $T^*$T∗ with largest depth. Leaf $v$v has a parent $u$u, and by (4.28) $T^*$T∗ is a full binary tree, so $u$u has another child $w$w. Then, $w$w is a leaf of $T^*$T∗. 反证法

定理 (4.31): There is an optimal prefix code, with corresponding tree $T^*$T∗, in which the two lowest-frequency letters are assigned to leaves that are siblings in $T^*$T∗.

算法伪代码

To construct a prefix code for an alphabet $S$S, with given frequencies:

1. If $S$S has two letters then
2. $\quad$Encode one letter using 0 and the other letter using 1
3. Else
4. $\quad$Let $y^*$y∗ and $z^*$z∗ be the two lowest-frequency letters
5. $\quad$Form a new alphabet $S'$S′ by deleting $y*$y∗ and $z^*$z∗ and replacing them with a new letter $w$w of frequency $f_{y^*}+f_{z^*}$fy∗​+fz∗​
6. $\quad$Recursively construct a prefix code $\gamma'$γ′ for $S'$S′, with tree $T'$T′
7. $\quad$Define a prefix code for $S$S as follows:
8. $\quad \quad$Start with $T'$T′
9. $\quad \quad$Take the leaf labeled $w$w and add two children below it, labeled $y^*$y∗ and $z^*$z∗
10. EndIf