哈夫曼编码：基于频率的电文压缩

首先按照频率从小到大排序，得到以下序列：/n/n(3, 0.03) (7, 0.06) (1, 0.07) (2, 0.10) (5, 0.20) (0, 0.30) (6, 0.22) (4, 0.02)/n/n接下来，按照哈夫曼树的构造方法，每次选取权值最小的两个节点合并，得到新节点的权值为两个节点权值之和。不断重复此过程，直到只剩下一个节点，即根节点。/n/n构造哈夫曼树的过程如下（其中数字为节点编号，括号内为节点的权值）：/n/n/n(4, 0.02) (3, 0.03)/n // //n // //n // //n (7, 0.06) (1, 0.07)/n // //n // //n // //n (2, 0.10)/n / ///n / ///n / ///n (6, 0.22) (0, 0.30)/n | |/n | |/n | |/n (5, 0.20) (3, 0.10)/n // //n // //n // //n (1.10)/n |/n |/n |/n (0.40)/n/n/n根据哈夫曼树的构造方法，左子树的编码为 0，右子树的编码为 1。从根节点出发，左子树为 0，右子树为 1，得到以下编码：/n/n/n4: 0000/n7: 0001/n1: 001/n2: 01/n5: 10/n0: 110/n6: 1110/n3: 1111/n/n/n另一种编码方案为使用 0~7 的二进制表示形式，即：/n/n/n0: 000/n1: 001/n2: 010/n3: 011/n4: 100/n5: 101/n6: 110/n7: 111/n/n/n对照表如下：/n/n/n字符 频率 哈夫曼编码 二进制编码/n0 0.30 110 000/n1 0.07 001 001/n2 0.10 01 010/n3 0.03 1111 011/n4 0.20 100 100/n5 0.06 10 101/n6 0.22 1110 110/n7 0.02 0000 111/n/n/n带权路径长度 WPL 的计算公式为：/n/n$$/text{WPL} = /sum_{i=0}^7/text{freq}_i/times/text{depth}_i$$/n/n其中 freq 表示频率，depth 表示节点深度。计算得到：/n/n$$/text{WPL} = 0.30/times3 + 0.07/times3 + 0.10/times2 + 0.03/times4 + 0.20/times2 + 0.06/times2 + 0.22/times3 + 0.02/times4 = 2.69$$