已知下列字符A、B、C、D、E、F、G的权值分别是3、12、7、4、2、8、11。绘制以该权值为叶子结点的Huffman树,并求出树的带权路径长度值WPL和压缩率,并写出以上每个字符的编码。
时间: 2023-11-08 17:36:33 浏览: 136
首先根据Huffman树构造的思想,我们需要将权值从小到大进行排序,得到以下序列:
E(2) A(3) D(4) C(7) F(8) G(11) B(12)
其中括号内为权值。接下来我们需要不断合并权值最小的两个节点,直到最后只剩下一个节点,这个节点就是Huffman树的根节点。具体步骤如下:
1. 将权值最小的两个节点E(2)和A(3)合并,得到一棵新树,其根节点权值为5,左子树为E,右子树为A。
5
/ \
E A
2. 继续合并权值最小的两个节点,即5和D(4),得到一棵新树,其根节点权值为9,左子树为之前合并的5和D,右子树为C。
9
/ \
5 C
/ \
E A
/
D
3. 继续合并权值最小的两个节点,即2和F(8),得到一棵新树,其根节点权值为10,左子树为E,右子树为之前合并的5和D和C和A和F。
10
/ \
E 9
/ \
5 C
/ \ /
A D F
4. 继续合并权值最小的两个节点,即11和B(12),得到一棵新树,其根节点权值为23,左子树为之前合并的10和E和9和5和C和A和D和F,右子树为G。
23
/ \
10 G
/ \
E 9
/ \
5 C
/ \ /
A D F
至此,我们得到了Huffman树。根据Huffman编码的原理,我们可以将左子树编码为0,右子树编码为1,从根节点开始递归进行编码,直到叶子节点。得到每个字符的编码如下:
E: 000
A: 001
D: 0100
C: 0101
F: 011
G: 1
B: 10
带权路径长度值WPL为每个叶子节点的权值乘以其到根节点的路径长度之和,即:
WPL = 2*3 + 3*3 + 4*3 + 7*2 + 8*2 + 11*1 + 12*2 = 119
压缩率为原文本编码后所占的比例,可以通过计算原文本和编码后文本的比值得到。这里我们假设原文本为“BADACEG”,共7个字符,每个字符占用一个字节(即8位),总共占用56位。将其编码后,得到的编码为0100001000100010010101010111011,共25位。压缩率为25/56 ≈ 0.4464,即压缩率约为44.64%。
阅读全文