霍夫曼編碼教案資料

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

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

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

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

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

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

霍夫曼編碼實際上構造了一個碼樹，碼樹從最上層的端點開始構造，直到樹根結束。這里舉個例子說明如何生成霍夫曼樹。假設對由a1、a2、a3、a4、a5、a6、a7、a8八個信源符號組成的源信息字符串:“a1a1a2a2a3a3a3a4a4a4a4a5a5a5a6a6a6a7a7a8”進行霍夫曼編碼。首先應對信息中各數(shù)字出現(xiàn)的次數(shù)進行統(tǒng)計(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頁。具體過程是這樣的，先將所有符號排成一行，構成8個最底層節(jié)點。首先(shǒuxiān)將這些節(jié)點中最小兩個概率值相加：0.05+0.1=0.15,得到新的節(jié)點這時擁有的概率值為0.2,0.1,0.1,0.15,0.15,0.15,0.15。第八頁，共14頁。再將兩個最小的概率(gàilǜ)值相加得到新的節(jié)點......直到得到根節(jié)點概率(gàilǜ)為1.0為止。相加時，對于概率(gàilǜ)值相等的多個節(jié)點，可以任意選取。除根節(jié)點外，設節(jié)點左邊分支為0，右邊分支為1（也可以反過來）。這樣，生成的霍夫曼樹如下圖所示：第九頁，共14頁。對于各值（碼值）的代碼（碼字）就是從根節(jié)點出發(fā)到底層節(jié)點所經(jīng)歷的分支序列。如a4的代碼（碼字）為00，a6的碼字為111......通常a4和a6等稱為(chēnɡwéi)碼值，00和111等稱為(chēnɡwéi)碼字。所有碼值和碼字對應關系如下表所示：第十頁，共14頁。（三）霍夫曼表

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

第十一頁，共14頁。進行壓縮編碼時，只要(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ǎ)的特點

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