霍夫曼编码

簡介

在電腦資料處理中，霍夫曼編碼使用變長編碼表對源符號（如檔案中的一個字母）進行編碼，其中變長編碼表是通過一種評估來源符號出現機率的方法得到的，出現機率高的字母使用較短的編碼，反之出現機率低的則使用較長的編碼，這便使編碼之後的字串的平均長度、期望值降低，從而達到無失真壓縮資料的目的。
例如，在英文中，e的出現機率最高，而z的出現概率則最低。當利用霍夫曼編碼對一篇英文進行壓縮時，e極有可能用一個位元來表示，而z則可能花去25個位元（不是26）。用普通的表示方法時，每個英文字母均占用一個位元組，即8個位元。二者相比，e使用了一般編碼的1/8的長度，z則使用了3倍多。倘若我們能實現對於英文中各個字母出現概率的較準確的估算，就可以大幅度提高無失真壓縮的比例。
霍夫曼樹又稱最優二元樹，是一種帶權路徑長度最短的二元樹。所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點爲0層，葉結點到根結點的路徑長度爲葉結點的層數）。樹的路徑長度是從樹根到每一結點的路徑長度之和，記爲WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N個權值Wi（i=1,2,...n）構成一棵有N個葉結點的二元樹，相應的葉結點的路徑長度爲Li（i=1,2,...n）。可以證明霍夫曼樹的WPL是最小的。

歷史

1951年，霍夫曼在麻省理工學院（MIT）攻讀博士學位，他和修讀資訊論課程的同學得選擇是完成學期報告還是期末考試。導師羅伯特·法諾（Robert Fano）出的學期報告題目是：尋找最有效的二進制編碼。由於無法證明哪個已有編碼是最有效的，霍夫曼放棄對已有編碼的研究，轉向新的探索，最終發現了基於有序頻率二元樹編碼的想法，並很快證明了這個方法是最有效的。霍夫曼使用自底向上的方法構建二元樹，避免了次優演算法香農-范諾編碼（Shannon–Fano coding）的最大弊端──自頂向下構建樹。
1952年，於論文《一種構建極小多餘編碼的方法》（A Method for the Construction of Minimum-Redundancy Codes）中發表了這個編碼方法。

範例

霍夫曼樹常處理符號編寫工作。根據整組資料中符號出現的頻率高低，決定如何給符號編碼。如果符號出現的頻率越高，則給符號的碼越短，相反符號的號碼越長。假設我們要給一個英文單字"F O R G E T"進行霍夫曼編碼，而每個英文字母出現的頻率分別列在Fig.1。

資料解壓縮

簡單來說，霍夫曼碼樹的解壓縮就是將得到的前置碼（Prefix Huffman code）轉換回符號，通常藉由樹的追蹤（Traversal），將接收到的位元串（Bits stream）一步一步還原。但是要追蹤樹之前，必須要先重建霍夫曼樹；某些情況下，如果每個符號的權重可以被事先預測，那麼霍夫曼樹就可以預先重建，並且儲存並重複使用，否則，傳送端必須預先傳送霍夫曼樹的相關資訊給接收端。
最簡單的方式，就是預先統計各符號的權重並加入至壓縮之位元串，但是此法的運算量花費相當大，並不適合實際的應用。若是使用Canonical encoding，則可精準得知樹重建的資料量只占B2^B位元（其中B為每個符號的位元數（bits））。如果簡單將接收到的位元串一個位元一個位元的重建，例如：'0'表示父節點，'1'表示終端節點，若每次讀取到1時，下8個位元則會被解讀是終端節點（假設資料為8-bit字母），則霍夫曼樹則可被重建，以此方法，資料量的大小可能為2~320位元組不等。雖然還有很多方法可以重建霍夫曼樹，但因為壓縮的資料串包含"traling bits"，所以還原時一定要考慮何時停止，不要還原到錯誤的值，如在資料壓縮時時加上每筆資料的長度等。

基本性質

考量到不同的應用領域以及該領域的平均性質，將會使用不同的通用機率，又或者，這個機率是可以從被壓縮文字中的實際頻率所取得。

最佳化

