霍夫曼編碼教案資料

霍夫曼編碼(biānmǎ)HuffmanCoding長春(chánɡchūn)理工大學(xué)080212418高延邦圖像(túxiànɡ)無損壓縮第一頁，共14頁。目錄(mùlù)

一、什么(shénme)是編碼二、霍夫曼編碼簡介三、霍夫曼編碼的熵四、霍夫曼編碼（一）霍夫曼編碼過程（二）霍夫曼樹的構(gòu)建（三）霍夫曼表五、霍夫曼編碼特點(diǎn)第二頁，共14頁。一.什么(shénme)是編碼編碼是將源對(duì)象內(nèi)容按照一種標(biāo)準(zhǔn)轉(zhuǎn)換(zhuǎnhuàn)為一種標(biāo)準(zhǔn)格式內(nèi)容。源對(duì)象標(biāo)準(zhǔn)編碼后GooddayG112237456o2d3d4a5y6

7第三頁，共14頁。二.霍夫曼編碼(biānmǎ)簡介

霍夫曼編碼是不定長編碼，即代表各元素的碼字長度不等。該方法完全依據(jù)(yījù)字符出現(xiàn)概率來構(gòu)造平均長度最短的碼字，有時(shí)稱之為最佳編碼。該編碼是基于不同符號(hào)的概率分布，在信息源中出現(xiàn)概率越大的符號(hào)，相應(yīng)的碼越短；出現(xiàn)概率越小的符號(hào)，其碼越長，從而達(dá)到用盡可能少的碼符號(hào)表示源數(shù)據(jù)。它在變長編碼中是最佳的。在計(jì)算機(jī)信息處理中，“霍夫曼編碼”是一種一致性編碼法（又稱"熵編碼法"）。DavidAlbertHuffman戴維·霍夫曼第四頁，共14頁。三、霍夫曼編碼(biānmǎ)的熵

一個(gè)事件集合x1,x2,……xn,處于一個(gè)基本概率空間，其相應(yīng)概率為p1,p2,……pn,且p1,p2,……pn之和為1，每一個(gè)事件的信息量為I(xk)=-logn(pk),如定義在空間中的每一事件的概率不相等的平均不肯定程度或平均信息量叫做熵H，則H=E{I(xk)}=∑pkI(xk)=-∑pkloga(pk)。對(duì)于圖像來說，n=2m個(gè)灰度級(jí)xi,則p(xi)為各灰度級(jí)出現(xiàn)的概率，熵即表示平均信息量為多少比特，換句話說，熵是編碼所需比特?cái)?shù)的下限，即編碼所需的最少比特。編碼一定要用不比熵少的比特?cái)?shù)編碼才能完全保持(bǎochí)原圖像的信息，這是圖像壓縮的下限。當(dāng)a=2是，H的單位是比特。第五頁，共14頁。四、霍夫曼編碼(biānmǎ)

設(shè)信息源空間為[A*P]:{A:a1a2……an}{P(A):P(a1)P(a2)P(a3)……P(an)}其中∑P(ak)=1,先用r個(gè)碼的號(hào)碼(hàomǎ)符號(hào)集X:{x1,x2,……xr}對(duì)信源A中的每一個(gè)符號(hào)ak進(jìn)行編碼。編碼過程如下：把信源符號(hào)ai按其出現(xiàn)的概率的大小順序排列起來；把最末兩個(gè)具有最小概率的元素之概率加起來；把該概率之和同其余概率由大到小排隊(duì)，然后再把兩個(gè)最小概率加起來，再排隊(duì)；重復(fù)步驟(2)、(3),直到概率和達(dá)到1為止;在每次合并消息時(shí)，將被合并的消息賦以1和0或0和1；尋找從每個(gè)信源符號(hào)到概率為1處的路徑，記錄下路徑上的1和0；對(duì)每個(gè)符號(hào)寫出"1"、"0"序列（從碼數(shù)的根到終節(jié)點(diǎn)）。創(chuàng)建霍夫曼表。壓縮編碼時(shí)，將碼值用碼字代替。（一）霍夫曼編碼(biānmǎ)過程第六頁，共14頁。（二）霍夫曼樹的構(gòu)建(ɡòujiàn)

