霍夫曼編碼霍夫曼編碼1目錄

一、什么是編碼二、霍夫曼編碼簡介三、霍夫曼編碼的熵四、霍夫曼編碼（一）霍夫曼編碼過程（二）霍夫曼樹的構建（三）霍夫曼表五、霍夫曼編碼特點第1頁/共14頁目錄

一、什么是編碼第1頁/共14頁2一.什么是編碼編碼是將源對象內容按照一種標準轉換為一種標準格式內容。源對象標準編碼后GooddayG112237456o2d3d4a5y6

7第2頁/共14頁一.什么是編碼編碼是將源對象內容按照一種標準轉換為一種標準3

二.霍夫曼編碼簡介

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

4三、霍夫曼編碼的熵

一個事件集合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)為各灰度級出現的概率，熵即表示平均信息量為多少比特，換句話說，熵是編碼所需比特數的下限，即編碼所需的最少比特。編碼一定要用不比熵少的比特數編碼才能完全保持原圖像的信息，這是圖像壓縮的下限。當a=2是，H的單位是比特。第4頁/共14頁三、霍夫曼編碼的熵

一個事件集合x1,x2,……xn,處于5四、霍夫曼編碼

設信息源空間為[A*P]:{A:a1a2……an}{P(A):P(a1)P(a2)P(a3)……P(an)}其中∑P(ak)=1,先用r個碼的號碼符號集X:{x1,x2,……xr}對信源A中的每一個符號ak進行編碼。編碼過程如下：把信源符號ai按其出現的概率的大小順序排列起來；把最末兩個具有最小概率的元素之概率加起來；把該概率之和同其余概率由大到小排隊，然后再把兩個最小概率加起來，再排隊；重復步驟

(2)、

(3),直到概率和達到

1為止

;在每次合并消息時，將被合并的消息賦以1和0或0和1；尋找從每個信源符號到概率為1處的路徑，記錄下路徑上的1和0；對每個符號寫出"1"、"0"序列（從碼數的根到終節點）。創建霍夫曼表。壓縮編碼時，將碼值用碼字代替。（一）霍夫曼編碼過程第5頁/共14頁四、霍夫曼編碼

設信息源空間為[A*P]:{A:a1a26（二）霍夫曼樹的構建

霍夫曼編碼實際上構造了一個碼樹，碼樹從最上層的端點開始構造，直到樹根結束。這里舉個例子說明如何生成霍夫曼樹。假設對由a1、a2、a3、a4、a5、a6、a7、a8八個信源符號組成的源信息字符串:“a1a1a2a2a3a3a3a4a4a4a4a5a5a5a6a6a6a7a7a8”進行霍夫曼編碼。首先應對信息中各數字出現的次數進行統計如下：

碼值

a1a2a3a4a5a6a7a8次數

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)第6頁/共14頁（二）霍夫曼樹的構建

霍夫曼編碼實際上構造了一個碼樹，碼樹從7具體過程是這樣的，先將所有符號排成一行，構成8個最底層

節點。首先將這些節點中最小兩個概率值相加：0.05+0.1=0.15,得到新的

節點這時擁有的概率值為0.2,0.1,0.1,0.15,0.15,0.15,0.15。第7頁/共14頁具體過程是這樣的，先將所有符號排成一行，構成8個最底層節8再將兩個最小的概率值相加得到新的節點......直到得到根節點概率為1.0為止。相加時，對于概率值相等的多個節點，可以任意選取。除根節點外，設節點左邊分支為0，右邊分支為1（也可以反過來）。這樣，生成的霍夫曼樹如下圖所示：第8頁/共14頁再將兩個最小的概率值相加得到新的節點......直到得到9對于各值（碼值）的代碼（碼字）就是從根節點出發到底層節點所經歷的分支序列。如a4的代碼（碼字）為00，a6的碼字為111......通常a4和a6等稱為碼值，00和111等稱為碼字。所有碼值和碼字對應關系如下表所示：第9頁/共14頁對于各值（碼值）的代碼（碼字）就是從根節點出發到底層節點所經10（三）霍夫曼表

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

第10頁/共14頁（三）霍夫曼表

將所有碼值和碼字的關系整理成一張表，為了整字11進行壓縮編碼時，只要將碼值用碼字代替即可。所以源符a1a1a2a2a3a3a3a4a4a4a4a5a5a5a6a6a6a7a7a8編碼為：。平均碼長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%第11頁/共14頁進行壓縮編碼時，只要將碼值用碼字代替即可。所以源符a1a112五、霍夫曼編碼的特點

1.霍夫曼方法構造出來的碼不是唯一的。原因：在給兩個分支賦值時

,可以是左支

(或上支

)為

0,也可以是右支

(或下支

)為

0,造成編碼的不唯一。當兩個消息的概率相等時,誰前誰后也是隨機的

,構造出來的碼字就不是唯一的。

2.霍夫曼編碼碼字字長參差不齊

。3.霍夫曼編碼對不同的信源的編碼效率是不同的。

當信源概率相等時

,其編碼效率最低。只有在概率分布很不均勻時

,霍夫曼編碼才會收到顯著的效果

。4.解碼時

,必須參照霍夫曼編碼表才能正確譯碼。

