贪心策略为何最优
哈夫曼算法是一个贪心算法：在每一步，它做出局部最优的选择（合并两个最廉价的节点），而不向前看。贪心算法并非总是全局最优的，但在这里是的。
最优性论证
假设编码 C 的平均长度最少为 L。考虑两个概率最低的符号，比如 p_a 和 p_b。在任何最优编码中，这两个符号必须在树的最深层级作为兄弟叶子出现。为什么？
如果它们没有共享父节点，你可以将更深的符号与更短的编码交换，从而减少 L。因此最深的叶子必须是最不可能的符号。
现在，如果你将 a 和 b 组合成一个元符号 ab（p_ab = p_a + p_b），那么对于减少一个符号的缩小字母表的任何最优编码都正好是缩小问题上的哈夫曼编码。归纳法完成了这个论证。
几何视角
哈夫曼算法自下而上构造二叉树，将最不可能的符号放在最大深度处。这最小化了 Σ 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) → 根(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 比特。
码长方差
两个哈夫曼编码可能达到相同的 L，但有不同的码长分布。码长的方差测量这种分布：
Var(l) = E[l²] − (E[l])²
其中 E[l] = L（平均码长）且 E[l²] = Σ p_i · l_i²。
为什么方差很重要：
1. 缓冲区要求。 在实时解码中，每个符号需要可变数量的比特。高方差意味着某些符号需要许多比特 — 你需要一个更大的输入缓冲区来保证你总能读到一个完整的符号。
2. 解码延迟。 高方差编码有长的最坏情况解码路径。低方差（灌木状）编码更紧密地限制最坏情况。
3. 鲁棒性。 高方差编码中的一个丢失比特会造成更多的同步损害，因为长编码字必须完全重新读取。
哈明的建议：当存在多个有效的哈夫曼编码（破平选择）时，更倾向选择方差较低的 — 灌木状树。
计算两棵树的方差
使用 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 符号哈夫曼编码端到端
一个完整的端到端示例：构建哈夫曼编码、计算 L、计算 H、验证 L ≥ H、计算 Var。
源：p(X)=0.6、p(Y)=0.3、p(Z)=0.1。
哈夫曼构造：
步骤 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) → 根(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。高于熵 8.1%。
方差： 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。
你的转向：完整管道
供参考的 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。