哈夫曼樹怎樣構(gòu)造編碼？首先構(gòu)造了哈夫曼樹，給出了哈夫曼樹的構(gòu)造規(guī)則：假設有n個權值，構(gòu)造的哈夫曼樹有n個葉節(jié)點。N個權值設為W1，W2哈夫曼樹的構(gòu)造規(guī)則如下：（1）W1，W2（2）在林中選取根節(jié)點權值

哈夫曼樹怎樣構(gòu)造編碼？

首先構(gòu)造了哈夫曼樹，給出了哈夫曼樹的構(gòu)造規(guī)則：假設有n個權值，構(gòu)造的哈夫曼樹有n個葉節(jié)點。N個權值設為W1，W2哈夫曼樹的構(gòu)造規(guī)則如下：（1）W1，W2（2）在林中選取根節(jié)點權值最小的兩棵樹，合并為一棵新樹的左右子樹，新樹的根節(jié)點的權重是其左右子樹的根節(jié)點的權重之和；（3）從林中刪除所選的兩棵樹，并將新樹添加到林中；（4）重復步驟（2）和（3），直到林中只剩下一棵樹。構(gòu)造完成后，從樹的根節(jié)點開始，默認的左子樹為0，右子樹為1，直到葉節(jié)點。葉節(jié)點的代碼是必需的代碼。例如，ABCDEF的權重是812520411，哈夫曼樹是：60/2337//f（11）B（12）17D（20）/a（8）9/e（4）C（5）編碼是a:100，B:01，C:1011，D:11，e:1010，f:00

假設用于通信的消息2113由字符集{a，B，C，D，e，f，G，H}中的5261個字母組成，這八個字母出現(xiàn)在消息中的概率是4102，也就是{0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10}。哈夫曼碼1653可以從上面的編碼表中得到：A:1001 B:01 C:10111 D:1010 e:11 F:10110 G:00 h:1000，三位二進制等長編碼的平均長度為3，哈夫曼樹編碼的平均長度為4*0.07 2*0.19 5*0.02 4*0.06 2*0.32 5*0.03 2*0.21 4*0.10=2.61 2.61/3=0.87%，平均碼長為等長碼的87%，平均壓縮比為13%。由于定長碼已經(jīng)使用了相同的位數(shù)，這個條件保證了任何字符的碼都不會成為其他碼的前綴，所以這種情況只發(fā)生在變長碼中，我們必須用一個條件來制作常規(guī)長度碼。這個條件是，如果我們想成為壓縮碼，可變長度的代碼必須是前綴碼。所謂前綴碼，是指任何一個字符的編碼不能是另一個字符編碼的前綴。