数据压缩与信源编码第3讲霍夫曼编码.

1、Huffmari编码算法基本规则 出现概率越高的符号采用越短的编码。 出现概率最低的两个符号采用相同长度的编码. 具体步骤 将符号出现概率从高到低排序. 将概率最低的两个符号合并成一个符号，它们概率之 和为新符号的概率。 重复上面两个步骤，直到概率为仁 每次合并符号，用0和1区分两个符号。 从根节点开始搜索每个符号，记录其0, !序列即为该 符号的编码。Huffman编码算法符号al32a3a5槪率0.20.40.10.1a2(0.4)a2(0.4)aO.4)aO.4) a2 (1.0)01 taO.2)a.CO.2)aJO.2) a；(0.6)101f%(02)八 时° 2)a3

2、(0.4)101ta4(0.1) a4(0J)1 fa5(01)1符兮a1a2a3a4a5Huffman 编硏10011011101111Huffman编码算法符号ala2a3a4a5Huffma n 编码10011011101111编码示例:信源输出符号序列a1 ,a2,a3,a4,a5,a2,a1 ,a2Huffman 编码输出为 100110111011110100Huffman编码算法符号a1a2a3a4a5槪率0.20.40.20.10.1Huffman 编 码10011011101111定长码000001010011100Huffman编码平均码长 =0.2*2+0.4*1 +0.

3、2*3+0.1 *4+0.1 *4=2.2bits如果使用定长码，每个符号需要3bits, Huffman编码平均 每符号节约0.8bits,压缩比3:2.2=1.36倍符号a1a2a3a4a5槪率0.20.40.20.10.1编码1001101110111100oHuffman编码树Huffman编码算法Huffman编码平均码长=0.2*2+0.4*1 +0.2*3+0.1 *4+0.1 *4=2.2bits假定以每个内节点的所有孩子节点的概率 之和表示该节点的值，Huffman编码树的 内节点之和等于平均码长.34Huffman编码算法符号a1a2a3a4a5槪率0.20.40.20.1

4、0.1Huffman 编 码10011011101111Huffman编码平均码长 =0.2*2+0.4*1 +0.2*3+0.V 4+0.1 *4=2.2bits信源的爛 (A)二工 Aq 丫仏)=-工)log円q) = 2UntlsymholHuffman编码冗余度=Huffman编码平均码长信源的埼s0.078bits/symbolHuffman编码没有达到压缩能力的极限，仍存在继续压缩 的可能。Huffman编码算法符号a1a2a3a4a5槪率0.25040.20.10.05瞅04)aJO.2)%(02)衍(04)臥0.4)a2(0.4) a2 (1.0)10 taO.2)aJO.2)

5、 8；(0.6)11Of1a4(0.1) a4 (0.2) 2a5(0.1) I霍夫曼编码中0和1的分配是任意的琼02) * a3 (0.4)10J符号a1a2a3a4a5編码110011011101111編码201100100010000Huffman编码算法瞅04)a2(0.4)也4)时0.2)aJ0.2)a,(0.2)a3(0.2)33(0.2)1a3(0.4)34(01)-84(0.2)0_Ia5(0.1)-0t, 丨因此，霍夫§a2(0.4) a2 (1.0)10 T- a；(0.6)1?1符号ala2a3a4a5槪率0.250.40.20.05符号a1a2a3a4a5编码

6、110011011101111編码201100100010000Huffman编码算法霍夫曼编码不唯一，什么样的霍夫曼编码最好呢？答案是：最小方差霍夫曼编码最小方差霍夫曼编码在合并两个符号时，如果有3个或 以上的符号概率都最小，则将刚合并的符号放在概率相 同的符号的最上面.最小方Huffman编码算法符号a1a2a3a4a5槪率0.250.40.20.10.05比(0.4)a2(0.4) 时(0.4)ai(0.2)S(02)时0.2)a3(0.2) JW4)84 (0.2)a；(0.6)a；(1.0)a；(0.4) 1符号ala2a3a4a5編码31000110100110 0 a/O) a5

7、(0.1) I最小方差H uffman编码算法符号a1a2a3a4a5编码110011011101111编码201100100010000编码3100011010011Huffman编码1和2码字长度在之间，码长方差较大， 编码3的码字长度在23之间，码长方差较小为什么码长方差小的编码最佳？对于一定速率的信源，例如1000symbol/秒，Huffman编 码平均码长为2.2bits,则平均编码码流输出为2200bit/秒, 假定信道带宽为2200biV秒，能够满足传输要求。最小方差H uffman编码算法最小方Huffman编码算法最小方差H uffman编码算法对于一定速率的信源.例如10

8、00symbol/Jt, Huffman编 码平均码长为2.2bits,则平均编码码流输出为2200bit/秒， 假定信道带宽为2200biV秒，能够满足传输要求.如果信源连续输出a2,贝ij编码1码流输出为1000bit/秒，浪 费信道带宽。如果信源连续输出a5贝ij编码1码流输出为4000bi”秒，信 道带宽又不足。最小方差H uffman编码算法最小方差H uffman编码算法最小方Huffman编码算法符号a1a2编码1100编码2011编码31000a3a4a5110111011110010001000011010011最小方差H uffman编码算法如果信源连续输出a2,则编码1码

