數(shù)據(jù)壓縮與信源編碼第3講霍夫曼編碼.

1、Huffmari編碼算法基本規(guī)則 出現(xiàn)概率越高的符號(hào)采用越短的編碼。 出現(xiàn)概率最低的兩個(gè)符號(hào)采用相同長(zhǎng)度的編碼. 具體步驟 將符號(hào)出現(xiàn)概率從高到低排序. 將概率最低的兩個(gè)符號(hào)合并成一個(gè)符號(hào)，它們概率之 和為新符號(hào)的概率。 重復(fù)上面兩個(gè)步驟，直到概率為仁 每次合并符號(hào)，用0和1區(qū)分兩個(gè)符號(hào)。 從根節(jié)點(diǎn)開始搜索每個(gè)符號(hào)，記錄其0, !序列即為該 符號(hào)的編碼。Huffman編碼算法符號(hào)al32a3a5槪率0.20.40.10.1a2(0.4)a2(0.4)aO.4)aO.4) a2 (1.0)01 taO.2)a.CO.2)aJO.2) a；(0.6)101f%(02)八 時(shí)° 2)a3

2、(0.4)101ta4(0.1) a4(0J)1 fa5(01)1符兮a1a2a3a4a5Huffman 編硏10011011101111Huffman編碼算法符號(hào)ala2a3a4a5Huffma n 編碼10011011101111編碼示例:信源輸出符號(hào)序列a1 ,a2,a3,a4,a5,a2,a1 ,a2Huffman 編碼輸出為 100110111011110100Huffman編碼算法符號(hào)a1a2a3a4a5槪率0.20.40.20.10.1Huffman 編 碼10011011101111定長(zhǎng)碼000001010011100Huffman編碼平均碼長(zhǎng) =0.2*2+0.4*1 +0.

3、2*3+0.1 *4+0.1 *4=2.2bits如果使用定長(zhǎng)碼，每個(gè)符號(hào)需要3bits, Huffman編碼平均 每符號(hào)節(jié)約0.8bits,壓縮比3:2.2=1.36倍符號(hào)a1a2a3a4a5槪率0.20.40.20.10.1編碼1001101110111100oHuffman編碼樹Huffman編碼算法Huffman編碼平均碼長(zhǎng)=0.2*2+0.4*1 +0.2*3+0.1 *4+0.1 *4=2.2bits假定以每個(gè)內(nèi)節(jié)點(diǎn)的所有孩子節(jié)點(diǎn)的概率 之和表示該節(jié)點(diǎn)的值，Huffman編碼樹的 內(nèi)節(jié)點(diǎn)之和等于平均碼長(zhǎng).34Huffman編碼算法符號(hào)a1a2a3a4a5槪率0.20.40.20.1

4、0.1Huffman 編 碼10011011101111Huffman編碼平均碼長(zhǎng) =0.2*2+0.4*1 +0.2*3+0.V 4+0.1 *4=2.2bits信源的爛 (A)二工 Aq 丫仏)=-工)log円q) = 2UntlsymholHuffman編碼冗余度=Huffman編碼平均碼長(zhǎng)信源的埼s0.078bits/symbolHuffman編碼沒有達(dá)到壓縮能力的極限，仍存在繼續(xù)壓縮 的可能。Huffman編碼算法符號(hào)a1a2a3a4a5槪率0.25040.20.10.05瞅04)aJO.2)%(02)衍(04)臥0.4)a2(0.4) a2 (1.0)10 taO.2)aJO.2)

5、 8；(0.6)11Of1a4(0.1) a4 (0.2) 2a5(0.1) I霍夫曼編碼中0和1的分配是任意的瓊02) * a3 (0.4)10J符號(hào)a1a2a3a4a5編碼110011011101111編碼201100100010000Huffman編碼算法瞅04)a2(0.4)也4)時(shí)0.2)aJ0.2)a,(0.2)a3(0.2)33(0.2)1a3(0.4)34(01)-84(0.2)0_Ia5(0.1)-0t, 丨因此，霍夫§a2(0.4) a2 (1.0)10 T- a；(0.6)1?1符號(hào)ala2a3a4a5槪率0.250.40.20.05符號(hào)a1a2a3a4a5編碼

6、110011011101111編碼201100100010000Huffman編碼算法霍夫曼編碼不唯一，什么樣的霍夫曼編碼最好呢？答案是：最小方差霍夫曼編碼最小方差霍夫曼編碼在合并兩個(gè)符號(hào)時(shí)，如果有3個(gè)或 以上的符號(hào)概率都最小，則將剛合并的符號(hào)放在概率相 同的符號(hào)的最上面.最小方Huffman編碼算法符號(hào)a1a2a3a4a5槪率0.250.40.20.10.05比(0.4)a2(0.4) 時(shí)(0.4)ai(0.2)S(02)時(shí)0.2)a3(0.2) JW4)84 (0.2)a；(0.6)a；(1.0)a；(0.4) 1符號(hào)ala2a3a4a5編碼31000110100110 0 a/O) a5

