2、假定用于通信的电文只有8个字母(a、b、C、d、e、f、g、h)组成,各字母在电文中出现的频率分别为5,20,3,6,10, 12, 4, 32。试为这些字母设计不等长的Huffman 编码,并给出该电文的总码数。(20分)。
时间: 2023-05-28 13:07:58 浏览: 69
首先根据频率从小到大排序,可以得到以下表格:
| 字母 | 频率 |
| :--: | :--: |
| c | 3 |
| g | 4 |
| a | 5 |
| d | 6 |
| e | 10 |
| f | 12 |
| b | 20 |
| h | 32 |
接着开始构建Huffman树,步骤如下:
1. 将所有节点按照频率从小到大排序,得到8个根节点。
2. 选取最小的两个节点(c和g),合并为一个新节点,频率为7,作为新的根节点。
3. 再次选取最小的两个节点(a和d),合并为一个新节点,频率为11,作为新的根节点。
4. 选取最小的两个节点(e和f),合并为一个新节点,频率为22,作为新的根节点。
5. 选取最小的两个节点(b和新的根节点),合并为一个新节点,频率为42,作为新的根节点。
6. 最后将剩下的节点(h和新的根节点)合并为一个新节点,频率为74,作为根节点。
构建完成后,可以得到以下Huffman编码:
| 字母 | 频率 | Huffman编码 |
| :--: | :--: | :---------: |
| c | 3 | 000 |
| g | 4 | 001 |
| a | 5 | 010 |
| d | 6 | 011 |
| e | 10 | 100 |
| f | 12 | 101 |
| b | 20 | 11 |
| h | 32 | 00 |
总码数为:3×3 + 4×3 + 5×3 + 6×3 + 10×3 + 12×3 + 20×2 + 32×2 = 214。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)