码作为树
前缀无关码映射到二进制树：根表示解码的开始，左分支表示比特0，右分支表示比特1，叶子节点表示完整的码字。
几何约束：每个叶子终止一条从根到叶子的路径。没有叶子可以有后代节点（如果有，它的码字将是后代码字的前缀，违反前缀无关性）。
这给了Kraft不等式一个几何解释：
深度d处的每个叶子'占据'总树容量的2^(−d)的分数。 深度D处的完全二进制树的总容量是1。前缀无关码在各种深度使用叶子；Kraft和测量总占用。
Kraft和 = 1：完整码（每条路径都以叶子结尾——完美打包）。
Kraft和 < 1：不完整码（某些树容量未使用——可以添加更多符号）。
Kraft和 > 1：对于前缀无关码不可能（某些路径将不得不共享叶子）。
更深的叶子 = 更长的码 = 更少的容量
深度1处的叶子使用树容量的一半（2^(−1) = 0.5）。
深度3处的叶子使用八分之一（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等式：当l_i = log₂(1/p_i)时，2^(−l_i) = p_i。
但log₂(1/p_i)很少是整数。向上舍入到⌈log₂(1/p_i)⌉给出Huffman长度，其满足H ≤ L < H + 1。
几何读法。 在深度l_i处将每个符号绘制为二进制树上的一点。Kraft和测量总叶子覆盖。熵测量加权平均深度，按概率加权。Shannon定理：概率加权的平均深度≥概率加权的信息含量。
熵界验证
已做的示例：符号{A, B, C, D}的p = [1/2, 1/4, 1/8, 1/8]。
最优长度：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恰好：最优码。
一个完整的已做示例
完整的流程：给定概率，计算熵，验证码满足界限。
信源：p(A)=0.5，p(B)=0.25，p(C)=0.125，p(D)=0.125。
H = 1.75比特（上面计算的）。
一个朴素的块码：4个符号→每个2比特→L = 2.0。相对于熵的开销：2.0 − 1.75 = 0.25比特/符号 = 12.5%浪费。
与定长码相比，变长码节省12.5%。对于大消息，这是可观的。
英文的熵率。 Shannon估计书面英文的熵约为每字符1.0到1.3比特，尽管使用了5比特ASCII码。这个4:1的比率反映了自然语言中的巨大冗余——常见字母聚集，单词重复，语法约束序列。
压缩无法超越熵
压缩比：H /（块码长度）。对于我们的示例：1.75/2.0 = 0.875——87.5%的效率。
您可以进一步压缩吗？只有通过使用上下文：如果您一起编码符号对或三元组，由于统计依赖性，联合熵H(X,Y)可能小于2·H(X)。这是无噪声编码定理向n-grams的扩展。