哈夫曼算法編碼原理與應(yīng)用

1、哈夫曼算法編碼原理與應(yīng)用哈夫曼算法編碼原理與應(yīng)用1概述信息時代，人們對使用計算機(jī)獲取信息、處理信息的依賴性越來越高。計算機(jī)系統(tǒng)面臨的是數(shù)值、文字、語言、音樂、圖形、動畫、靜圖像、電視視頻圖像等多種媒體。數(shù)字化的視頻和音頻信號的數(shù)量之大是驚人的，對于電視畫面的分辨率640×480的彩色圖像，30幀/s，則一秒鐘的數(shù)據(jù)量為：640×480×24×3022112M，所以播放時，需要221Mbps的通信回路。存儲時，1張CD可存640M，則僅可以存放 289s的數(shù)據(jù)。2哈夫曼算法編碼原理與應(yīng)用大數(shù)據(jù)量的圖像信息會給存儲器的存儲容量，通信干線信道的帶寬，以及計算機(jī)

2、的處理速度增加極大的壓力。單純靠增加存儲器容量，提高信道帶寬以及計算機(jī)的處理速度等方法來解決這個問題是不現(xiàn)實的，這時就要考慮壓縮。壓縮的關(guān)鍵在于編碼，如果在對數(shù)據(jù)進(jìn)行編碼時，對于常見的數(shù)據(jù)，編碼器輸出較短的碼字；而對于少見的數(shù)據(jù)則用較長的碼字表示，就能夠?qū)崿F(xiàn)壓縮。21舉個例子：假設(shè)一個文件中出現(xiàn)了8種符號S0，SQ，S2，S3，S4，S5，S6，S7，那么每種符號要編碼，至少需要3bit。假設(shè)編碼成000，001， 010，011，100，101，110，111。那么符號序列S0S1S7S0S1S6S2S2S3S4S5S0S0S1編碼后變成 00000111100000111001001001

3、1100101000000001，共用了42bit。我們發(fā)現(xiàn)S0，S1，S2這3個符號出現(xiàn)的頻率比較大，其它符號出現(xiàn)的頻率比較小，我們采用這樣的編碼方案：S0到S7的碼遼分別01，11，101，0000，0001，0010，0011， 100，那么上述符號序列變成011110001110011101101000000010010010111，共用了39bit。盡管有些碼字如 S3，S4，S5，S6變長了(由3位變成4位)，但使用頻繁的幾個碼字如S0，S1變短了，所以實現(xiàn)了壓縮。對于上述的編碼可能導(dǎo)致解碼出現(xiàn)非單值性：比如說，如果S0的碼字為01，S2的碼字為011，那么當(dāng)序列中出現(xiàn)011時，你

4、不知道是S0的碼字后面跟了個1，還是完整的一個S2的碼字。因此，編碼必須保證較短的編碼決不能是較長編碼的前綴。符合這種要求的編碼稱之為前綴編碼。要構(gòu)造符合這樣的二進(jìn)制編碼體系，可以通過二叉樹來實現(xiàn)。1)首先統(tǒng)計出每個符合出現(xiàn)的頻率，上例SO到S7的出現(xiàn)頻率分別為4/14，3/14，2/14，1/14，1/14，1/14，1/14，1/14。2)從左到右把上述頻率按從小到大的順序排列。3)每一次選出最小的兩個值，作為二叉樹的兩個葉子節(jié)點，將和作為它們的根節(jié)點，這兩個葉子節(jié)點不再參與比較，新的根節(jié)點參與比較。4)重復(fù)(3)，直到最后得到和為1的根節(jié)點。將形成的二叉樹的左節(jié)點標(biāo)0，右節(jié)點標(biāo)1。把從最

