沟通信息英语

平均码长=(4 * 0.09+3 * 0.15+4 * 0.04+4 * 0.07+2 * 0.28+4 * 0.08+2 * 0.21+3 * 0.18)/65438。

假设有n个权重，构造的霍夫曼树有n个叶节点。n个权重分别设置为w1，w2，wn，那么构建霍夫曼树的规则如下:

(1) w1，w2，wn视为有n棵树的森林(每棵树只有一个节点)；

(2)从森林中选择根节点权重最小的两棵树，合并为新树的左右子树，新树的根节点权重为左右子树的根节点权重之和；

(3)从森林中删除两个选择的树，并向森林中添加新的树；

(4)重复步骤(2)和(3)，直到森林中只剩下一棵树，这就是得到的霍夫曼树。

霍夫曼树不是唯一的，但是它的加权路径长度是唯一的。

扩展数据:

霍夫曼编码的具体方法:先按照出现的概率排队，将两个最小概率相加作为新概率和剩余概率，然后将两个最小概率相加，再重新排队，直到最后变成1。每次将“0”和“1”加到两个加法概率上，读出时，符号开始，一直到最后的“1”，路线上遇到的“0”和“1”按照从最低位到最高位的顺序排列，这就是符号的霍夫曼码。

比如a7从左到右，从U到U“”，它的码字是1000；

A6按照路由从最低位到最高位的顺序排列“0”和“1”，其码字为1001…

霍夫曼编码得到的平均比特率为σ码长×出现概率。

上面的例子是:0.2×2+0.19×2+0.18×3+0.1.15×3+0.1.01×4。

可以算出这个例子的源熵是2.61bit，非常接近。

百度百科-霍夫曼编码