Huffman编码,1,多媒体计算机 技术原理及应用,主讲：李 晓,辅导课程六,Huffman编码,2,第二章 学习内容,2.1 信息表示与编码 2.2 常用的数据压缩技术 2.3 静态图像压缩标准JPEG 2.4 运动图像压缩标准MPEG 2.5 视听通信编码解码标准H.261 2.6 声音压缩标准 本章小结,Huffman编码,3,2.2 常用的数据压缩技术,本节课内容： 2.2.4 信息熵编码Huffman编码,Huffman编码,4,Huffman编码是可变字长编码(VLC)的一种，最先由 Huffman 在1952年提出。,2.2.4 信息熵编码2. Huffman编码,Huffman编码,5,（1）理论基础 定理 在变长编码中，对出现概率大的信源符号赋予短码字，而对于出现概率小的信源符号赋予长码字。如果码字长度严格按照所对应符号出现概率大小的逆序排列，则编码结果平均码字长度一定小于任何其他排列方式。,2.2.4 信息熵编码2. Huffman编码,Huffman编码,6,（2）Huffman编码方法对一组信源符号进行编码的步骤如下： 第一步：构造根节点为1的二叉树 第二步：对每对合并的信源，根据概率的大小分别赋0、1 第三步：获得从该符号到根节点的路径逆向即为码字,2.2.4 信息熵编码2. Huffman编码,Huffman编码,7,第一步：构造根节点为1的二叉树(1)将信源符号按概率递减顺序排列； (2)把两个最小概率相加作为新符号的概率，并按(1)重排； (3)重复(1)、(2)，直到概率为1；,2.2.4 信息熵编码2. Huffman编码,Huffman编码,8,第二步：对每对合并的信源，根据概率的大小分别赋0、1 （如可概率大者赋“0“，概率小者赋“1“）；,2.2.4 信息熵编码2. Huffman编码,Huffman编码,9,第三步：获得从该符号到根节点的路径-逆向即为码字(1)寻找从每一信源符号到概率为1处的路径，记录路径上的0、1； (2)写出每一符号的1、0序列(从树根到信源符号节点),2.2.4 信息熵编码2. Huffman编码,Huffman编码,10,2.2.4 信息熵编码2. Huffman编码,Huffman编码,