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

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

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

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

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

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

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

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

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

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