7、(0.1) I最小方差H uffman編碼算法符號(hào)a1a2a3a4a5編碼110011011101111編碼201100100010000編碼3100011010011Huffman編碼1和2碼字長(zhǎng)度在之間，碼長(zhǎng)方差較大， 編碼3的碼字長(zhǎng)度在23之間，碼長(zhǎng)方差較小為什么碼長(zhǎng)方差小的編碼最佳？對(duì)于一定速率的信源，例如1000symbol/秒，Huffman編 碼平均碼長(zhǎng)為2.2bits,則平均編碼碼流輸出為2200bit/秒, 假定信道帶寬為2200biV秒，能夠滿足傳輸要求。最小方差H uffman編碼算法最小方Huffman編碼算法最小方差H uffman編碼算法對(duì)于一定速率的信源.例如10

8、00symbol/Jt, Huffman編 碼平均碼長(zhǎng)為2.2bits,則平均編碼碼流輸出為2200bit/秒， 假定信道帶寬為2200biV秒，能夠滿足傳輸要求.如果信源連續(xù)輸出a2,貝ij編碼1碼流輸出為1000bit/秒，浪 費(fèi)信道帶寬。如果信源連續(xù)輸出a5貝ij編碼1碼流輸出為4000bi”秒，信 道帶寬又不足。最小方差H uffman編碼算法最小方差H uffman編碼算法最小方Huffman編碼算法符號(hào)a1a2編碼1100編碼2011編碼31000a3a4a5110111011110010001000011010011最小方差H uffman編碼算法如果信源連續(xù)輸出a2,則編碼1碼

9、流輸出為lOOObit/秒，浪 費(fèi)信道帶寬。如果信源連續(xù)輸出a5,則編碼1碼流輸出為4000bit/秒，信 道帶寬又不足 為了充分利用信道帶寬，必須對(duì)編碼輸出的碼流進(jìn)行緩沖. 在信道帶寬不足時(shí)將碼流存儲(chǔ)起來，在信道帶寬富裕時(shí)進(jìn) 行傳送。符號(hào)a1a2a3a4a5編碼110011011101111編碼201100100010000編碼31000110100112200biVs1. 110OOsymbol/s a5 l1. 1a51. 100 1最小方差H uffman編碼算法最小方差H uffman編碼算法如果信源連續(xù)輸出a2, 費(fèi)信道帶寬如果信源連續(xù)輸岀a5, 道帶寬又不足 編碼的碼長(zhǎng)方差越大,

10、 編碼的碼長(zhǎng)方差越小,最小方差H uffman編碼算法符號(hào)a1a2a3a4a5編碼110011011101111編碼201100100010000編碼3100011010011則編碼1碼流輸出為lOOObit/秒，浪 則編碼1碼流輸出為4000bit/秒，信 緩沖必須越大；緩沖可以越??；因此.最佳的Huffman編碼為最小方差Huffman編碼。Huffman編碼特點(diǎn)符號(hào)ala2a3a4a5編碼110011011101111編碼201100100010000編碼3100011010011哈夫曼編碼方法構(gòu)造出來的碼不是惟一的OHuffman編碼特點(diǎn)符號(hào)ala2a3a4a5編碼1100110111

11、01111編碼201100100010000編碼3100011010011Huffman編碼的碼長(zhǎng)雖然是可變的，但卻不需要另外附加同 步代碼。例如.10011011101111按照編碼1可解釋為a1a2a3a4a5o 又如.100011010011按照編碼3可解釋為a1a2a3a4a5o規(guī)范Huffman碼字規(guī)范的霍夫曼碼字是從Huffman碼字從特意挑選出來的, 目的是便于在譯碼時(shí)檢測(cè)碼字的長(zhǎng)度。F面兩個(gè)編碼中，編碼2為規(guī)范的Huffman碼字。符號(hào)1234567800000101001110000100011001010011編瑪201110010111000100001010011000

12、111符號(hào)91011121314151610100101010101011101100101101101110101111110000編碼201000000000000001000010000011000100000101000110規(guī)范H uffman碼字符號(hào)1234567B編碼201110010111000100001010011000111符號(hào)910111213141516冷碼201000000000000001000010000011000100000101000110規(guī)范的Huffman碼字這樣產(chǎn)生 first =0;for x:=5 downto 1 do firstx=(firs

13、tx+1 +numlx+1 )/2 其中，【y表示取不小于y的最小整數(shù)。規(guī)范H uffman碼字符號(hào)12345678編碼100000101001110000100011001010011編硏201110010111000100001010011000111符號(hào)910111213141516編碼110100101010101011101100101101101110101111110000編碼201000000000000001000010000011000100000101000110碼長(zhǎng) Length123456碼字個(gè)數(shù)Numl004057起始編碼 first243540規(guī)范H uffman