霍夫曼編碼實(shí)際上構(gòu)造了一個(gè)碼樹，碼樹從最上層的端點(diǎn)開始構(gòu)造，直到樹根結(jié)束。這里舉個(gè)例子說明如何生成霍夫曼樹。假設(shè)對(duì)由a1、a2、a3、a4、a5、a6、a7、a8八個(gè)信源符號(hào)組成的源信息字符串:“a1a1a2a2a3a3a3a4a4a4a4a5a5a5a6a6a6a7a7a8”進(jìn)行霍夫曼編碼。首先應(yīng)對(duì)信息中各數(shù)字出現(xiàn)的次數(shù)進(jìn)行統(tǒng)計(jì)(tǒngjì)如下：

碼值

a1a2a3a4a5a6a7a8次數(shù)

22343331概率0.10.10.150.20.150.150.10.05熵H＝-0.1*log2(0.1)-0.1*log2(0.1)-0.15*log2(0.15)-0.2*log2(0.2)-0.15*log2(0.15)-0.15*log2(0.15)-0.1*log2(0.1)-0.05*log2(0.05)=2.9087(bit)第七頁，共14頁。具體過程是這樣的，先將所有符號(hào)排成一行，構(gòu)成8個(gè)最底層節(jié)點(diǎn)。首先(shǒuxiān)將這些節(jié)點(diǎn)中最小兩個(gè)概率值相加：0.05+0.1=0.15,得到新的節(jié)點(diǎn)這時(shí)擁有的概率值為0.2,0.1,0.1,0.15,0.15,0.15,0.15。第八頁，共14頁。再將兩個(gè)最小的概率(gàilǜ)值相加得到新的節(jié)點(diǎn)......直到得到根節(jié)點(diǎn)概率(gàilǜ)為1.0為止。相加時(shí)，對(duì)于概率(gàilǜ)值相等的多個(gè)節(jié)點(diǎn)，可以任意選取。除根節(jié)點(diǎn)外，設(shè)節(jié)點(diǎn)左邊分支為0，右邊分支為1（也可以反過來）。這樣，生成的霍夫曼樹如下圖所示：第九頁，共14頁。對(duì)于各值（碼值）的代碼（碼字）就是從根節(jié)點(diǎn)出發(fā)到底層節(jié)點(diǎn)所經(jīng)歷的分支序列。如a4的代碼（碼字）為00，a6的碼字為111......通常a4和a6等稱為(chēnɡwéi)碼值，00和111等稱為(chēnɡwéi)碼字。所有碼值和碼字對(duì)應(yīng)關(guān)系如下表所示：第十頁，共14頁。（三）霍夫曼表

將所有碼值和碼字的關(guān)系整理成一張表，為了整字節(jié)輸出碼字，表中還含有各碼字的長度(chángdù)。這種表就稱為霍夫曼表。本例霍夫曼表如表所示：

第十一頁，共14頁。進(jìn)行壓縮編碼時(shí)，只要(zhǐyào)將碼值用碼字代替即可。所以源符a1a1a2a2a3a3a3a4a4a4a4a5a5a5a6a6a6a7a7a8編碼為：0100100110111011011010000000011011011010000100001001。平均碼長B=0.1*3+0.1*3+0.15*3+0.2*2+0.15*3+0.15*3+0.1*4+0.05*4＝2.95(b)熵H＝2.9087編碼效率N=H/B=2.9087/2.95=98.6%第十二頁，共14頁。五、霍夫曼編碼(biānmǎ)的特點(diǎn)

1.霍夫曼方法構(gòu)造出來的碼不是唯一的。原因：在給兩個(gè)分支賦值時(shí),可以是左支(或上支)為0,也可以是右支(或下支)為0,造成編碼的不唯一。當(dāng)兩個(gè)消息的概率相等時(shí),誰前誰后也是隨機(jī)的,構(gòu)造出來的碼字就不是唯一的。2.霍夫曼編碼碼字字長參差不齊。3.霍夫曼編碼對(duì)不同的信源的編碼效率是不同的。當(dāng)信源概率相等時(shí),其編碼效率最低。只有在概率分布很不均勻時(shí),霍夫曼編碼才會(huì)收到顯著的效果。4.解碼時(shí),必須參照霍夫曼編碼表才能正確譯碼。在信源的存儲(chǔ)與傳輸過程中必須首先存儲(chǔ)或傳輸這一霍夫曼編碼表，在實(shí)際計(jì)算壓縮效果時(shí),必須考慮霍夫曼編