無失真壓縮算法的先行者：David Huffman 的故事

大家在壓縮文件的時候有沒有想過，為什麼文件經壓縮後既減少了存儲空間，又不會損害文件本身的內容？

在電腦資料處理中，霍夫曼編碼（Huffman’s Encode）的利用，透過出現機率高的字母使用較短的編碼，反之出現機率低的則使用較長的編碼，使編碼之後的字串的平均長度、期望值降低，從而達到無失真壓縮資料的目的。

而提到這個霍夫曼編碼，就不得不提它的發明者 — 大衛·霍夫曼（David Huffman）。

為了不用考試，他提出了霍夫曼編碼

霍夫曼大生於美國俄亥俄州，在18歲的時候已經在俄亥俄州立大學取得電機工程學士。在服軍役及修讀碩士後，他進入了麻省理工學院攻讀博士，主修電機工程。

在他攻讀博士的期間，霍夫曼和修讀資訊論課程的同學可以在完成學期報告還是期末考試中選擇，而為了不去考試，他選擇了完成學期報告。而當時學期報告的題目是：尋找最有效的二進制編碼。

霍夫曼在多月的研究後仍然無法證明哪個已有編碼是最有效的。正當他把他的筆記扔進垃圾桶時，他突然靈機一觸，放棄對已有編碼的研究，轉向新的探索，最終發現了基於有序頻率二元樹編碼的想法，亦即是後來被稱為霍夫曼編碼的方法，亦證明了這個方法是最有效的。

霍夫曼編碼的原理是用較少碼來表示出現頻率最高的字符，用較多的碼表示出現頻率低的字符，這便使編碼之後的字串的平均長度降低，從而達到無失真壓縮資料的目的。

霍夫曼編碼的步驟如下：

1）按字符出現的概率按多少的順序排隊。

2）把兩個最小的概率相加，並繼續這一步驟，始終將較高的概率分支放在右邊，直到最後變成概率１。

3）畫出由概率１處到每個信源符號的路徑，順序記下沿路徑的０和１，所得就是該符號的霍夫曼碼字。

4）將每對組合的左邊一個指定為0，右邊一個指定為1（或相反）。

舉例來說，以這句句子「this is an example of a huffman tree」，空格出現的頻率最多，x出現的頻率最少，所以空格的編碼最短，x的編碼最長，整句句子共需要135 bit。

為了紀念他的成就，人們把他在編碼中用到的特殊二元樹稱之為霍夫曼樹，將他的編碼方法稱為霍夫曼編碼。

現時霍夫曼編碼主要用於幫助壓縮MP3音樂文件和JPEG圖像，從而令文件的所需空間更少。

即使很多人使用霍夫曼代碼用來壓縮文件，但霍夫曼從未試圖從他的作品中獲得發明專利。相反，他把精力集中在教育上。用霍夫曼的話說，「我的產品就是我的學生。（My products are my students.）」

資料來源：維基