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的结点