霍夫曼編碼法

 

Huffman’s Encode的概念:

霍夫曼編碼法Huffman’s Encode是霍夫曼在1952年所提出的一種無失真壓縮技術,其原理是將欲壓縮之字串,先讀一遍,將字串中的每一相異單字元(Single Character)的出現頻率,做成統計,依此建構霍夫曼樹(Huffman’s Tree)。每一相異單字元,用01予以編碼,出現次數逾多者,給予較少的位元編碼,最後將這些位元串組合起來,並加上Huffman’s tree ,就成為壓縮檔案。Huffman編碼法為依資訊源符號出現機率,在對資訊源符號逐一編碼條件下(The symbols be coded one at a time),最佳之編碼方法。

 

Huffman’s Encode的特性:

Huffman編碼法的特點在於所編碼出來的檔案具有唯一碼性質的即時碼。也就是各個相異字元所編碼出所位元串並不相同,解碼時能立即解出。也就是說,Huffman編碼法之解碼過程為即時(Instantaneous) 且為唯一(Uniquely Decodable) 之解碼。

 

舉例說明Huffman’s Encode:

Example 1:

1. 輸入一字串 YAHOO

2. 統計每一相異字元出現次數   Y:1  A:1  H:1  O:2

3. 出現次數由大到小排列 O:2  Y:1  A:1  H:1  並令其為各節點

4. 找出加權比重小的兩個節點,為這兩節點做父節點,並將兩節點之權值相加給予此父節點。

5. 重複第四步,直到找到樹根(root)

6. 建構完成霍夫曼樹,樹枝右邊給0,左邊給1

7. 完成編碼:

編碼:   O->0    Y->10   A->110  H->111 

        YAHOO  -> 10 110 111 0 0

 

Example 2:

 

**目前本項技術普遍應用在一般商業壓縮軟體、傳真機及無失真之靜態影像上。**