码作为树
前缀免费码映射到二叉树：根代表解码的开始，左支表示位0，右支表示位1，叶子表示完整的码字。
几何约束：每个叶子终止一个根到叶子的路径。没有叶子可以有一个后代（如果有，那么它的码字将是后代的前缀，违反前缀免费性质）。
这给Kraft不等式提供了几何解释：
每个深度为d的叶子‘占用’总树容量的1/2^(−d)。 深度为D的完全二叉树的总容量为1。前缀免费码使用不同深度的叶子；Kraft和度量总占用量。
Kraft和度量为1：完全码（每个路径都结束在一个叶子上——完美填充）。
Kraft和度量<1：不完整码（一些树容量未使用——可以添加更多符号）。
Kraft和度量>1：前缀免费码不可能（一些路径将不得不共享一个叶子）。
更深的叶子=更长的码=更少的容量
深度为1的叶子使用了树容量的一半（2^(−1) = 0.5）。
深度为3的叶子使用了1/8（2^(−3) = 0.125）。
将一个短码字放在树的高处会阻止所有它的后代被使用——你用一个短码来交换很多潜在的长码。
构建前缀免费树
考虑5个符号的长度l = {1, 2, 3, 3, 3}。Kraft和度量 = 2^(−1) + 2^(−2) + 3·2^(−3) = 0.5 + 0.25 + 0.375 = 1.125 > 1。
这超过1：这些长度与前缀免费码不兼容。在一个长度必须增加。
修复：将l_1从1改为2。新的长度{2, 2, 3, 3, 3}：Kraft = 2·2^(−2) + 3·2^(−3) = 0.5 + 0.375 = 0.875 < 1。有效，但不完整。
修复：将l_1从2改为2，添加l_2 = 3以使用剩余容量。Kraft = 0.875；剩余 = 0.125 = 2^(−3)：有一个更多深度为3的叶子。
为什么熵限制了码字长度
Kraft不等式限制了码字的结构（长度必须符合树的要求）。Shannon的熵限制了码字的效率（平均长度无法超过理论下限）。
最优码长。 对于一个概率为p_i的符号，理想的码长是log₂(1/p_i)。稀有符号应该有长的码；频繁的符号应该有短的码。这与Kraft等式相似：2^(−l_i) = p_i 当l_i = log₂(1/p_i)。
但是log₂(1/p_i)很少是整数。向上取整到⌈log₂(1/p_i)⌉得到Huffman长度，它满足H ≤ L < H + 1。
几何解释。 将每个符号绘制为在二叉树的深度l_i处的点。Kraft和度量总体叶子覆盖面积。熵衡量的是加权平均深度，根据概率加权。Shannon定理：加权平均深度≥加权信息内容。
熵下界验证
这个例子：p = [1/2, 1/4, 1/8, 1/8] 对于符号{A, B, C, D}。
最优长度：l_A = log₂(2) = 1，l_B = log₂(4) = 2，l_C = log₂(8) = 3，l_D = log₂(8) = 3。
这些都是整数 —— 完美匹配。Huffman码：A=0, B=10, C=110, D=111。
L = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 0.5 + 0.5 + 0.375 + 0.375 = 1.75。
H = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 1.75. L = H exactly: optimal code.
一个完整的例子
完整流程：给定概率，计算熵，验证码子满足界限。
源：p(A)=0.5，p(B)=0.25，p(C)=0.125，p(D)=0.125。
H = 1.75 bits (computed above).
一个简单的块码：4 个符号 → 每个 2 位 → L = 2.0。熵率超过：2.0 − 1.75 = 0.25 bits/symbol = 12.5% waste。
变长码比定长码节省了 12.5%。对于长消息，这将是巨大的。
英文的熵率。香农估计书面英文的熵率在大约 1.0 到 1.3 bits per character，尽管使用 5 位 ASCII 码。这个 4:1 的比率反映了自然语言的巨大冗余——常见字母聚集，词重复，语法限制序列。
压缩无法超过熵
压缩比：H / (块码长度)。对于我们的例子：1.75/2.0 = 0.875 — 87.5% 效率。
你能再压缩更多吗？只有通过上下文：如果你将符号的 n-grams 一起编码，联合熵 H(X,Y) 可能小于 2·H(X) 由于统计依赖。这是噪声less 编码定理的扩展到 n-grams。