信息時(shí)代，人們對使用計算機獲取信息、處理信息的依賴(lài)性越來(lái)越高。計算機系統面臨的是數值、文字、語(yǔ)言、音樂(lè )、圖形、動(dòng)畫(huà)、靜圖像、電視視頻圖像等多種媒體。數字化的視頻和音頻信號的數量之大是驚人的，對于電視畫(huà)面的分辨率640×480的彩色圖像，30幀/s，則一秒鐘的數據量為：640×480×24×30＝22112M，所以播放時(shí)，需要221Mbps的通信回路。存儲時(shí)，1張CD可存640M，則僅可以存放 289s的數據。
2哈夫曼算法編碼原理與應用
大數據量的圖像信息會(huì )給存儲器的存儲容量，通信干線(xiàn)信道的帶寬，以及計算機的處理速度增加極大的壓力。單純靠增加存儲器容量，提高信道帶寬以及計算機的處理速度等方法來(lái)解決這個(gè)問(wèn)題是不現實(shí)的，這時(shí)就要考慮壓縮。壓縮的關(guān)鍵在于編碼，如果在對數據進(jìn)行編碼時(shí)，對于常見(jiàn)的數據，編碼器輸出較短的碼字；而對于少見(jiàn)的數據則用較長(cháng)的碼字表示，就能夠實(shí)現壓縮。
21舉個(gè)例子：假設一個(gè)文件中出現了8種符號S0，SQ，S2，S3，S4，S5，S6，S7，那么每種符號要編碼，至少需要3bit。假設編碼成000，001， 010，011，100，101，110，111。那么符號序列S0S1S7S0S1S6S2S2S3S4S5S0S0S1編碼后變成 000001111000001110010010011100101000000001，共用了42bit。我們發(fā)現S0，S1，S2這3個(gè)符號出現的頻率比較大，其它符號出現的頻率比較小，我們采用這樣的編碼方案：S0到S7的碼遼分別01，11，101，0000，0001，0010，0011， 100，那么上述符號序列變成011110001110011101101000000010010010111，共用了39bit。盡管有些碼字如 S3，S4，S5，S6變長(cháng)了(由3位變成4位)，但使用頻繁的幾個(gè)碼字如S0，S1變短了，所以實(shí)現了壓縮。對于上述的編碼可能導致解碼出現非單值性：比如說(shuō)，如果S0的碼字為01，S2的碼字為011，那么當序列中出現011時(shí)，你不知道是S0的碼字后面跟了個(gè)1，還是完整的一個(gè)S2的碼字。因此，編碼必須保證較短的編碼決不能是較長(cháng)編碼的前綴。符合這種要求的編碼稱(chēng)之為前綴編碼。要構造符合這樣的二進(jìn)制編碼體系，可以通過(guò)二叉樹(shù)來(lái)實(shí)現。
1)首先統計出每個(gè)符合出現的頻率，上例SO到S7的出現頻率分別為4/14，3/14，2/14，1/14，1/14，1/14，1/14，1/14。
2)從左到右把上述頻率按從小到大的順序排列。
3)每一次選出最小的兩個(gè)值，作為二叉樹(shù)的兩個(gè)葉子節點(diǎn)，將和作為它們的根節點(diǎn)，這兩個(gè)葉子節點(diǎn)不再參與比較，新的根節點(diǎn)參與比較。
4)重復(3)，直到最后得到和為1的根節點(diǎn)。
將形成的二叉樹(shù)的左節點(diǎn)標0，右節點(diǎn)標1。把從最上面的根節點(diǎn)到最下面的葉子節點(diǎn)路徑中遇到的0，1序列串起來(lái)，得到各個(gè)符號的編碼。
可以看到，符號只能出現在樹(shù)葉上，任何一個(gè)字符的路徑都不會(huì )是另一字符路徑的前綴路徑，這樣，前綴編碼也就構造成功了。
這樣一棵二叉樹(shù)在數據結構課程中稱(chēng)之為Huffman樹(shù)，常用于最佳判定，它是最優(yōu)二叉樹(shù)，是一種帶權路徑長(cháng)度最短的二叉樹(shù)。所謂樹(shù)的帶權路徑長(cháng)度，就是樹(shù)中所有的葉結點(diǎn)的權值乘上其到根結點(diǎn)的路徑長(cháng)度(若根結點(diǎn)為0層，葉結點(diǎn)到根結點(diǎn)的路徑長(cháng)度為葉結點(diǎn)的層數)。樹(shù)的帶權路徑長(cháng)度記為：WPL＝ (W1*L1＋W2*L2＋W3*L3＋…＋Wn*Ln)，N個(gè)權值Wi(i＝1，2，…n)構成一棵有N個(gè)葉結點(diǎn)的二叉樹(shù)，相應的葉結點(diǎn)的路徑長(cháng)度為 Li(i＝1，2，…n)。Huffman樹(shù)得出的WPL值最小。
22在對一幅大小為100，672bytes 8位BMP圖像文件進(jìn)行Huffman編碼過(guò)程中，作者按照以下步驟實(shí)現了的壓縮和解壓縮算法。
1)掃描位圖文件的全部數據(對應用于調色板的編碼)，完成數據頻度的統計。
2)依據數據出現的頻度建立哈夫曼樹(shù)。
3)將哈夫曼樹(shù)的信息寫(xiě)入輸出文件(壓縮后文件)，以備解壓縮時(shí)使用。
4)進(jìn)行第二遍掃描，將原文件所有編碼數據轉化為哈夫曼編碼，保存到輸出文件。解壓縮則為逆過(guò)程，以下是編碼和解碼的實(shí)現算法。
a)定義數據結構Node如下：
Struct Node
{long freq；//該節點(diǎn)符號的頻率值，初值為0
int parent；//該節點(diǎn)父節點(diǎn)的序號，初值為－1
int right；//該節點(diǎn)右子節點(diǎn)的序號，初值為－1
int left；//該節點(diǎn)左子節點(diǎn)的序號，初值為－1
?。麭mp tree［511］
說(shuō)明：
之所以有511個(gè)節點(diǎn)，是因為每個(gè)字節可表示的符號個(gè)數為256個(gè)(對應于256種顏色)二叉樹(shù)有256個(gè)葉節點(diǎn)，根據二叉樹(shù)的性質(zhì)總節點(diǎn)數為 2·256－1＝511個(gè)節點(diǎn)。這里用0～255個(gè)元素來(lái)依次對應256種顏色。由第256以后的元素來(lái)依次對應形成的各個(gè)父節點(diǎn)的信息，即父節點(diǎn)的編號從256開(kāi)始。
b)按照前述的壓縮步驟，先對欲壓縮文件的各個(gè)符號的使用次數進(jìn)行統計，填充于bmp tree［0～255］ ·freq項內；在已有的節點(diǎn)中找出頻率最低的兩個(gè)節點(diǎn)，給出它們的父節點(diǎn)，將兩個(gè)節點(diǎn)號填充于父節點(diǎn)的right，left，將父節點(diǎn)號填充于兩個(gè)節點(diǎn)的Parent內。重復步驟直到根節點(diǎn)，建樹(shù)工作完成。
建樹(shù)完成后進(jìn)行編碼，對每個(gè)符號從符號的父節點(diǎn)開(kāi)始。若節點(diǎn)的父節點(diǎn)值不為－1，則一直進(jìn)行下去，直到樹(shù)根?；厮葸^(guò)程中遇左出0，遇右出1輸出編碼。
Huffman編碼遞歸過(guò)程如下：
Void Bmp Huff Code(int node,int child)
if{Bmp tree［node］P(pán)arent!＝－1}；//父節點(diǎn)為－1的節點(diǎn)是樹(shù)根
Bmp Huff Code(Bmp tree［node］parent，node)；//若不為－1則遞歸
if(child≠－1)；//若不為葉節點(diǎn)
{if(child＝bmp tree［node］right)；//右子節點(diǎn)，輸出“1”
outputbit(1)；
else if(child＝bmp tree［node］left)；//左子節點(diǎn)，輸出“0”
Outputbit(0)；
}
c)解碼時(shí)從樹(shù)根開(kāi)始，遇1取右節點(diǎn)，遇0取左節點(diǎn)，直到找到節點(diǎn)號小于256的節點(diǎn)(葉節點(diǎn))。
HuHnun解碼過(guò)程如下：
Int Expand Huffman(Void)
{int node＝Root-node-leaf；//解碼從根節點(diǎn)開(kāi)始。
do
{Head Flag＝Getonebit()；//從編碼串中讀取一位。
if(Head Flag＝0)；//若為“0”，
{node＝Huffman-Tree［(node-256)*2］；}//取當前節點(diǎn)的左節點(diǎn)號；
else if(Head Flag＝1)若為“1”
{node＝Huffman-tree［)node-256)*2＋1］；}//取當前節點(diǎn)的右節點(diǎn)號；
}While(node>＝256)；//節點(diǎn)號大于256繼續循環(huán)
}expanddata-buffer［counter＋＋］＝node；//輸出解碼得到一個(gè)字節
壓縮后的文件大小為48，431bytes，壓縮比為481%，解壓縮后的數據讀出的圖像正常。
本站僅提供存儲服務(wù)，所有內容均由用戶(hù)發(fā)布，如發(fā)現有害或侵權內容，請
點(diǎn)擊舉報。
