贪婪策略为什么是最优的
Huffman 算法是一个 贪婪算法：在每个步骤中，它都选择局部最优选择（合并两者最便宜的节点）而不考虑未来。贪婪算法并不总是全局最优——但在这里，它们是。
最优性论证
假设一个代码 C 具有最小平均长度 L。考虑一下概率最低的两个符号，例如 p_a 和 p_b。在任何最优代码中，这两个符号必须以树的最深层次作为同胞叶子。为什么？
如果它们没有共享一个父节点，你可以将更深的符号与更短的代码交换——减少 L。因此，最深的叶子必须是最不可能的符号。
现在，如果将 a 和 b 组合成一个元符号 ab (具有 p_ab = p_a + p_b)，任何最优代码的减少字母表是精确的 Huffman 代码。归纳法完成了论证。
几何视图
Huffman 算法从下至上构建二进制树，将最不可能的符号置于最大深度。这最小化了 Σ p_i · depth(i) = L。
等价视图：您正在为树叶分配标签，以便最小化加权路径长度，其中每个叶子的权重是其概率。
执行贪婪步骤
概率：p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1。总和为 1.0 ✓
第 1 步：最低两者：C(0.2)、D(0.1)。合并→ CD(0.3)。列表：A(0.4)、B(0.3)、CD(0.3)。
第 2 步：最低两者：B(0.3)、CD(0.3)（打平——任意一个都有效）。合并→ BCD(0.6)。列表：A(0.4)、BCD(0.6)。
第 3 步：合并 A(0.4)、BCD(0.6)→ root(1.0)。分配 A=0, BCD=1。
逆向：BCD → B=10 (l=2)、CD=11 → C=110 (l=3)、D=111 (l=3)。
L = 0.4·1 + 0.3·2 + 0.2·3 + 0.1·3 = 0.4+0.6+0.6+0.3 = 1.9 位。
代码长度方差
两种 Huffman 代码可能以相同的 L 实现，但它们的代码长度分布可能不同。代码长度方差衡量这种分布范围：
Var(l) = E[l²] − (E[l])²
其中 E[l] = L（平均代码长度）和 E[l²] = Σ p_i · l_i²。
为什么方差重要：
1. 缓冲区需求。 在实时解码中，每个符号需要消耗不同的比特数。 方差较大意味着某些符号需要多比特数 — 你需要一个更大的输入缓冲区来保证你总是能读取到完整的符号。
2. 解码延迟。 方差较大的代码具有较长的最坏情况解码路径。低方差（繁茂）代码对最坏情况进行更紧密的约束。
3. 鲁棒性。 在高方差代码中，丢失一个比特可能导致更严重的同步损坏，因为长的编码单元必须重新读取。
Hamming 的建议：在多个有效 Huffman 代码中（在多个有效 Huffman 代码中进行选择时），优先选择方差较低的代码 —— 繁茂树。
计算两棵树的方差
使用 p(A)=0.4，p(B)=0.3，p(C)=0.2，p(D)=0.1 和代码 A=0，B=10，C=110，D=111：
E[l] = L = 1.9
E[l²] = 0.4·1² + 0.3·2² + 0.2·3² + 0.1·3² = 0.4+1.2+1.8+0.9 = 4.3
Var = 4.3 − 1.9² = 4.3 − 3.61 = 0.69
3符号Huffman代码从头到尾
一个完整的从头到尾示例：构建Huffman代码、计算L、计算H、验证L ≥ H、计算Var。
源：p(X)=0.6，p(Y)=0.3，p(Z)=0.1。
Huffman构建：
步骤1：排序：X(0.6)，Y(0.3)，Z(0.1)。最低两者：Y(0.3)，Z(0.1)。
合并→ YZ(0.4)。列表：X(0.6)，YZ(0.4)。
步骤2：合并 X(0.6)，YZ(0.4) → root(1.0)。分配 X=0，YZ=1。
YZ → Y=10，Z=11。
代码：X=0（l=1），Y=10（l=2），Z=11（l=2)。
L = 0.6·1 + 0.3·2 + 0.1·2 = 0.6 + 0.6 + 0.2 = 1.4比特。
熵： H = −0.6·log₂(0.6) − 0.3·log₂(0.3) − 0.1·log₂(0.1)
log₂(0.6) ≈ −0.737，log₂(0.3) ≈ −1.737，log₂(0.1) ≈ −3.322
H = 0.6·0.737 + 0.3·1.737 + 0.1·3.322 = 0.442 + 0.521 + 0.332 = 1.295比特。
L = 1.4 ≥ H = 1.295 ✓。L/H = 1.4/1.295 ≈ 1.081。1.8%高于熵。
方差： E[l²] = 0.6·1 + 0.3·4 + 0.1·4 = 0.6+1.2+0.4 = 2.2。Var = 2.2 − 1.4² = 2.2 − 1.96 = 0.24。
你的 turno：一个完整的管道
参考的log₂值：log₂(0.5)=−1.000，log₂(0.25)=−2.000，log₂(0.125)=−3.000，log₂(0.375)≈−1.415，log₂(0.625)≈−0.678。