9、流输出为lOOObit/秒，浪 费信道带宽。如果信源连续输出a5,则编码1码流输出为4000bit/秒，信 道带宽又不足 为了充分利用信道带宽，必须对编码输出的码流进行缓冲. 在信道带宽不足时将码流存储起来，在信道带宽富裕时进 行传送。符号a1a2a3a4a5编码110011011101111编码201100100010000编码31000110100112200biVs1. 110OOsymbol/s a5 l1. 1a51. 100 1最小方差H uffman编码算法最小方差H uffman编码算法如果信源连续输出a2, 费信道带宽如果信源连续输岀a5, 道带宽又不足 编码的码长方差越大,

10、 编码的码长方差越小,最小方差H uffman编码算法符号a1a2a3a4a5编码110011011101111编码201100100010000编码3100011010011则编码1码流输出为lOOObit/秒，浪 则编码1码流输出为4000bit/秒，信 缓冲必须越大；缓冲可以越小；因此.最佳的Huffman编码为最小方差Huffman編码。Huffman编码特点符号ala2a3a4a5编码110011011101111编码201100100010000编码3100011010011哈夫曼编码方法构造出来的码不是惟一的OHuffman编码特点符号ala2a3a4a5编码1100110111

11、01111编码201100100010000编码3100011010011Huffman编码的码长虽然是可变的，但却不需要另外附加同 步代码。例如.10011011101111按照编码1可解释为a1a2a3a4a5o 又如.100011010011按照编码3可解释为a1a2a3a4a5o规范Huffman码字规范的霍夫曼码字是从Huffman码字从特意挑选出来的, 目的是便于在译码时检测码字的长度。F面两个编码中，编码2为规范的Huffman码字。符号1234567800000101001110000100011001010011编玛201110010111000100001010011000

12、111符号91011121314151610100101010101011101100101101101110101111110000編码201000000000000001000010000011000100000101000110规范H uffman码字符号1234567B编码201110010111000100001010011000111符号910111213141516冷码201000000000000001000010000011000100000101000110规范的Huffman码字这样产生 first =0;for x:=5 downto 1 do firstx=(firs

13、tx+1 +numlx+1 )/2 其中，【y表示取不小于y的最小整数。规范H uffman码字符号12345678编码100000101001110000100011001010011编硏201110010111000100001010011000111符号910111213141516编码110100101010101011101100101101101110101111110000编码201000000000000001000010000011000100000101000110码长 Length123456码字个数Numl004057起始编码 first243540规范H uffman

14、码字码长 Length123456硏字个数 Numl004057起始编码 first243540规池的Huffman码字可以这样解码 例如码流00110x:=1; in put v; while v<firstxappend next input bit to v; x ：s x * 1;end while;v=0,first1=2; v=o6, first =4; v=001,first3=d; v=0011,first4=5; v=00110,first5=：4; 码长为5, v-first=2,符 号为码长为5的第2个符号 （以0开始），即符号7Huffman编码编程头现方法Huf

15、fman编码编程编码开始 对原始数据出现次数进行统计.将次数存储在數组counter中建立码树/码衷传送码表I编码传送压编码流符号ala2a3a4a5权值100283528312概率0.2180.0610.0760.6180.026编码结束Huffman编码编程利用统计錯果counter和徒表'typedef structint weit; 权值 int Ichd; 左孩子 int rchd; 右孩子Int part； 父节由 Jhufmtree; hufmtree *htree; 建立Huffman码树和码表.Huffman编码编程编码结束Huffman编码编程Huffman编码编程

16、Huffman编码编程压缩对abc.txt进行压缩，压缩结果存储在abc_code.tx忡。 解压对abc_code.txt进行解压，恢复结果存储在abc decode.txt中。对比abc.txt和abc_decode.txt.如果完全一致，表明 压缩/解压过程正确，反之不正确.对比abc.txt和abc_ decode.txt文件大小,计算压缩比自适应Huffman编码Adaptive Huffman coding ( Dynamic Huffman coding )Huffman编码需要实现知道输入符号集的概率分布，为了 进行编码需要先对数据计算概率分布，然后再对数据进行 编码，需要对数

17、据扫描两遍。对信源进行哈夫曼编码后形成了一个哈夫曼编码表，若要 正确解码必须依照此表.于是在信源存储与传输过程中， 必须首先考応此表的存储与传输，故此表也占有一定的比 特数。一种解决方法是使用默认的哈夫曼编码表，而更 好的方法是自适应Huffman编码自适应Huffman编码不需要事先计算概率分布，能够在 编码/解码过程中自动建立Huffman编码树，只需要对数 据扫描一遍因而得到了广泛应用自适应Huffman编码Adaptive Huffman coding ( Dynamic Huffman coding )自适应Huffman编码的思想是从一)个空的Huffman编码树开始.空的NYTH

18、uffman编码树仅包含一个空节点 NYT(Not Yet Transmitted),表示还没有开始数据传送。自适应Huffman编码Adaptive Huffman coding ( Dynamic Huffman coding )自适应Huffman编码的思想是从一 个空的Huffman编码树开始.空的 Huffman编码树仅包含一个空节点 NYT(Not Yet Transmitted) 表示 还没有开始数据传送.读入的第1个符号，不做压缩直接 进入输出码流，同时将其添加进树 中赋予码字.自适应Huffman编码Adaptive Huffman coding ( Dynamic Huffman coding ) 每读入*!个新的符号，输出NYT,然 eAb. 后将新符号不做压缩直接进入输出 同时将其添加进树中赋予码00110001000皐流,Adaptive Huffman coding ( Dynamic Huffman coding )自适应Huffman编码自适应Huffman编码Adaptive Huffman coding ( Dynamic Huffman coding )自适应Huffman编码Adaptive Huffman codi