4.1 静态哈夫曼编码 _编码

一、发展历史
哈夫曼使用自底向上的方法构建二叉树。
哈夫曼编码的基本方法是先对图像数据扫描一遍，计算出各种像素出现的概率，按概率的大小指定不同长度的唯一码字（这种长度不同的编码方式称为变长编码，对应的长度相同的编码方式叫定长编码），由此得到一张该图像的哈夫曼码表。编码后的图像数据记录的是每个像素的码字，而码字与实际像素值的对应关系记录在码表中。
（同理也可对字符数据，扫描字符数据，计算各字符出现概率，按概率的大小指定不同长度的唯一码字，得到一段该字符数据的哈夫曼码表，编码后的字符数据记录是每个字符的码字，而码字与实际字符的对应关系记录在码表中）
该方法完全依据字符出现概率来构造异字头（即任一字符的编码不会是另一字符编码的前缀）的平均长度最短的码字，有时称之为最佳编码，一般就称编码。
二、原理
a图表示将新合并的支路排到等概率的最上支路，b图则是排到等概率的最下支路
设某信源产生有五种符号 u 1，u 2，u 3，u 4 和 u 5 u_1，u_2，u_3，u_4和u_5 u1?，u2?，u3?，u4?和u5?，对应概率 p 1 = 0.4，p 2 = 0.1，p 3 = p 4 = 0.2，p 5 = 0.1 p_1=0.4，p_2=0.1，p_3=p_4=0.2，p_5=0.1 p1?=0.4，p2?=0.1，p3?=p4?=0.2，p5?=0.1 。首先，将符号按照概率由大到小排队，如图1所示。编码时，从最小概率的两个符号开始，可选其中一个支路为0，另一支路为1 。这里，我们选上支路为0，下支路为1 。再将已编码的两支路的概率合并，并重新排队。多次重复使用上述方法直到合并概率归一时为止。
从上图中(a)和(b)可以看出，两者虽平均码长相等，但同一符号可以有不同的码长，及编码方法并不唯一，其原因是两支路概率合并后重新排队时，可能出现几个支路概率相等，造成排队方法不唯一。一般，若将新合并后的支路排到等概率的最上支路，将有利于缩短码长方差，且编出的码更接近于等长码。这里上图(a)的编码比(b)好。
哈夫曼码的码字（各符号的代码）是异前置码字，即任一码字不会是另一码字的前面部分，这使各码字可以连在一起传送，中间不需另加隔离符号，只要传送时不出错，收端仍可分离各个码字，不致混淆。
三、定理
哈夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1 。每次相加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”，将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的赫夫曼编码。
3.1 举例
U ：（ a 1 , a 2 , a 3 , a 4 , a 5 , a 6 , a 7 ） U：（a_1,a_2,a_3,a_4,a_5,a_6,a_7） U：（a1?,a2?,a3?,a4?,a5?,a6?,a7?）
值分别为：
（ 0.20 0.20 0.200.19 0.19 0.190.18 0.18 0.180.17 0.17 0.170.15 0.15 0.150.10 0.10 0.100.01 0.01 0.01）
生成的哈哈夫曼树如下：
哈夫曼编码为：
a 1 a_1 a1?：01
a 2 a_2 a2?：00
a 3 a_3 a3?：111
a 4 a_4 a4?：110
a 5 a_5 a5?：101
a 6 a_6 a6?：1000
a 7 a_7 a7?：1001
用赫夫曼编码所得的平均比特率： ∑ 码长 ? 出现概率 \sum码长 *出现概率 ∑码长?出现概率
上例为：0.2 * 2+0.19 * 2+0.18 * 3+0.17 * 3+0.15 * 3+0.1 * 4+0.01 *4=2.72bit
四、类型 4.1 静态哈夫曼编码
1.哈夫曼编码时如何实现数据的压缩和解压缩的呢？
在计算机当中，数据的存储和加工都是以字节为基本单位的，一个西文字符要通过一个字节来表示，而一个汉字就要用两个字节，我们把这种每一个字符都通过相同的字节数来表达的编码形式称为定长编码。