原始的霍夫曼演算法是一個符號與符號間已知輸入機率分布的最佳編碼方式，也就是說將不相關的符號個別編碼為如此的資料串流。然而，當符號間的限制被捨棄或是品質機率函式是未知的時候，如此方式則並非最佳化。此外，當這些符號之間不是互相獨立，且分布不相同的時候，單一一個符號可能不足以實現最佳化。在這種情況之下，算術編碼可能比起霍夫曼編碼會有更佳的壓縮能力。
雖然上述兩種方法都可以組合任意數量的符號以實現更高效的編碼效果，並且通常適應於實際的輸入統計層面，但儘管最簡單的版本比霍夫曼編碼更慢且更複雜，算術編碼不會顯著增加其計算或演算法複雜度。當輸入概率不是精確已知或在流內顯著變化時，這種靈活性特別有用。然而，霍夫曼編碼通常更快，並且算術編碼在歷史上是專利問題的一些主題。因此，許多技術歷來避免使用有利於霍夫曼和其他前綴編碼技術的算術編碼。截至2010年中期，隨著早期專利的到期，這種替代霍夫曼編碼的最常用技術已經進入公有領域。
對於具有均勻概率分布的一組符號，以及作為2的冪之成員，霍夫曼編碼等同於簡單的二進位制編碼，例如 ASCII 編碼。這反映了如此的事實：無論壓縮方法是什麼，這種輸入都不可能進行壓縮，或只是說對資料無所作為，比起壓縮才是才是最佳選擇。
在任何情況下，霍夫曼編碼在所有方法中是最佳的方式，其中每個輸入符號是具有二元機率的已知獨立且相同分布的隨機變數。前綴碼，特別是霍夫曼編碼，往往在小字母表上產生較差的效率，其中概率通常落在這些最佳（二元）點之間。當最可能符號的概率遠超過0.5時，可能發生霍夫曼編碼的最壞情況，使低效率的上限無限制。
在使用霍夫曼編碼的同時，有兩種相關的方法可以解決這種特定的低效問題。將固定數量的符號組合在一起（阻塞）通常會增加（並且永不減少）壓縮。隨著塊的大小接近無窮大，霍夫曼編碼理論上接近熵限制，即最佳壓縮。然而，阻塞任意大的符號組是不切實際的，因為霍夫曼程式碼的複雜性在要編碼的可能性的數量上是線性的，這是在塊的大小中呈指數的數字。這限制了在實踐中完成的阻塞量。
廣泛使用的實際替代方案是行程編碼。該技術在熵編碼之前增加一步，特別是對重複符號進行執行次數的計數，然後對其進行編碼。對於伯努力（Bernoulli）過程的簡單情況，哥倫（Golomb）編碼在編碼遊程長度的前綴碼中是最佳的，這是通過霍夫曼編碼技術證明的事實。使用改進的霍夫曼編碼的傳真機採用類似的方法。但是，遊程編碼並不像其他壓縮技術那樣適應許多輸入類型。

變化

霍夫曼編碼有衍生出許多的許多變化，其中一些使用類似霍夫曼的演算法，而其他一些演算法找到最佳前綴碼（例如，對輸出施加不同的限制）。注意，在後一種情況下，該方法不需要像霍夫曼那樣，實際上甚至不需要到多項式複雜度。

多元樹霍夫曼編碼

多元樹霍夫曼編碼演算法使用 {0, 1, ... , n − 1} 字母來編碼訊息並構建一個多元樹。霍夫曼在他的原始論文中考慮了這種方法。對於二進制（n=2）程式碼應用相同的演算法，除了n個最不可能的符號被一起使用，而不是僅2個最不可能的符號。注意，對於大於2的n，並非所有源字集都可以正確地形成用於霍夫曼編碼的多元樹。在這些情況下，必須添加額外的0概率佔位符。這是因為樹必須形成一個n到1的承包商;對於二進制編碼，這是一個2比1的承包商，任何大小的集合都可以形成這樣的承包商。如果源字的數量與1模n-1一致，則源字集將形成適當的霍夫曼樹。

自適應霍夫曼編碼

自適應霍夫曼編碼的變化，涉及基於源符號序列中的最近實際頻率動態地計算概率，以及改變編碼樹結構以符合更新的概率估計。它在實踐中很少使用，因為更新樹的成本使其比最佳化的自適應算術編碼慢，後者更靈活並且具有更好的壓縮。

霍夫曼模板演算法

在霍夫曼編碼的實現中，通常會使用權重表示數值概率，但是上面給出的演算法不需要這樣;它只需要權重形成一個完全有序的可交換么半群，這意味著一種訂購權重和添加權重的方法。霍夫曼模板演算法使人們能夠使用任何類型的權重（成本，頻率，權重對，非數字權重）和許多組合方法之一（不僅僅是加法），這個問題首先應用於電路設計。

