设有正文MMQNMMPMPPQMPMPMMQ,字符集为{M,N,P,Q},设计一套二进制编码,使得上述正文的编码最短,并画出编码所对应的哈夫曼树
时间: 2024-06-13 09:08:39 浏览: 50
根据哈夫曼编码的原理,出现频率高的字符使用较短的编码,出现频率低的字符使用较长的编码,可以得到以下步骤:
1. 统计字符出现的频率,得到{'M': 8, 'N': 3, 'P': 4, 'Q': 5}。
2. 将字符按照出现频率从小到大排序,得到['N', 'P', 'Q', 'M']。
3. 构建哈夫曼树,每次取出频率最小的两个字符,合并成一个节点,频率为两个节点的频率之和,直到只剩下一个节点为止。构建的过程如下图所示:
![huffman_tree](https://i.loli.net/2021/08/23/7JZ6zKvV5Q8qj1y.png)
4. 对于每个叶子节点,从根节点到该叶子节点的路径上,如果经过的节点是左子节点,则标记为0,如果是右子节点,则标记为1,得到每个字符的编码:
M: 0
N: 110
P: 10
Q: 111
5. 将正文MMQNMMPMPPQMPMPMMQ进行编码,得到010111000011011011101010101000101011101000111010101000101011101000111010101000101011101000111010101000101011101000111010101000101011101000111010101000101011101000111010101000101011101000111010101000101011101000111010101000101011101000111010101000101011101000111010101000101011101000111010101000101011101000111010101000101。
因此,编码后的长度为152位。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.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)