哈夫曼编码加权平均长度计算示例
假设有一个字符集及其出现概率如下：
字符概率A0.4B0.3C0.2D0.1
步骤1：构建哈夫曼树
1. 排序：按概率从小到大排序 → D(0.1), C(0.2), B(0.3), A(0.4)
2. 合并最小概率的两个节点：
合并 D(0.1) 和 C(0.2) → 新节点 P1(0.3)
现在队列：B(0.3), P1(0.3), A(0.4)
3. 继续合并：
合并 B(0.3) 和 P1(0.3) → 新节点 P2(0.6)
现在队列：A(0.4), P2(0.6)
4. 最后合并：
合并 A(0.4) 和 P2(0.6) → 根节点（概率1.0）
步骤2：分配编码
左分支 = 0，右分支 = 1（或相反，不影响最终平均长度）：
A(0.4) → `0`（长度1）
B(0.3) → `10`（长度2）
C(0.2) → `110`（长度3）
D(0.1) → `111`（长度3）
步骤3：计算加权平均长度
验证最优性
香农熵（理论最小平均长度）：
比较：哈夫曼编码的 L=1.9接近熵 H≈1.846，且满足H≤L 另一个例子（固定长度 vs 哈夫曼编码） 假设字符集：A(0.7), B(0.2), C(0.1) 固定长度编码（2比特/符号） 编码：A=`00`, B=`01`, C=`10` 平均长度：2×0.7+2×0.2+2×0.1=2 比特/符号 哈夫曼编码 1. 合并 C(0.1) 和 B(0.2) → P1(0.3) 2. 合并 P1(0.3) 和 A(0.7) → 根节点(1.0) 3. 编码： A(0.7) → `0`（长度1） B(0.2) → `10`（长度2） C(0.1) → `11`（长度2） 4. 平均长度： L=(0.7×1)+(0.2×2)+(0.1×2)=0.7+0.4+0.2=1.3 比特/符号 压缩率提升：相比固定长度（2比特），哈夫曼编码（1.3比特）节省了35%空间！ 总结 哈夫曼编码通过动态分配短码给高频字符，最小化加权平均长度。 计算步骤： 1. 按概率升序排序； 2. 反复合并最小概率的节点，构建哈夫曼树； 3. 分配编码（左0右1或反之）； 4. 计算 。 哈夫曼树 WPL（带权路径长度）计算示例 WPL（Weighted Path Length，带权路径长度）是哈夫曼树的一个重要指标，表示所有叶子节点的权值 × 路径长度之和。它直接影响哈夫曼编码的加权平均长度。 计算公式 其中： 权值：通常是字符的频率或概率； 路径长度：从根节点到该叶子节点的边数（即编码位数）。 示例1：计算给定哈夫曼树的 WPL 假设已经构建好如下哈夫曼树（数字代表权值）： (100) / \ (40) (60) / \ (25) (35) 叶子节点： 左子树：40（路径长度=1） 右子树的左：25（路径长度=2） 右子树的右：35（路径长度=2） 计算 WPL： 示例2：从字符频率构建哈夫曼树并计算 WPL 给定字符频率： 字符频率A5B9C12D13E16F45 步骤1：构建哈夫曼树 1. 按频率升序排列：A(5), B(9), C(12), D(13), E(16), F(45)。 2. 每次合并最小的两个节点： 合并 A(5) + B(9) → P1(14) 合并 C(12) + D(13) → P2(25) 合并 P1(14) + E(16) → P3(30) 合并 P2(25) + P3(30) → P4(55) 合并 F(45) + P4(55) → 根节点(100) 最终哈夫曼树结构： (100) / \ F(45) (55) / \ (25) (30) / \ / \ C(12) D(13) P1(14) E(16) / \ A(5) B(9) 步骤2：计算 WPL F(45)：路径长度=1 → 45×1=45 C(12)：路径长度=3 → 12×3=36 D(13)：路径长度=3 → 13×3=39 A(5)：路径长度=4 → 5×4=20 B(9)：路径长度=4 → 9×4=36 E(16)：路径长度=3 → 16×3=48 示例3：验证 WPL 与哈夫曼编码的关系 对上述字符集进行哈夫曼编码： F(45)：`0`（长度1） C(12)：`100`（长度3） D(13)：`101`（长度3） A(5)：`1100`（长度4） B(9)：`1101`（长度4） E(16)：`111`（长度3） 计算加权平均编码长度： 结论：WPL（224）除以总频率（100）即为加权平均长度（2.24），两者直接相关。 关键点总结 1. WPL 是哈夫曼树的带权路径长度，等于所有叶子节点的（权值×路径长度）之和。 2. 哈夫曼编码的加权平均长度 = WPL / 总频率。 3. 构建哈夫曼树时，每次合并权值最小的两个节点，确保 WPL 最小。