3.2.2哈夫曼编码（课件）-《多媒体技术应用》同步教学（高教版）

如果没有数据压缩技术，我们就没法用 WinRAR 为 Email 中的附件瘦身；如果没有数据压缩技术，市场上的数码录音笔就只能记录不到 20 分钟的语音；如果没有数据压缩技术，从 Internet 上下载一部电影也许要花半年的时间…… This chapter 多媒体数据压缩技术 1 哈夫曼编码 contents 数据压缩方法 本节内容 哈弗曼编码简介 香农的信息保持编码只是指出存在一种无失真的编码，使得编码平均码长逼近熵值这个下限，但它并没有给出具体的编码方法。信息论中介绍了几种典型的熵编码方法，如Shannon(香农)编码法、Fano（法诺）编码法和Huffman编码法，其中尤其以哈夫曼编码法为最佳，在多媒体编码系统中常用这种方法作熵保持编码。 哈夫曼编码方法于1952年问世。迄今为止，仍经久不衰，广泛应用于各种数据压缩技术中，且仍不失为熵编码中的最佳编码方法。 Huffman编码法利用了最佳编码定理：在变字长码中，对于出现概率大的信息符号以短字长编码，对于出现概率小的信息符号以长字长编码。如果码字长度严格按照符号概率的大小的相反顺序排列，则平均码字长度一定小于按任何其他符号顺序排列方式得到的码字长度。 5 哈夫曼编码方法的具体步骤归纳如下： (1)概率统计（如对一幅图像，或m幅同种类型图像作灰度信号统计），得到n个不同概率的信源信息符号。 (2)将信源信息符号的n个概率，按概率大小排序。 (3)将n个概率中的最后两个小概率相加，这时概率个数减为n-1个。 (4)将n-1个概率按大小重新排序。 (5)重复步骤(3)，将新排序后的最后两个小概率再相加，相加所得到的和与其余概率再排序。 (6)如此反复重复n-2次，最后只剩下两个概率序列。 (7)以二进制码元（0，1）赋值（如大概率用“0”表示，小概率用“1”表示），构成哈夫曼字，至此编码结束。 例：设有7个符号的信源X={x1,x2,x3,…,x7} 概率分布为P=P(xi){0.35,0.20,0.15,0.10,0.10,0.06,0.04} 做出哈夫曼编码。 码字的平均码长 用下面公式计算 = = =(0.35+0.20)×2+(0.15+0.10+0.10)×3+(0.06+0.04)×4 =2.55bits/pel 哈夫曼码字长度和信息符号出现概率大小次序正好相反，即大概率信息符号分配码字长度短，小概率信息符号分配码字长度长。 $$