设用于通讯的电文仅由 8 个字母组成,它们在电文中出现的频率分别为 0.30、0.07、0.10、0.03、0.20、0.06、0.22、0.02,试设计哈夫曼树(每次选取与合并时按权值小的在左,权值大的在右的方式构造)及其编码。使用 0~7 的二进制表示形式是另一种编码方案。给出两种编码的对照表、带权路径长度 WPL 值。
时间: 2023-07-10 15:18:19 浏览: 36
好的,我知道了,下面是我的回答:
根据哈夫曼树的构造方法,我们可以先将权值从小到大排序,然后选取权值最小的两个节点合并,形成一个新的节点,其权值为两个节点的权值之和。依次类推,直到所有的节点都被合并为一个根节点。
根据这个方法,我们可以得到如下的哈夫曼树:
```
1.00
/ \
/ \
0.70 0.30
/ \ / \
/ \ / \
0.37 0.33 0.14 0.16
/\ /\
a b c d
```
根据上面的哈夫曼树,我们可以得到以下的编码:
```
a: 00
b: 01
c: 100
d: 101
e: 110
f: 1110
g: 1111
h: 1100
```
这个编码方案的带权路径长度 WPL 值为:
```
WPL = 0.30*1 + 0.07*2 + 0.10*3 + 0.03*3 + 0.20*2 + 0.06*4 + 0.22*4 + 0.02*4 = 2.74
```
另外一种编码方案,我们可以使用 0~7 的二进制表示形式,也就是说,每个字母都可以用 3 位二进制数来表示。按照出现频率从高到低依次为 000、001、010、011、100、101、110、111。这个编码方案的对照表如下:
```
a: 000
b: 001
c: 010
d: 011
e: 100
f: 101
g: 110
h: 111
```
这个编码方案的带权路径长度 WPL 值为:
```
WPL = 0.30*3 + 0.07*3 + 0.10*3 + 0.03*3 + 0.20*3 + 0.06*3 + 0.22*3 + 0.02*3 = 2.79
```
至此,我已经回答了你的问题。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)