長度限制霍夫曼編碼

長度受限的霍夫曼編碼是一種變體，其目標仍然是實現最小加權路徑長度，但是存在另外的限制，即每個碼字的長度必須小於給定常數。包合併演算法通過一種與霍夫曼演算法非常相似的簡單貪婪方法解決了這個問題。

不相等成本霍夫曼編碼

在標準的霍夫曼編碼問題中，假設集合中構成碼字的每個符號具有相同的傳輸成本：長度為N位的碼字總是具有N的成本，無論多少這些數字是0，有多少是1，等等。在這個假設下工作時，最小化訊息的總成本和最小化數字總數是相同的。
具有不等字母成本的霍夫曼編碼是沒有這種假設的概括：由於傳輸介質的特性，編碼字母表的字母可能具有不均勻的長度。一個例子是摩爾斯電碼的編碼字母表，其中'破折號'比'點'需要更長的發送時間，因此傳輸時間中破折號的成本更高。目標仍然是最小化加權平均碼字長度，但僅僅最小化訊息使用的符號數量已經不夠了。沒有演算法以與傳統霍夫曼編碼相同的方式或相同的效率來解決這個問題，儘管它已經由卡普（Karp）解決，其解決方案已經針對哥林（Golin）的整數成本的情況進行了改進。

最佳字母二元樹

在標準霍夫曼編碼問題中，假設任何碼字可以對應於任何輸入符號。在字母表中，輸入和輸出的字母順序必須相同。

規範霍夫曼編碼

如果對應於按字母順序排列的輸入的權重是按數字順序排列的，則霍夫曼程式碼具有與最佳字母程式碼相同的長度，這可以從計算這些長度中找到，從而不需要使用胡 - 塔克（Hu-Tucker）編碼。由數字（重新）有序輸入產生的程式碼有時被稱為規範霍夫曼程式碼，並且由於易於編碼/解碼，通常是實踐中使用的程式碼。用於找到該程式碼的技術有時被稱為霍夫曼 - 香農 - 法諾編碼，因為它像霍夫曼編碼一樣是最優的，但是在重量概率上是字母的，例如香農 - 法諾編碼。

示範程式

1 // 以下為C++程式碼，在G++下編譯通過 2 // 僅用於示範如何根據權值建構霍夫曼樹， 3 // 沒有經過性能上的優化及加上完善的異常處理。 4 #include <cstdlib> 5 #include <iostream> 6 #include <deque> 7 #include <algorithm> 8  9 using namespace std;10 11 const int size = 10;12 struct node {                               // 霍夫曼樹節點結構13     unsigned key;                           // 保存權值14     node *lchild;                           // 左孩子指針15     node *rchild;                           // 右孩子指針16 };17 deque<node *> forest;18 deque<bool> code;                           // 此處也可使用bitset19 node *ptr;20 int frequency[size] = {0};21 22 void printCode(deque<bool> ptr);            // 用於輸出霍夫曼編碼23 24 bool compare( node *a, node *b) {25     return a->key < b->key;26 }27 int main(int argc, char *argv[]) {28     for (int i = 0; i < size; i++) {29         cin >> frequency[i];                // 輸入10個權值30         ptr = new node;31         ptr->key = frequency[i];32         ptr->lchild = NULL;33         ptr->rchild = NULL;34         forest.push_back(ptr);35     } // 形成森林，森林中的每一棵樹都是一個節點36     // 從森林構建霍夫曼樹37     for (int i = 0; i < size - 1; i++) {38         sort(forest.begin(), forest.end(), compare);39         ptr = new node;40         // 以下代碼使用下標索引隊列元素，具有潛在危險，使用時請注意41         ptr->key = forest[0]->key + forest[1]->key;42         ptr->lchild = forest[0];43         ptr->rchild = forest[1];44         forest.pop_front();45         forest.pop_front();46         forest.push_back(ptr);47     }48     ptr = forest.front(); // ptr是一個指向根的指針49     system("PAUSE");50     return EXIT_SUCCESS;51 }52 53 void printCode(deque<bool> ptr) {54     // deque<bool>55     for (int i = 0; i < ptr.size(); i++) {56         if (ptr[i])57             cout << "1";58         else59             cout << "0";60     }61 }