14、碼字碼長(zhǎng) Length123456硏字個(gè)數(shù) Numl004057起始編碼 first243540規(guī)池的Huffman碼字可以這樣解碼 例如碼流00110x:=1; in put v; while v<firstxappend next input bit to v; x ：s x * 1;end while;v=0,first1=2; v=o6, first =4; v=001,first3=d; v=0011,first4=5; v=00110,first5=：4; 碼長(zhǎng)為5, v-first=2,符 號(hào)為碼長(zhǎng)為5的第2個(gè)符號(hào) （以0開始），即符號(hào)7Huffman編碼編程頭現(xiàn)方法Huf

15、fman編碼編程編碼開始 對(duì)原始數(shù)據(jù)出現(xiàn)次數(shù)進(jìn)行統(tǒng)計(jì).將次數(shù)存儲(chǔ)在數(shù)組counter中建立碼樹/碼衷傳送碼表I編碼傳送壓編碼流符號(hào)ala2a3a4a5權(quán)值100283528312概率0.2180.0610.0760.6180.026編碼結(jié)束Huffman編碼編程利用統(tǒng)計(jì)錯(cuò)果counter和徒表'typedef structint weit; 權(quán)值 int Ichd; 左孩子 int rchd; 右孩子Int part； 父節(jié)由 Jhufmtree; hufmtree *htree; 建立Huffman碼樹和碼表.Huffman編碼編程編碼結(jié)束Huffman編碼編程Huffman編碼編程

16、Huffman編碼編程壓縮對(duì)abc.txt進(jìn)行壓縮，壓縮結(jié)果存儲(chǔ)在abc_code.tx忡。 解壓對(duì)abc_code.txt進(jìn)行解壓，恢復(fù)結(jié)果存儲(chǔ)在abc decode.txt中。對(duì)比abc.txt和abc_decode.txt.如果完全一致，表明 壓縮/解壓過程正確，反之不正確.對(duì)比abc.txt和abc_ decode.txt文件大小,計(jì)算壓縮比自適應(yīng)Huffman編碼Adaptive Huffman coding ( Dynamic Huffman coding )Huffman編碼需要實(shí)現(xiàn)知道輸入符號(hào)集的概率分布，為了 進(jìn)行編碼需要先對(duì)數(shù)據(jù)計(jì)算概率分布，然后再對(duì)數(shù)據(jù)進(jìn)行 編碼，需要對(duì)數(shù)

17、據(jù)掃描兩遍。對(duì)信源進(jìn)行哈夫曼編碼后形成了一個(gè)哈夫曼編碼表，若要 正確解碼必須依照此表.于是在信源存儲(chǔ)與傳輸過程中， 必須首先考応此表的存儲(chǔ)與傳輸，故此表也占有一定的比 特?cái)?shù)。一種解決方法是使用默認(rèn)的哈夫曼編碼表，而更 好的方法是自適應(yīng)Huffman編碼自適應(yīng)Huffman編碼不需要事先計(jì)算概率分布，能夠在 編碼/解碼過程中自動(dòng)建立Huffman編碼樹，只需要對(duì)數(shù) 據(jù)掃描一遍因而得到了廣泛應(yīng)用自適應(yīng)Huffman編碼Adaptive Huffman coding ( Dynamic Huffman coding )自適應(yīng)Huffman編碼的思想是從一)個(gè)空的Huffman編碼樹開始.空的NYTH

18、uffman編碼樹僅包含一個(gè)空節(jié)點(diǎn) NYT(Not Yet Transmitted),表示還沒有開始數(shù)據(jù)傳送。自適應(yīng)Huffman編碼Adaptive Huffman coding ( Dynamic Huffman coding )自適應(yīng)Huffman編碼的思想是從一 個(gè)空的Huffman編碼樹開始.空的 Huffman編碼樹僅包含一個(gè)空節(jié)點(diǎn) NYT(Not Yet Transmitted) 表示 還沒有開始數(shù)據(jù)傳送.讀入的第1個(gè)符號(hào)，不做壓縮直接 進(jìn)入輸出碼流，同時(shí)將其添加進(jìn)樹 中賦予碼字.自適應(yīng)Huffman編碼Adaptive Huffman coding ( Dynamic Huffman coding ) 每讀入*!個(gè)新的符號(hào)，輸出NYT,然 eAb. 后將新符號(hào)不做壓縮直接進(jìn)入輸出 同時(shí)將其添加進(jìn)樹中賦予碼00110001000皐流,Adaptive Huffman coding ( Dynamic Huffman coding )自適應(yīng)Huffman編碼自適應(yīng)Huffman編碼Adaptive Huffman coding ( Dynamic Huffman coding )自適應(yīng)Huffman編碼Adaptive Huffman codi