在信源的存儲與傳輸過程中必須首先存儲或傳輸這一霍夫曼編碼表，在實際計算壓縮效果時

,必須考慮霍夫曼編碼表占有的比特數。在某些應用場合,信源概率服從于某一分布或存在一定規律

(這主要由大量的統計得到

),這樣就可以在發送端和接收端固定霍夫曼編碼表

,在傳輸數據時就省去了傳輸霍夫曼編碼表

,這種方法稱為霍夫曼編碼表缺省使用。第12頁/共14頁五、霍夫曼編碼的特點

1.霍夫曼方法構造出來的碼不是唯一13謝謝大家!第13頁/共14頁第13頁/共14頁14感謝您的觀看。第14頁/共14頁感謝您的觀看。第14頁/共14頁15霍夫曼編碼霍夫曼編碼16目錄

一、什么是編碼二、霍夫曼編碼簡介三、霍夫曼編碼的熵四、霍夫曼編碼（一）霍夫曼編碼過程（二）霍夫曼樹的構建（三）霍夫曼表五、霍夫曼編碼特點第1頁/共14頁目錄

一、什么是編碼第1頁/共14頁17一.什么是編碼編碼是將源對象內容按照一種標準轉換為一種標準格式內容。源對象標準編碼后GooddayG112237456o2d3d4a5y6

7第2頁/共14頁一.什么是編碼編碼是將源對象內容按照一種標準轉換為一種標準18

二.霍夫曼編碼簡介

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

19三、霍夫曼編碼的熵

一個事件集合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)為各灰度級出現的概率，熵即表示平均信息量為多少比特，換句話說，熵是編碼所需比特數的下限，即編碼所需的最少比特。編碼一定要用不比熵少的比特數編碼才能完全保持原圖像的信息，這是圖像壓縮的下限。當a=2是，H的單位是比特。第4頁/共14頁三、霍夫曼編碼的熵

一個事件集合x1,x2,……xn,處于20四、霍夫曼編碼

設信息源空間為[A*P]:{A:a1a2……an}{P(A):P(a1)P(a2)P(a3)……P(an)}其中∑P(ak)=1,先用r個碼的號碼符號集X:{x1,x2,……xr}對信源A中的每一個符號ak進行編碼。編碼過程如下：把信源符號ai按其出現的概率的大小順序排列起來；把最末兩個具有最小概率的元素之概率加起來；把該概率之和同其余概率由大到小排隊，然后再把兩個最小概率加起來，再排隊；重復步驟

(2)、

(3),直到概率和達到

1為止

;在每次合并消息時，將被合并的消息賦以1和0或0和1；尋找從每個信源符號到概率為1處的路徑，記錄下路徑上的1和0；對每個符號寫出"1"、"0"序列（從碼數的根到終節點）。創建霍夫曼表。壓縮編碼時，將碼值用碼字代替。（一）霍夫曼編碼過程第5頁/共14頁四、霍夫曼編碼

設信息源空間為[A*P]:{A:a1a221（二）霍夫曼樹的構建

霍夫曼編碼實際上構造了一個碼樹，碼樹從最上層的端點開始構造，直到樹根結束。這里舉個例子說明如何生成霍夫曼樹。假設對由a1、a2、a3、a4、a5、a6、a7、a8八個信源符號組成的源信息字符串:“a1a1a2a2a3a3a3a4a4a4a4a5a5a5a6a6a6a7a7a8”進行霍夫曼編碼。首先應對信息中各數字出現的次數進行統計如下：

碼值

a1a2a3a4a5a6a7a8次數

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)第6頁/共14頁（二）霍夫曼樹的構建

霍夫曼編碼實際上構造了一個碼樹，碼樹從22具體過程是這樣的，先將所有符號排成一行，構成8個最底層

節點。首先將這些節點中最小兩個概率值相加：0.05+0.1=0.15,得到新的

節點這時擁有的概率值為0.2,0.1,0.1,0.15,0.15,0.15,0.15。第7頁/共14頁具體過程是這樣的，先將所有符號排成一行，構成8個最底層節23再將兩個最小的概率值相加得到新的節點......直到得到根節點概率為1.0為止。相加時，對于概率值相等的多個節點，可以任意選取。除根節點外，設節點左邊分支為0，右邊分支為1（也可以反過來）。這樣，生成的霍夫曼樹如下圖所示：第8頁/共14頁再將兩個最小的概率值相加得到新的節點......直到得到24對于各值（碼值）的代碼（碼字）就是從根節點出發到底層節點所經歷的分支序列。如a4的代碼（碼字）為00，a6的碼字為111......通常a4和a6等稱為碼值，00和111等稱為碼字。所有碼值和碼字對應關系如下表所示：第9頁/共14頁對于各值（碼值）的代碼（碼字）就是從根節點出發到底層節點所經25（三）霍夫曼表

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

第10頁/共14頁（三）霍夫曼表

將所有碼值和碼字的關系整理成一張表，為了整字26進行壓縮編碼時，只要將碼值用碼字代替即可。所以源符a1a1a2a2a3a3a3a4a4a4a4a5a5a5a6a6a6a7a7a8編碼為：。平均碼長B=0.1*3+0.1*3+0.15*3+0.2*2+0.15*3+0