怎樣求哈夫曼樹(shù)的平均編碼長(zhǎng)？怎樣求哈夫曼樹(shù)？假設(shè)用于通信2113的消息由字符集{a、B、C、D、e、F、G、H}中的5261個(gè)字母組成，消息中出現(xiàn)這八個(gè)字母的概率為4102，即{0.07、0.19、0

怎樣求哈夫曼樹(shù)的平均編碼長(zhǎng)？怎樣求哈夫曼樹(shù)？

假設(shè)用于通信2113的消息由字符集{a、B、C、D、e、F、G、H}中的5261個(gè)字母組成，消息中出現(xiàn)這八個(gè)字母的概率為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，三位二進(jìn)制等長(zhǎng)編碼的平均長(zhǎng)度為3，哈夫曼樹(shù)編碼的平均長(zhǎng)度為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%，平均碼長(zhǎng)為等長(zhǎng)碼的87%，平均壓縮比為13%。由于定長(zhǎng)碼已經(jīng)使用了相同的位數(shù)，這個(gè)條件保證了任何字符的碼都不會(huì)成為其他碼的前綴，所以這種情況只發(fā)生在變長(zhǎng)碼中，我們必須用一個(gè)條件來(lái)制作常規(guī)長(zhǎng)度碼。這個(gè)條件是，如果我們想成為壓縮碼，可變長(zhǎng)度的代碼必須是前綴碼。所謂前綴碼，是指任何一個(gè)字符的編碼不能是另一個(gè)字符編碼的前綴。

哈夫曼編碼和二進(jìn)制編碼優(yōu)缺點(diǎn)比較？

（1）哈夫曼編碼形成的碼字不是唯一的，但編碼效率是唯一的。當(dāng)給兩個(gè)最小概率符號(hào)賦值時(shí)，可以指定大符號(hào)為“1”，小符號(hào)為“0”，反之亦然。如果兩個(gè)符號(hào)的出現(xiàn)概率相等，那么不管哪個(gè)符號(hào)在前面，它都是可以排列的，因此哈夫曼構(gòu)造的碼字是不唯一的。對(duì)于同一信源，無(wú)論序列如何排列，其平均碼長(zhǎng)都不會(huì)改變，因此編碼效率是唯一的。（2） 只有當(dāng)信源中每個(gè)符號(hào)的概率非常不均勻時(shí)，哈夫曼編碼的效果才明顯。（3） 哈夫曼編碼必須精確計(jì)算原始文件中每個(gè)符號(hào)的頻率。沒(méi)有這些精確的統(tǒng)計(jì)數(shù)據(jù)，就無(wú)法達(dá)到預(yù)期的壓縮效果。霍夫曼編碼通常要經(jīng)過(guò)兩次運(yùn)算，第一次用于統(tǒng)計(jì)，第二次用于編碼，因此編碼速度相對(duì)較慢。另外，電路的實(shí)現(xiàn)比較復(fù)雜，各種長(zhǎng)度編碼的解碼過(guò)程也比較復(fù)雜，所以解壓過(guò)程比較慢。（4） 哈夫曼編碼只能用整數(shù)來(lái)表示單個(gè)符號(hào)，不能用小數(shù)來(lái)表示，這大大限制了壓縮效果。（5） 哈夫曼的所有片段都放在一起了。如果其中一個(gè)被更改，它的數(shù)據(jù)將被更改得無(wú)法識(shí)別