7.6 Huffman树及其应用 Huffman树 、 Huffman编码 带权路径 长度最短 的树 Huffman树 最优二叉树 是通信 Huffman编码■不等长编码 中最经 典的压
1 7.6 Huffman树及其应用 一 、Huffman树 二、Huffman编码 Huffman树 最优二叉树 Huffman编码 带权路径 长度最短 的树 不等长编码 是通信 中最经 典的压 缩编码
、 Huffman树(最优二叉树) 若干术语: 路径:由一结点到另一结点间的分支所构成。 路径长度:路径上的分支数目。例如:a→e的路径长度=2 二叉树的路径长 度 从二叉树根到每一结点的路径长度树长度=0 之和。 叉树的带权路从二叉树根结点到所有叶子结点的路径长度与 径长度: 相应叶子结点权值的乘积(WPL) 即树中所有叶子结点的带权路径长度之和 Huffman树:带权路径长度最小的树 Huffman常译为赫夫曼、霍夫曼、哈夫曼等
2 一、 Huffman树（最优二叉树） 路 径： 路径长度： 二叉树的路径长 度： 二叉树的带权路 径长度： Huffman树： 由一结点到另一结点间的分支所构成。 路径上的分支数目。 从二叉树根到每一结点的路径长度 之和。 从二叉树根结点到所有叶子结点的路径长度与 相应叶子结点权值的乘积（WPL） 若干术语： d e b a c f g 即树中所有叶子结点的带权路径长度之和 带权路径长度最小的树。 例如：a→e的路径长度＝ 树长度＝ 2 10 Huffman常译为赫夫曼、霍夫曼、哈夫曼等
树的带权路径长度 树中所有叶子结 如何计算? WPL= ∑听 点的带权路径长 经典之例 度之和 ca(b (b) WPL=36 WPL=46 WPL= 35 Huffman树是mL最小的树
3 树的带权路径长度 如何计算？ WPL = wklk k=1 n a b c d 7 5 2 4 (a) c d a b 2 4 7 5 (b) b d a c 7 5 2 4 (c) 经典之例： WPL= WPL= WPL= Huffman树是WPL 最小的树 树中所有叶子结 点的带权路径长 度之和 36 46 35
1.构造 Huffman树的基本思想: WPL最小的树 权值大的结点用短路径,权值小的结点用长路径。 讨论: Huffman树有什么用?一最小冗余编码、信息高效传输」 例:设有4个字符d,i,a,n,出现的频度分别为7,5,2,4 怎样编码才能使它们组成的报文在网络中传得最快? 法1:等长编码(如二进制编码) 令d=00,i=01,a=10,n=11,则: 频度高的信息 WPL1=2bi×(7+5+2+4)=36 用短码,反之 用长码,传输 法2:不等长编码(如 Huffman编码) 效率肯定高! 令d=0;i=10,a=110,n=111,则: WPL2=1bit×7+2bit×5+3bit×(2+4)=35 明确:要实现 Huffman编码,就要先构造 Huffman树
4 1. 构造Huffman树的基本思想： 设有4个字符d,i,a,n，出现的频度分别为7,5,2,4， 怎样编码才能使它们组成的报文在网络中传得最快？ 法1：等长编码（如二进制编码） 令d=00，i=01，a=10，n=11，则： WPL1＝2bit×(7＋5＋2＋4）＝36 法2：不等长编码（如Huffman编码） 令d=0;i=10,a=110,n=111，则： 明确：要实现Huffman编码，就要先构造Huffman树 讨论：Huffman树有什么用？ 权值大的结点用短路径，权值小的结点用长路径。 WPL最小的树 频度高的信息 用短码，反之 用长码，传输 效率肯定高！ WPL2=1bit×7＋2bit×5+3bit×(2+4)=35 最小冗余编码、信息高效传输
2.构造 Huffman树的步骤(即 HUffman算法) (1)由给定的n个权值{w,w2…,wn}构成n棵二叉树的集合F T,T2y…Tn}(即森林),其中每棵二叉树T中只有一个 带权为n的根结点,其左右子树均空。 (2)在F中选取两棵根结点权值最小的树做为左右子树构造一棵 新的二叉树,且让新二叉树根结点的权值等于其左右子树的 根结点权值之和。 (3)在F中删去这两棵树,同时将新得到的二叉树加入F中 (4)重复(2)和(3),直到F只含一棵树为止。这棵树便是 Huffman 树 怎样证明它就是WPL最小的最优二叉树?参考《信源编码》 Huffman树的特点:没有度为1的结点
5 2. 构造Huffman树的步骤（即Huffman算法）： 怎样证明它就是WPL最小的最优二叉树？参考《信源编码》 Huffman树的特点：没有度为1的结点
具体操作步骤: step1:对权值进行合并、删除与替换 在权值集合{7,5,2,4中,总是合并当前值最小的两个权 a.初始 合并{5}{6 d合并{7}{1} F:{7}{5}{2}{4 F:{7}{11} F:{18} b合并{2}{4 F:{7}{5}{6} 圆框表示内结点 7][5K2][4 (合并后的权值) 方框表示外结点(叶子,字符)
6 step1： ——在权值集合{7,5,2,4}中，总是合并当前值最小的两个权 具体操作步骤： a. 初始 方框表示外结点（叶子，字符） 圆框表示内结点 （合并后的权值） b. 合并{2} {4} c. 合并{5} {6} d. 合并{7} {11}
step2:按左“0”若 对 Huffman树的所有分支 编号 将 Huffman树与 Huffman编码挂钩 0(1 d 0/1 0/ 2[4 Huffman编码结果:d=0,i=10,a=110,n=111 WPL=1bit×7+2bit×5+3bit(2+4)=35(小于等长码的WL=36) 特征:每一码不会是另一码的前缀,译码时可惟一复原 Huffman编码也称为前缀码
7 step2： d a i n 1 1 0 1 0 0 Huffman编码结果：d=0, i=10, a=110, n=111 WPL=1bit×7＋2bit×5+3bit(2+4)=35（小于等长码的WPL=36） Huffman编码也称为 Huffman树 与 Huffman编码 挂钩
二、 Huffman编码 霍夫曼编码的基本思想是 出现概率大的信息用短码,概率小的用长码,最小冗余 分析 Huffman树和编码的特点: (1)由于 Huffman树的WL最小,说明编码所 需要的比特数最少。 这种编码已广泛应 用于网络通信中。 (2) Huffman树肯定没有度为1的结点; (3)一棵有n0个叶子结点的 Huffman树,共有2n0-1个结点; (因为n=no+n1+n2=2n-1) (4) Huffman编码时是从叶子走到根;而译码时又要从根走 到叶子,因此每个结点需要增开双亲指针分量(连同结点权值 共要开5个分量) (5)用计算机实现时,顺序和链式两种存储结构都要用到
8 二、Huffman编码 （1）由于Huffman树的WPL最小，说明编码所 需要的比特数最少。 （4） Huffman编码时是从叶子走到根；而译码时又要从根走 到叶子，因此每个结点需要增开双亲指针分量（连同结点权值 共要开5个分量） （5）用计算机实现时，顺序和链式两种存储结构都要用到。 分析Huffman树和编码的特点： 霍夫曼编码的基本思想是—— 出现概率大的信息用短码，概率小的用长码,最小冗余 这种编码已广泛应 用于网络通信中。 （2） Huffman树肯定没有度为1的结点； （3）一棵有n 0个叶子结点的Huffman树，共有2n0-1个结点； （因为n=n0+n1+n2=2n0-1)
如何编程实现 Huffman编码? 建议1: Huffman树中结点的结构可设计成5分量形式: char weight parent Child rchild 建议2: Huffman树的存储结构可采用顺序存储结构 将整个 Huffman树的结点存储在一个数组H[1..n.m中 各叶子结点的编码存储在另一“复合”数组H[1..n中
9 如何编程实现Huffman编码？ 建议1：Huffman树中结点的结构可设计成5分量形式： char weight parent lchild rchild 将整个Huffman树的结点存储在一个数组HT[1..n..m]中; 各叶子结点的编码存储在另一“复合”数组HC[1..n]中。 建议2： Huffman树的存储结构可采用顺序存储结构：
Huffman树和 Huffman树编码的存储表示: typedef struct unsigned int weight;∥权值分量(可放大取整) unsigned int parent, Child, rchild;/双亲和孩子分量 HTNode, Huffmantree;用动态数组存储 Huffman树 typedef char* *Huffman code;/动态数组存储 Huffman编码表 米 Huffmantree或HT向量 指针型指针 双亲 7 2|19 p—0—09 0-0 r00=0 HT[3]. parent=9 32
10 typedef struct{ unsigned int weight；//权值分量（可放大取整） unsigned int parent，lchild，rchild； //双亲和孩子分量 }HTNode， *HuffmanTree；//用动态数组存储Huffman树 typedef char**HuffmanCode； //动态数组存储Huffman编码表 Huffman树和Huffman树编码的存储表示： 0 0 0 r 2 9 0 19 0 0 7 0 0 w p l 3 2 1 双亲 *HuffmanTree或 HT向量 HT[3].parent=9 指针型指针