哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫做Huffman编码(有时也称为霍夫曼编码)。

1.哈夫曼编码解码原理

设某信源产生有五种符号u1、u2、u3、u4和u5,对应概率P1=0.4,P2=0.1,P3=P4=0.2,P5=0.1。首先,将符号按照概率由大到小排队。编码时,从最小概率的两个符号开始,可选其中一个支路为0,另一支路为1。再将已编码的两支路的概率合并,并重新排队。多次重复使用上述方法直至合并概率归一时为止。如图所示,从图(a)和(b)可以看出,两者虽平均码长相等,但同一符号可以有不同的码长,即编码方法并不唯一,其原因是两支路概率合并后重新排队时,可能出现几个支路概率相等,造成排队方法不唯一。一般,若将新合并后的支路排到等概率的最上支路,将有利于缩短码长方差,且编出的码更接近于等长码。这里图(a)的编码比(b)好。

 

哈夫曼编码解码原理

(图片来源于互联网)

 

哈夫曼码的码字(各符号的代码)是异前置码字,即任一码字不会是另一码字的前面部分,这使各码字可以连在一起传送,中间不需另加隔离符号,只要传送时不出错,收端仍可分离各个码字,不致混淆。

 

实际应用中,除采用定时清洗以消除误差扩散和采用缓冲存储以解决速率匹配以外,主要问题是解决小符号集合的统计匹配,例如黑(1)、白(0)传真信源的统计匹配,采用0和1不同长度游程组成扩大的符号集合信源。游程,指相同码元的长度(如二进码中连续的一串0或一串1的长度或个数)。按照CCITT标准,需要统计2×1728种游程(长度),这样,实现时的存储量太大。事实上长游程的概率很小,故CCITT还规定:若l表示游程长度,则l=64q+r。其中q称主码,r为基码。编码时,不小于64的游程长度由主码和基码组成。而当l为64的整数倍时,只用主码的代码,已不存在基码的代码。

 

长游程的主码和基码均用赫夫曼规则进行编码,这称为修正赫夫曼码,其结果有表可查。该方法已广泛应用于文件传真机中。

 

2.哈夫曼编码数据结构

在变字长编码中,如果码字长度严格按照对应符号出现的概率大小逆序排列,则其平均码字长度为最小。现在通过一个实例来说明上述定理的实现过程。设将信源符号按出现的概率大小顺序排列为 :U:( a1 a2 a3 a4 a5 a6 a7 )   0.20 0.19 0.18 0.17 0.15 0.10 0.01。给概率最小的两个符号a6与a7分别指定为“1”与“0”,然后将它们的概率相加再与原来的 a1~a5组合并重新排序成新的原为:U′: ( a1 a2 a3 a4 a5 a6′ )  0.20 0.19 0.18 0.17 0.15 0.11,对a5与a′6分别指定“1”与“0”后,再作概率相加并重新按概率排序得U″:(0.26 0.20 0.19 0.18 0.17)等等,直到最后得 U″″:(0.61 0.39)。

 

赫夫曼编码的具体方法:先按出现的概率大小排队,把两个最小的概率相加,作为新的概率 和剩余的概率重新排队,再把最小的两个概率相加,再重新排队,直到最后变成1。每次相 加时都将“0”和“1”赋与相加的两个概率,读出时由该符号开始一直走到最后的“1”, 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好,就是该符号的赫夫曼编码。

 

例如a7从左至右,由U至U″″,其码字为1000;a6按路线将所遇到的“0”和“1”按最低位到最高位的顺序排好,其码字为1001…用赫夫曼编码所得的平均比特率为:Σ码长×出现概率

 

上例为:0.2×2+0.19×2+0.18×3+0.17×3+0.15×3+0.1×4+0.01×4=2.72 bit可以算出本例的信源熵为2.61bit,二者已经是很接近了。

哈夫曼编码数据结构

(图片来源于互联网)

 

3.哈夫曼编码的作用

哈夫曼树─即最优二叉树,带权路径长度最小的二叉树,经常应用于数据压缩。 在计算机信息处理中,“哈夫曼编码”是一种一致性编码法(又称“熵编码法”),用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符(例如某文件中的一个符号)进行编码。这张编码表的特殊之处在于,它是根据每一个源字符出现的估算概率而建立起来的(出现概率高的字符使用较短的编码,反之出现概率低的则使用较长的编码,这便使编码之后的字符串的平均期望长度降低,从而达到无损压缩数据的目的)。这种方法是由David.A.Huffman发展起来的。 例如,在英文中,e的出现概率很高,而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时,e极有可能用一个位(bit)来表示,而z则可能花去25个位(不是26)。用普通的表示方法时,每个英文字母均占用一个字节(byte),即8个位。二者相比,e使用了一般编码的1/8的长度,z则使用了3倍多。若能实现对于英文中各个字母出现概率的较准确的估算,就可以大幅度提高无损压缩的比例。

 

哈夫曼编码的作用

(图片来源于互联网)