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 最小冗余编码、信息高效传输