23. 印刷格物致知
          23.6. 壓縮演算法
 23.6.1. Huffman 壓縮

霍夫曼壓縮演算法 (Huffman compression algorithm,也稱為 Huffman Coding) 是以它的發明者大衛霍夫曼 (David Huffman) 的名字來命名,他是前麻省理工學院 (MIT) 教授,於 1952 年發表提出霍夫曼壓縮演算法 。

霍夫曼壓縮是一種無損失的壓縮演算法,是文字或程式檔案的最理想壓縮方式,這可能解釋了為什麼這許多壓縮程式如 ZIP 或 ARJ 都使用它。

霍夫曼壓縮如何工作

霍夫曼壓縮屬於一個編碼字元長度可變的演算法家族之一,這表示每一個符號(例如文字內的各字母)都被長度不等的各自一串位元序列取代,越常出現的符號以越短的字元序列替換,而越少出現的就以較長位元序列取代。因為原本的資料是以固定長度的系統編碼(例如:英文用 ASCII 或是繁體中文用 BIG5 或是 Unicode),所以編碼後自然就讓整個檔案變小了。

舉一個實際例子來說明展示這個的原理:假設想要壓縮下面這段資料:ACDABA

因為它有 6 個英文字元,所以這串文字占用 6 個位元組 (Bytes) 或 48 各位元 (Bits);使用霍夫曼編碼時,第一步先搜尋最經常出現的符號(在這個例子下,'A' 出現了 3 次),然後建立了一個分析各個字元出現的頻率的樹狀資料結構來決定如何取代符號位的位元序列。在這種例子下,演算法將使用下列的替代表: A=0, B=10, C=110, D=111,若按照這個替換表套入後,壓縮後的資料變成:01101110100

這表示只用了 11 個位元就可以取代了 48 個位元,在這個例子中壓縮比為 4 比 1。

夫曼編碼可以進一步以兩種不同的方式來優化:

  • 適應式霍夫曼編碼 (Adaptive Huffman):根據各符號出現機率的變化動態改變代碼。 
  • 擴展式霍夫曼編碼 (Extended Huffman):壓縮可以是對一群體符號來進行編碼,而非單一個符號。 

優點和缺點

這種壓縮演算法主要是文字或程式檔案能進行有效地壓縮,審視分析整個檔案的內容再建構出最佳的代碼表,是需要較長的計算時間代價,因此實用上大部分要考量平衡值,有時壓縮未必達到最好的可能性;它也是免費(無專利保護)、簡易、快速的壓縮法,但不適用於圖檔、已壓縮、亂數資料等等,印前使用的圖像則是最好使用其他壓縮演算法。

霍夫曼壓縮應用於哪裡

霍夫曼壓縮主要應用於像是 WINZIP, WINRAR, pkZIP, lha, gz, zoo, arj 壓縮程式,在 JPEG 和 MPEG 壓縮內也被用到。

延伸閱讀

根據這個利用符號出現的頻率之多寡來對資料重新編碼之基本概念,可以衍生與修正最佳化到某些應用上的變化形不計其數,變化的部分包含有:符號取樣方式、樹狀結構建立方式、統計取樣範圍、編碼法、...雖然它發佈於1952年,但至今仍有論文討論新意新法,如果有進一步的興趣請參考:huffman encoding,更進一步就到書局買書來看了(很厚的書)。

Table of contents