5、上面的根節(jié)點到最下面的葉子節(jié)點路徑中遇到的0，1序列串起來，得到各個符號的編碼?？梢钥吹剑栔荒艹霈F(xiàn)在樹葉上，任何一個字符的路徑都不會是另一字符路徑的前綴路徑，這樣，前綴編碼也就構(gòu)造成功了。這樣一棵二叉樹在數(shù)據(jù)結(jié)構(gòu)課程中稱之為Huffman樹，常用于最佳判定，它是最優(yōu)二叉樹，是一種帶權(quán)路徑長度最短的二叉樹。所謂樹的帶權(quán)路徑長度，就是樹中所有的葉結(jié)點的權(quán)值乘上其到根結(jié)點的路徑長度(若根結(jié)點為0層，葉結(jié)點到根結(jié)點的路徑長度為葉結(jié)點的層數(shù))。樹的帶權(quán)路徑長度記為：WPL (W1*L1W2*L2W3*L3Wn*Ln)，N個權(quán)值Wi(i1，2，n)構(gòu)成一棵有N個葉結(jié)點的二叉樹，相應(yīng)的葉結(jié)點的路徑長度為

6、 Li(i1，2，n)。Huffman樹得出的WPL值最小。22在對一幅大小為100，672bytes 8位BMP圖像文件進(jìn)行Huffman編碼過程中，作者按照以下步驟實現(xiàn)了的壓縮和解壓縮算法。1)掃描位圖文件的全部數(shù)據(jù)(對應(yīng)用于調(diào)色板的編碼)，完成數(shù)據(jù)頻度的統(tǒng)計。2)依據(jù)數(shù)據(jù)出現(xiàn)的頻度建立哈夫曼樹。3)將哈夫曼樹的信息寫入輸出文件(壓縮后文件)，以備解壓縮時使用。4)進(jìn)行第二遍掃描，將原文件所有編碼數(shù)據(jù)轉(zhuǎn)化為哈夫曼編碼，保存到輸出文件。解壓縮則為逆過程，以下是編碼和解碼的實現(xiàn)算法。a)定義數(shù)據(jù)結(jié)構(gòu)Node如下：Struct Nodelong freq；/該節(jié)點符號的頻率值，初值為0int p

7、arent；/該節(jié)點父節(jié)點的序號，初值為1int right；/該節(jié)點右子節(jié)點的序號，初值為1int left；/該節(jié)點左子節(jié)點的序號，初值為1Bmp tree511說明：之所以有511個節(jié)點，是因為每個字節(jié)可表示的符號個數(shù)為256個(對應(yīng)于256種顏色)二叉樹有256個葉節(jié)點，根據(jù)二叉樹的性質(zhì)總節(jié)點數(shù)為 2·2561511個節(jié)點。這里用0255個元素來依次對應(yīng)256種顏色。由第256以后的元素來依次對應(yīng)形成的各個父節(jié)點的信息，即父節(jié)點的編號從256開始。b)按照前述的壓縮步驟，先對欲壓縮文件的各個符號的使用次數(shù)進(jìn)行統(tǒng)計，填充于bmp tree0255 ·freq項內(nèi)；在已

8、有的節(jié)點中找出頻率最低的兩個節(jié)點，給出它們的父節(jié)點，將兩個節(jié)點號填充于父節(jié)點的right，left，將父節(jié)點號填充于兩個節(jié)點的Parent內(nèi)。重復(fù)步驟直到根節(jié)點，建樹工作完成。建樹完成后進(jìn)行編碼，對每個符號從符號的父節(jié)點開始。若節(jié)點的父節(jié)點值不為1，則一直進(jìn)行下去，直到樹根?；厮葸^程中遇左出0，遇右出1輸出編碼。Huffman編碼遞歸過程如下：Void Bmp Huff Code(int node,int child)ifBmp treenodeParent!1；/父節(jié)點為1的節(jié)點是樹根Bmp Huff Code(Bmp treenodeparent，node)；/若不為1則遞歸if(chil

9、d1)；/若不為葉節(jié)點if(childbmp treenoderight)；/右子節(jié)點，輸出“1”outputbit(1)；else if(childbmp treenodeleft)；/左子節(jié)點，輸出“0”O(jiān)utputbit(0)；c)解碼時從樹根開始，遇1取右節(jié)點，遇0取左節(jié)點，直到找到節(jié)點號小于256的節(jié)點(葉節(jié)點)。HuHnun解碼過程如下：Int Expand Huffman(Void)int nodeRoot-node-leaf；/解碼從根節(jié)點開始。doHead FlagGetonebit()；/從編碼串中讀取一位。if(Head Flag0)；/若為“0”，nodeHuffman-Tree(node-256)*2；/取當(dāng)前節(jié)點的左節(jié)點號；else if(Head Flag1)若為“1”nodeHuffman-tr