假设用于通讯的电文仅有八个字母ABCDEFGH组成字母在电文中出现的频率分别为007 019 002 006 032 003 021 010。试为这八个字母设计哈夫曼编码。
首先,按照出现频率从小到大排序,得到:C,E,F,H,A,D,G,B。
然后,构建哈夫曼树:
- 将最小的两个频率C和E合并,得到频率为0.09的节点CE。
- 将下一个最小频率F和CE合并,得到频率为0.12的节点FCE。
- 将下一个最小频率H和A合并,得到频率为0.17的节点HA。
- 将下一个最小频率D和G合并,得到频率为0.24的节点DG。
- 将下一个最小频率FCE和HA合并,得到频率为0.29的节点FCEHA。
- 将下一个最小频率B和FCEHA合并,得到频率为1的节点BFCEHA。
最后,根据哈夫曼树得到每个字母的编码:
A:100 B:0 C:1100 D:101 E:111 F:1101 G:1000 H:1110
注意,每个字母的编码都不是其他字母编码的前缀,因此这是一种前缀编码,可以唯一地解码出原始电文。
原文地址: https://www.cveoy.top/t/topic/fprI 著作权归作者所有。请勿转载和采集!