少言者乃最佳之人 – 亨利五世
在第 1 章，我们探讨了信息编码的方法，以确保唯一可解码或瞬时解码。在这两种情况下，Kraft 不等式或 McMillan 不等式都表明，我们需要使用足够长的编码单词。这引出了效率的问题：如果编码单词过长，则存储变得困难，传输速度也会变慢。因此，我们需要在确保有效解码和保证经济性之间找到平衡。从这一角度来看，最优的编码方案是最优编码（optimal codes），即平均编码长度最短的瞬时编码。接下来，我们将证明这类编码的存在性，并研究Huffman 算法的构造过程。
为了简化讨论，我们主要关注二进制编码（\(r = 2\)）的情况，同时简要介绍这些思想如何扩展到非二进制编码。
2.1 Optimality
设 \(S\) 为信息源，如第 1 章所述。我们仍然假设符号的概率分布独立于时间 \(n\)，且与前序符号 \(X_1, \dots, X_{n-1}\) 无关。尽管以下理论可以扩展到不满足这些条件的情况，但我们将重点关注满足这些条件的最简单情况。由于数列 \(\{ p_i \}\) 形成了概率分布，因此：
\[ 0 \leq p_i \leq 1 \quad \sum_{i=1}^{q} p_i = 1 \]
如果信息源 \(S\) 的编码 \(C\) 具有编码单词长度 \(l_1, l_2, \dots, l_q\)，则其平均编码长度定义为：
\[ L = L(C) = \sum_{i=1}^{q} p_i l_i \]
显然，对于所有编码 \(C\)，有：\(L(C) \geq 0\) 。为了兼顾经济性与效率，我们希望使 \(L(C)\) 尽可能小，同时保证瞬时解码。在给定进制数 \(r\) 和概率分布 \(\{ pp_i \}\) 的情况下，我们希望找到最优 \(r\) 进制编码 \(C\)，使 \(L(C)\) 最小。这样的编码称为最优编码（optimal codes）或紧凑编码（compact codes）。
例 2.1
设 \(S\) 为每日天气的信息源（如例 1.2），假设 \(S\) 的符号概率分布如下：\(p_1 = \frac{1}{4}, \quad p_2 = \frac{1}{2}, \quad p_3 = \frac{1}{4}\) 。二进制编码 \(C\) 如下：\(s_1 \to 00, \quad s_2 \to 01, \quad s_3 \to 1\) ，由于该编码是前缀码，因此它是瞬时码，且其平均编码长度为：
\[ L(C) = \frac{1}{4} \cdot 2 + \frac{1}{2} \cdot 2 + \frac{1}{4} \cdot 1 = 1.75 \]
另一种二进制编码 \(D\) 如下：\(s_1 \to 00, \quad s_2 \to 1, \quad s_3 \to 01\) 。编码 \(D\) 和编码 \(C\) 用的是相同的码字，但是不同顺序。该编码同样是瞬时码，但其平均编码长度为：
\[ L(D) = \frac{1}{4} \cdot 2 + \frac{1}{2} \cdot 1 + \frac{1}{4} \cdot 2 = 1.5 \]
因此：\(L(D) < L(C)\)，可见 \(D\) 的平均编码长度更短。因此，\(V\) 是 \(S\) 的最优二进制编码，即：对于 \(S\) 的所有瞬时二进制编码 \(C\)，均有 \(L(D) \leq L(C)\)。
例 2.1 说明了一个普遍规律：通过给更频繁出现的源符号分配较短的编码词，可以减少平均编码长度。在编码 \(D\) 中，我们选择了 \(w_2 = 1\)，而不是在 \(C\) 中的 \(w_2 = 01\)，从而降低了平均编码长度。这种方法能够提高编码效率。莫尔斯电码（Morse Code） 也采用了相同的策略：对于高频使用的字符（如 “E”、“T”），使用较短的编码，而对于低频字符（如 “Q”、“Z”），使用较长的编码，从而提高通信效率。
练习 2.1
证明在任何最优编码（optimal code）中，若 \(p_i > p_j\)，则 \(l_i \leq l_j\)。
我们将在后面的章节中更系统地使用这一原则，以构造任意信息源的最优编码。首先，我们证明：允许使用唯一可译码（而非瞬时码）的编码方式，不能进一步降低平均编码长度。因此将编码限制为瞬时码上并不会造成任何损失。这一结论可以直接从 §1.6 中的推论 1.22 得出。从而，我们也有以下引理：
引理 2.2
对于给定的信息源 \(S\) 和整数 \(r\)，所有唯一可译 \(r\) 进制编码 \(C\) 的平均码长 \(L(C)\) 的集合，与所有瞬时 \(r\) 进制编码 \(C\) 的平均码长 \(L(C)\) 的集合是相等的。
这个平均码长的集合显然有下界（最小值至少为 0），因此我们用 \(L_{\min}(S)\) 来表示它的最大下界（greatest lower bound），这里默认 \(r\) 已知。如果一个瞬时 \(r\) 进制编码 \(C\) 满足 \(L(C) = L_{\min}(S)\)，则称其为最优码（optimal code）。
然而，最优码的存在性并不是显而易见的。理论上讲，瞬时 \(r\) 进制编码的平均码长可能无限接近但永远无法达到最大下界（就像数列 \(\frac{1}{n}\) 在 \(n \to \infty\) 时趋于 0，但从不等于 0）。因此，我们需要证明最优码总是存在的——这是文献中常常被忽略的一个重要点。
定理 2.3
对于每个信息源 \(S\)，以及每个 \(r \geq 2\) 的整数，都存在一个最优 \(r\) 进制编码。
证明
如果需要，可以重新编号源符号 \(s_1, \dots, s_q\) 。所以，我们假设存在某个整数 \(k\)，使得：
当 \(i \leq k\) 时，\(p_i > 0\)，
当 \(i > k\) 时，\(p_i = 0\)。
设 \(p = \min(p_1, \dots, p_k)\)，显然有 \(p > 0\)。
首先，至少存在一个瞬时 \(r\) 进制编码 \(C\) 适用于 \(S\)。例如，可以令 \(l_1 = \dots = l_q = l\)，其中 \(l\) 使得 \(r^l \geq q\)，然后根据定理 1.20构造一个瞬时编码。
为了证明本定理，只需证明：对于所有瞬时 \(r\) 进制编码 \(D\)，使得 \(L(D) \leq L(C)\) 的编码数量是有限的。那么这些编码的平均码长 \(L(D)\) 也只有有限多个值，其中的最小值一定被某个编码 \(D\) 取到，这个 \(D\) 就是最优编码。
为了证明这一点，考虑任意满足 \(L(D) \leq L(C)\) 的瞬时 \(r\) 进制编码 \(D\)，其码长 \(l_1, \dots, l_q\) 必须满足：
\[ l_i < \frac{L(C)}{p}, \quad \text{对于 } i = 1, \dots, k. \]
否则，将导致：
\[ L(D) = p_1 l_1 + \dots + p_q l_q \geq p_i l_i > p \frac{L(C)}{p} = L(C), \]
这与 \(L(D) \leq L(C)\) 矛盾。
在前述不等式的约束下，只有有限个单词 \(w \in T^+\)，满足 $ |w| $ ，因此 \(D\) 的码字选择 \(w_1, \dots, w_k\) 是有限的。对于 \(i > k\)，码字 \(w_i\) 的选取可以有无限多种可能，但由于 \(p_i = 0\)，这些码字不会影响 \(L(D)\) 的值。因此，\(L(D) \leq L(C)\) 的可能取值是有限的，其中的最小值必然可以由某个编码 \(D\) 取到，因此最优编码存在。
2.2 Binary Huffman Codes
1952 年，Huffman 提出了一个用于构造最优编码的算法。为简化讨论，我们主要关注二进制情况，即令 \(T = \mathbb{Z}_2 = \{0,1\}\) 。给定一个信息源 \(S\) ，我们首先按照概率大小对符号 \(s_1, \dots, s_q\) 进行重新编号，使其满足：
\[ p_1 \geq p_2 \geq \dots \geq p_q \]
然后，我们合并概率最小的两个符号 \(s_{q-1}\) 和 \(s_q\) ，形成一个新的符号：
\[ s' = s_{q-1} \vee s_q \quad (\text{表示} s_{q-1} \text{ 或 } s_q) \]
该新符号的概率为：\(p' = p_{q-1} + p_q\) 。如果 \(s_{q-1}\) 和 \(s_q\) 不唯一（即有多个符号满足概率最小），我们就任意选择两个概率最小的符号进行合并。这样，我们就得到了一个新的信息源 \(S'\) ，它包含 \(q-1\) 个符号：\(s_1, \dots, s_{q-2}, s'\) ，对应的概率分布为：\(p_1, \dots, p_{q-2}, p'\) 。
给定任何二进制编码 \(C'\) 适用于 \(S'\) ，我们可以利用 \(C'\) 来构造信息源 \(S\) 的编码 \(C\) ：
如果 \(C'\) 对于符号 \(s_i\)（ \(i = 1, \dots, q-2\) ）的编码是 \(w_i\)，那么 \(C\) 沿用相同的编码。
如果 \(C'\) 对于合并后的符号 \(s'\) 的编码是 \(w'\), 则 \(C\) 将 \(s_{q-1}\) 和 \(s_q\) 分别编码为 \(w'0\) 和 \(w'1\) 。
引理 2.4
如果编码 \(C'\) 是即时码，那么 \(C\) 也是即时码。
证明 如果 \(C'\) 是一个前缀码，则 \(C\) 也是前缀码，这一点很容易验证；由定理 1.17 可完成证明。 \(\square\)
这意味着，对于源 \(S\) （具有 \(q\) 个符号）的瞬时二进制码 \(C\) ，可以从的源 \(S'\) （具有 \(q - 1\) 个符号）的瞬时二进制码 \(C'\) 构造出 。同样，可以从具有 \(q - 2\) 个符号的源 \(S''\) 的瞬时二进制码 \(C''\) 构造出 \(S'\) 的瞬时二进制码 \(C'\) ，其中 \(S''\) 由 \(S'\) 通过合并两个最不可能出现的符号得到。
如果继续按此方式缩减源，我们将得到一系列源：
\[ S \to S' \to \dots \to S^{(q-2)} \to S^{(q-1)} \]
其符号数量依次减少，最终，\(S^{(q-1)}\) 仅包含一个符号 \(s_1 \vee \dots \vee s_q\) ，其概率为 1，我们用空字符串 \(\epsilon\) 对其进行编码，得到码： \(C^{(q-1)} = \{\epsilon\}\) 作为 \(S^{(q-1)}\) 的编码。
随后，通过给一个码字 \(w'\) 添加 0 和 1，我们可以得到 \(S^{(q-2)}\) 的瞬时二进制码：
\[ C^{(q-2)} = \{c_0 = 0, c_1 = 1\} \]
重复此过程 \(q - 1\) 次，我们最终获得一系列二进制码： \(C^{(q-1)}, C^{(q-2)}, \dots, C', C\) ，分别对应源： \(S^{(q-1)}, S^{(q-2)}, \dots, S', S\)。
\[ S \to S' \to \dots \to S^{(q-2)} \to S^{(q-1)} \]
\[ C \longleftarrow C' \longleftarrow \dots \longleftarrow C^{(q-2)} \longleftarrow C^{(q-1)} \]
最终得到的码 \(C\) 被称为源 \(S\) 的 Huffman 码。根据 引理 2.4 的反复使用，它是一个瞬时码，并且我们将在 §2.4 证明它是最优的。（注意，每个 \(C^{(i)}\) 都是 \(S^{(i)}\) 的 Huffman 码，因为我们可以选择忽略 \(s'\) 以及所有 \(j < i\) 的 \(C^{(j)}\) 码。）
例 2.5
设源 \(S\) 具有 \(q = 5\) 个符号 \(s_1, \dots, s_5\) ，其概率分别为 \(p_i = 0.3, 0.2, 0.2, 0.2, 0.1\)。
我们首先执行一系列 源缩减（source-reduction）操作；其连续的概率分布如下：
源 概率分布 \(S\) 0.3, 0.2, 0.2, 0.2, 0.1 \(S'\) 0.3, 0.3, 0.2, 0.2 \(S''\) 0.4, 0.3, 0.3 \(S'''\) 0.6, 0.4 \(S^{(4)}\) 1 在每一行中，我们通过将两个最小的概率替换为它们的和（用加粗表示）来形成下一行，并确保新概率集合按非递增顺序排列。然后，我们反向执行此过程，以构造源的哈夫曼编码，从底部的 \(S^{(4)}\) 开始，依次向上构造：
源 编码 \(C\) \(C\) 00, 10, 11, 010, 011 \(C'\) 00, 01, 10, 11 \(C''\) 1, 00, 01 \(C'''\) 0, 1 \(C^{(4)}\) \(\varepsilon\) 在反向构造编码时，每一行的编码是从其下一行的编码派生出来的：
对于下行中新合并的符号 \(w'\) ，我们在其编码后加上 0 或 1，得到 \(w'0, w'1\) ，分别对应合并前的两个符号。
其他编码保持不变。
最终得到的哈夫曼编码为： \(C = \{ 00, 10, 11, 010, 011 \}\)。编码的长度分别为：\(l_1 = 2, l_2 = 2, l_3 = 2, l_4 = 3, l_5 = 3\) ，则
\[ L(C) = \sum P_i l_i = 0.3 \times 2 + 0.2 \times 2 + 0.2 \times 2 + 0.2 \times 3 + 0.1 \times 3 = 2.3 \]
在大多数情况下，哈夫曼编码的构造过程是唯一的，因此生成的编码也是唯一的（仅在每一步分配 0 或 1 时可有不同选择，但不会影响码长）。然而，如果在某一步骤中有多个最小概率对，则哈夫曼编码可能有多个可能的结果，例如本例中的第一步。这种情况下，尽管编码可能不同，但平均码长 \(L(C)\) 仍然是唯一的，这是哈夫曼编码的最优性所保证的。
一般来说，概率 \(p_i\) 之间的变化越大，最优编码的平均码长就越短。 这是因为在这种情况下，我们有更大的空间为更频繁出现的符号分配更短的编码。我们将在第 3 章中更系统地研究这一现象，并使用熵（entropy）这一概念来衡量概率分布中的变化程度。
2.3 Average Word-length of Huffman Codes
让我们回到 §2.2 中的一般情况，并比较编码 \(C\) 和 \(C'\) 的平均码长。
在编码 \(C'\) 中，符号 \(s' = s_{q-1} \vee s_q\) 具有概率 \(p' = p_{q-1} + p_q\) ，并被分配一个编码 \(w'\) ，其长度记为 \(l = |w'|\) 。
在编码 \(C\) 中，符号 \(s'\) 被替换为两个符号 \(s_{q-1}\) 和 \(s_q\)，它们的概率分别为 \(p_{q-1}\) 和 \(p_q\) ，并被分配编码 \(w'0\) 和 \(w'1\) ，其长度为 \(l + 1\)。
所有其他符号 \(s_1, \dots, s_{q-2}\) 在 \(C'\) 和 \(C\) 中的编码保持不变，因此有：
\[ \begin{aligned} L(C) - L(C') & = p_{q-1} (l + 1) + p_q (l + 1) - (p_{q-1} + p_q) l\\ & = p_{q-1} + p_q\\ & = p' \end{aligned} \]
这就是将 \(S\) 归约为 \(S'\) 时生成的“新”概率。如果我们重复这一过程，并利用 \(L(C^{(q-1)}) = |\epsilon| = 0\) ，则可得：
\[ \begin{aligned} L(C) & = (L(C) - L(C')) + (L(C') - L(C'')) + \dots + (L(C^{(q-2)}) - L(C^{(q-1)})) + L(C^{(q-1)})\\ & = (L(C) - L(C')) + (L(C') - L(C'')) + \dots + (L(C^{(q-2)}) - L(C^{(q-1)}))\\ & = P' + P'' + \dots + P^{(q-1)} \end{aligned} \]
这等于在将 \(S\) 归约为 \(S^{(q-1)}\) 过程中生成的所有新概率 \(p', p'', \dots, p^{(q-1)}\) 的总和。
例如，在例 2.5（§2.2）中，我们将加粗的概率相加，得到：
\[ L(C) = 0.3 + 0.4 + 0.6 + 1 = 2.3 \]
这种方法是一个极大的省力工具，因为它允许我们计算 \(L(C)\) 而无需实际构造编码 \(C\)。例如，在例 2.5 中，从给定的概率 \(p_i = 0.3, 0.2, 0.2, 0.2, 0.1\) 可以清楚地看出，通过依次合并最小的概率对，我们得到：
\[ p' = 0.2 + 0.1 = 0.3\\ p'' = 0.2 + 0.2 = 0.4\\ p''' = 0.3 + 0.3 = 0.6\\ p'''' = 0.4 + 0.6 = 1 \]
2.4 Optimality of Binary Huffman Codes
在本节中，我们将证明二进制 Huffman 编码是最优的。首先，我们需要一个定义和一个引理。
定义 2.6
如果两个二进制单词 \(w_1\) 和 \(w_2\) 具有形式 \(x0\) 和 \(x1\) （或反之），其中 \(x \in T^*\) ，则称它们为兄弟（siblings）。
引理 2.7
对于任何源 \(S\) ，都存在一个最优二进制编码 \(V\) ，且其中两个最长的编码单词是兄弟。
证明
根据定理 2.3，\(S\) 存在一个最优二进制编码。在所有这样的编码中，选择一个 \(D\) 使得：\(\sigma(D) = \sum l_i\) 最小，其中 \(\sigma(D)\) 是所有编码单词的长度总和（由于长度是非负整数，这样的 \(D\) 是存在的）。我们断言 \(D\) 具有所需的性质。
选择 \(D\) 中最长的编码单词，设其形式为 \(xt\) ，其中 \(x \in T^*\) ，\(t \in T = Z_2\) 。
令 \(\bar{t} = 1 - t\) ，即如果 \(t = 1\) ，则 \(\bar{t} = 0\) ，反之亦然。
如果 \(x\bar{t} \in D\) ，那么 \(xt\) 和 \(x\bar{t}\) 就是所需的兄弟单词，证明完成。
假设 \(x\bar{t} \notin D\) 。由于 \(D\) 是前缀码，那么 \(D\) 中前缀为 \(x\) 的唯一编码单词是 \(xt\) （因为 \(|xt|\) 是最长的，并且 \(x\bar{t} \notin V\) ）。
现在用 \(x\) 取代 \(xt\) 得到新的编码 \(D'\) ，由于 \(D'\) 仍然是前缀码，所以它也是一个瞬时码。
但是，\(V'\) 的长度总和： \[ \sigma(D') = \sigma(D) - 1 < \sigma(D) \] 这与我们对 \(D\) 的选择相矛盾（因为 \(D\) 是使 \(\sigma(D)\) 最小的最优编码）。
因此，\(x\bar{t} \in V\)，即 \(xt\) 和 \(x\bar{t}\) 必然存在于 \(V\) 中，它们是兄弟单词，证明完毕。
定理 2.8
如果 \(C\) 是源 \(S\) 的二进制 Huffman 码，则 \(C\) 是 \(S\) 的最优码。
证明
引理 2.4 表明 \(C\) 是瞬时码，因此只需要证明 \(L(C)\) 是最小的（在所有源 $ S $ 的瞬时二进制码的平均字长中）。我们通过对源符号数 \(q\) 使用数学归纳法来证明。
如果 \(q = 1\) ，则 \(C = \{\epsilon\}\)，且 \(L(C) = 0\) ，因此结论显然成立。
因此我们可以假设 $ q > 1 $ ，并且假设对于所有具有 $ q - 1 $ 个符号的源，结论已经证明。
设 \(S'\) 是通过在 §2.2 中所述的方式对 \(S\) 进行简化得到的源，所以 \(S'\) 具有 \(q-1\) 个符号 \(s_1, \ldots, s_{q-2}, s' = s_{q-1} \cup s_q\) 。根据 §2.3 公式，我们有：\(L(C) - L(C') = p_{q-1} + p_q = p'\) ，其中 \(p'\) 是 \(s'\) 的概率。
现在设 \(D: s_i \to x_i\) 为由引理 2.7 给出的 \(S\) 的最优二进制码，其中 \(D\) 具有一对最长的兄弟码字 \(x_u = x0\) 和 \(x_v = x1\) ，表示源 \(S\) 的符号 \(s_u\) 和 \(s_v\) 。我们将证明可以假设 \(u = q-1\) 和 \(v = q\) 。
如果 \(v \neq q\)，则我们可以交换分配给 \(s_v\) 和 \(s_q\) 的码字 \(x_v\) 和 \(x_q\) ，得到另一个源 \(S\) 的瞬时码 \(D^*\) 。如果 \(m_i\) 表示码字 \(x_i\) 的长度，则该交换将替换 \(p_v m_v + p_q m_q\) 在 $ L(D) $ 中的项，改为 \(p_v m_q + p_q m_v\) 在 $ L(D^*) $ 中的项。现在：
\[ (p_v m_v + p_q m_q) - (p_v m_q + p_q m_v) = (p_v - p_q)(m_v - m_q) \geq 0 \]
这是因为 \(p_v \geq p_q\) 且 \(m_v \geq m_q\) ，因此 \(L(D) \geq L(D^*)\) 。由于 \(D\) 是最优的，这意味着 \(L(D) = L(D^*)\) ，并且 \(D^*\) 也是最优的。因此，我们可以在必要时将 $ D $ 替换为 $ D^* $ ，从而假设 \(v = q\) 。类似的论证使得我们可以假设 \(u = q - 1\) ，因此 \(D\) 中的兄弟码字 \(x0\) 和 \(x1\) 是 $ s_{q-1} $ 和 $ s_q $ 的码字。
接下来我们为 \(S'\) 形成一个码 \(D'\) ，其中 \(s_i \to x_i\) 对于 \(i = 1, \ldots, q-2\) ，并且 \(s' \to x\) 。因此，\(D\) 与 \(D'\) 的关系与 \(C\) 与 \(C'\) 的关系相同。特别地，应用 §2.3 中的论证，得到：
\[ L(D) - L(D') = p_{q-1} + p_q = L(C) - L(C') \]
因此，
\[ L(D') - L(C') = L(D) - L(C) \]
现在，\(C'\) 是 \(S'\) 的一个 Huffman 码，\(S'\) 是一个具有 \(q-1\) 个符号的源，因此根据归纳假设，\(C'\) 是最优的；因此，\(L(C') \leq L(D')\) ，从而有 \(L(C) \leq L(D)\) 。由于 \(D\) 是最优的，\(C\) 也是最优的（且 \(L(C) = L(V)\) ）。
2.5 r-ary Huffman Codes
如果我们使用一个字母表 \(T\) ，且其大小 \(|T| = r > 2\) ，那么构建 \(r\) 进制 Huffman 码的方法与二进制情况类似。给定一个源 \(S\)，我们依次形成一系列简化后的源 \(S', S'', \dots\) ，每次将 \(r\) 个最不可能的符号 \(s_i\) 合并成一个符号 \(s'\) ，并将它们的概率相加得到 \(s'\) 的概率 \(p'\) 。
最终我们希望将源 \(S\) 简化为一个只有一个符号（概率为1）的源，并为该符号分配码字 \(\epsilon\) 。由于每一步简化过程都会减少 \(r - 1\) 个符号，因此只有当 \(q \equiv 1 \mod (r - 1)\) 时，简化过程才是可能的。当 \(r = 2\) 时，这个条件始终满足，但当 \(r > 2\) 时不一定满足。如果 \(q \not\equiv 1 \mod (r - 1)\)，我们可以向 \(S\) 中添加足够多的符号 \(S_i\)，其概率 \(p_i = 0\)，通过增加 \(q\) 来使得这个同余条件成立，然后继续进行简化过程。
例 2.9
设 \(q = 6\) 和 \(r = 3\) 。由于 \(r - 1 = 2\) ，我们需要 \(q \equiv 1 \mod (2)\) ，因此我们向 \(S\) 中附加一个额外的符号 \(s_7\) ，其概率 \(p_7 = 0\) 。然后，简化过程产生了源 \(S'\) , \(S''\) 和 \(S'''\) ，它们的符号数量分别为 5、3 和 1。
构造码 \(C\) 的过程与二进制情况类似。给定源 \(S^{(i)}\) 的码 \(C^{(i)}\) ，我们为源 \(S^{(i-1)}\) 构造码 \(C^{(i-1)}\) ：这是通过移除新符号 \(s'\) 的码字 \(w'\)，并用 \(S^{(i-1)}\) 中合并成 \(s'\) 的 \(r\) 个符号的码字 \(w't\)（ \(t \in T\) ）替换它。通过迭代这一过程，我们最终得到源 \(S\) 的 \(r\) 进制 Huffman 码 \(C\) ，并删除开始时附加的任何额外符号 \(s_i\) 的码字。
例 2.10
设 \(q = 6\) 和 \(r = 3\) ，如同在例 2.9 中所述，并且假设源 \(S\) 的符号 \(s_1, \dots, s_6\) 的概率为 \(p_1 = 0.3, p_2 = 0.2, p_3 = 0.2, p_4 = 0.1, p_5 = 0.1, p_6 = 0.1\) 。在附加了 \(s_7\) 并使其概率 \(p_7 = 0\) 后，简化过程如下，将给定的概率分布整理成表格的形式。
\(S\) 0.3 0.2 0.2 0.1 0.1 0.1 0 \(S'\) 0.3 0.2 0.2 0.2 0.1 \(S''\) 0.5 0.3 0.2 \(S'''\) 1 如果我们取 \(T = \mathbb{Z}_3 = \{0, 1, 2\}\) ，那么一种可能的编码过程是：
\(C\) 1 2 00 02 010 011 012 \(C'\) 1 2 00 01 02 \(C''\) 0 1 2 \(C'''\) \(\epsilon\) 删除附加符号 \(s_7\) 的码字 \(012\) 后，我们得到源 \(S\) 的三进制 Huffman 码：\(C = \{ 1, 2, 00, 02, 010, 011 \}\) ，且平均码长为 \(L(C) = 1.7\) 。
2.6 Extensions of Sources
与其一次编码一个源符号 \(s_i\)，更高效的方法是对连续的符号块进行编码。例如，在文本中，与其单独编码每个字母，不如对整个单词（甚至句子）进行编码。这种方法能提供更丰富的概率变化，从而降低平均码长（正如§2.2中所述）。
设 \(S\) 为一个源，其源字母表为 \(S\)，包含 \(q\) 个符号 \(s_1, \dots, s_q\)，其对应的概率为 \(p_1, \dots, p_q\)。源 \(S\) 的第 \(n\) 次扩展 $S^n $是一个新的源，其源字母表 \(S^n\) 由 \(q^n\) 个符号 \(s_{i_1} \dots s_{i_n}\) 组成（其中 \(s_{i_j} \in S^n\) ），每个符号的概率为：\(p_{i_1} \cdots p_{i_n}\)。我们可以将 \(s_{i_1} \dots s_{i_n}\) 看作是来自 \(S\) 的 \(n\) 个连续符号组成的一个块，或者等价地视为 \(n\) 个独立的 \(S\) 副本同时输出一个符号（例如，想象同时投掷多个相同的硬币或掷多个相同的骰子）。我们可以验证，概率 \(p_{i_1} \cdots p_{i_n}\) 形成一个概率分布，只需展开以下等式的左侧：
\[ (p_1 + \cdots + p_q)^n = 1^n = 1 \]
并注意到每个 \(p_{i_1} \cdots p_{i_n}\) 在展开中恰好出现一次。
例 2.11
设 \(S\) 的源字母表为 \(S = {s_1, s_2}\) ，其中 \(p_1 = \frac{2}{3}\)，\(p_2 = \frac{1}{3}\) 。那么，\(S^2\) 的源字母表为：\(S^n = \{s_1s_1, s_1s_2, s_2s_1, s_2s_2\}\) ，其对应的概率为：\(\frac{4}{9}, \frac{2}{9}, \frac{2}{9}, \frac{1}{9}\)。
一般来说，设 \(p_1\) 和 \(p_q\) 分别是 \(S\) 中最大的和最小的概率，那么 \(S^n\) 中的最大和最小概率也分别是 \({p_1}^n\) 和 \({p_q}^n\)。
假设 \(p_1 > p_q\)（即，概率 \(p_i\) 不全相等于 \(1/q\) ），那么我们有：
\[ \frac{p_1^n}{p_q^n} \to \infty \quad \text{When} \quad n \to \infty \]
这意味着，随着 \(n\) 的增加，\(S^n\) 的概率分布变得更加不均匀，因此可以期望更高效的编码。
例 2.12
如果 \(S\) 如例 2.11 所示，则存在一个二进制 Huffman 编码 \(C\)：\(s_1 \to 0, \quad s_2 \to 1\)，其平均码长为：\(L(C) = 1\)，乍一看，似乎无法进一步优化，但我们仍然可以为 \(S^2\) 构造 Huffman 编码。我们使用 §2.2 描述的算法进行如下操作（每行的概率未按降序排列）：
\(S^2\) \(\frac{4}{9}\) \(\frac{2}{9}\) \(\frac{2}{9}\) \(\frac{1}{9}\) 0 10 110 111 \((S^2)'\) \(\frac{4}{9}\) \(\frac{2}{9}\) \(\frac{3}{9}\) 0 10 11 \((S^2)''\) \(\frac{4}{9}\) \(\frac{5}{9}\) 0 1 \((S^2)'''\) \(1\) \(\epsilon\) 这给出了 \(S^2\) 的 Huffman 编码 \(C^2\) ：
\[ s_1 s_1 \to 0, \quad s_1 s_2 \to 10, \quad s_2 s_1 \to 110, \quad s_2 s_2 \to 111 \]
其平均码长为：\(L_2 = L(C_2) = \frac{2}{9} + \frac{3}{9} + \frac{5}{9} + \frac{1}{9} = \frac{17}{9}\)。
由于 \(C^2\) 中的每个码字代表 \(S\) 的两个符号块，因此平均而言，每个 \(S\) 的符号需要：\(\frac{L_2}{2} = \frac{17}{18} \approx 0.944\)。这小于 \(S\) 的 Huffman 编码 \(C\) 的平均码长 \(L(C) = 1\)，因此这种编码方式更高效。
严格来说，我们所描述的并不是 \(S\) 的一个编码，因为 \(S\) 的各个单独符号并未被分配它们自己的编码词；尽管如此，它使我们能够对来自 \(S\) 的信息进行编码，因此我们称之为 \(S\) 的编码。这样的编码是唯一可解码的：作为 \(S^2\) 的编码，Huffman 码 \(C^2\) 是瞬时的，因此是唯一可解码的；这意味着我们可以将任何编码序列 \(t\) 唯一地分解为编码词，从而确定编码在 \(t\) 中的 \(S^2\) 的符号 \(s_{i_1}s_{i_2}\) ，并由此得到编码在 \(t\) 中的 \(S\) 的各个单独符号 \(s_i\) 。然而，这种解码并非完全瞬时的：我们必须成对地依次确定 \(S\) 的符号，而不是一次确定一个，因此在等待配对完成时存在一定的有限延迟。
继续这一原则，可以证明 \(S^3\) 的 Huffman 码 \(C^3\) 的平均词长 \(L_3 = L(C^3) = 76/27\) ；作为 \(S\) 的编码，它的平均词长为
\[ \frac{L_3}{3} = \frac{76}{81} = 0.938\ldots \]
这比使用 \(C_2\) 还要好。
这一想法显然可以扩展到任意 \(n\) 的 \(S^n\) ，由此引出了两个自然的问题：当 \(n \to \infty\) 时，平均词长 \(L_n / n\) 会发生什么变化，其中 \(L_n = L(C_n)\) ；以及我们能否应用相同的方法来获得其他信源更有效的编码？要回答这些问题，我们需要引入下一个重要主题，即熵（entropy）。