霍夫曼编码
| 字母 | 頻率 | 編碼 |
|---|---|---|
| space | 7 | 111 |
| a | 4 | 010 |
| e | 4 | 000 |
| f | 3 | 1101 |
| h | 2 | 1010 |
| i | 2 | 1000 |
| m | 2 | 0111 |
| n | 2 | 0010 |
| s | 2 | 1011 |
| t | 2 | 0110 |
| l | 1 | 11001 |
| o | 1 | 00110 |
| p | 1 | 10011 |
| r | 1 | 11000 |
| u | 1 | 00111 |
| x | 1 | 10010 |
霍夫曼編碼（Huffman Coding）是一種編碼方式，是一種用於無損數據壓縮的熵編碼（權編碼）演算法。1952年，David A. Huffman在麻省理工攻讀博士時所發明的，並發表於《一種構建極小多餘編碼的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文。
在计算机資料處理中，霍夫曼編碼使用變長編碼表對源符號（如文件中的一個字母）進行編碼，其中變長編碼表是通過一種評估來源符號出現機率的方法得到的，出現機率高的字母使用較短的編碼，反之出現機率低的則使用較長的編碼，這便使編碼之後的字符串的平均長度、期望值降低，從而達到無損壓縮數據的目的。
例如，在英文中，e的出現機率最高，而z的出現概率則最低。當利用霍夫曼編碼對一篇英文進行壓縮時，e極有可能用一個位元來表示，而z則可能花去25個位元（不是26）。用普通的表示方法時，每個英文字母均占用一個字節（byte），即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 M. Fano給他們的學期報告的題目是，尋找最有效的二進制編碼。由於無法證明哪個已有編碼是最有效的，霍夫曼放棄對已有編碼的研究，轉向新的探索，最終發現了基於有序頻率二叉樹編碼的想法，並很快證明了這個方法是最有效的。
由於這個算法，學生终于青出於藍，超過了他那曾經和信息論創立者克劳德·香农共同研究過類似編碼的導師。霍夫曼使用自底向上的方法構建二叉樹，避免了次優算法Shannon-Fano編碼的最大弊端──自頂向下構建樹。
[编辑] 示範程式
//以下為C++程式碼，在GCC下編譯通過 //僅用於示範如何根據權值構建霍夫曼樹， //沒有經過性能上的優化及加上完善的異常處理。 #include <cstdlib> #include <iostream> #include <deque> #include <algorithm> using namespace std; const int size=10; struct node //霍夫曼樹節點結構 { unsigned key; //保存權值 node* lchild; //左孩子指針 node* rchild; //右孩子指針 }; deque<node*> forest; deque<bool> code; //此處也可使用bitset node* ptr; int frequency[size]={0}; void printCode(deque<bool> ptr); //用於輸出霍夫曼編碼 bool compare( node* a, node* b) { return a->key < b->key; } int main(int argc, char *argv[]) { for (int i=0;i<size;i++) { cin>>frequency[i]; //輸入10個權值 ptr=new node; ptr->key=frequency[i]; ptr->lchild=NULL; ptr->rchild=NULL; forest.push_back(ptr); }//形成森林，森林中的每一棵樹都是一個節點 //從森林構建霍夫曼樹 for (int i=0;i<size-1;i++) { sort(forest.begin(),forest.end(),compare); ptr=new node; //以下代碼使用下標索引隊列元素，具有潛在危險，使用時請注意 ptr->key=forest[0]->key+forest[1]->key; ptr->lchild=forest[0]; ptr->rchild=forest[1]; forest.pop_front(); forest.pop_front(); forest.push_back(ptr); } ptr=forest.front();//ptr是一個指向根的指針 system("PAUSE"); return EXIT_SUCCESS; } void printCode(deque<bool> ptr) { //deque<bool> for (int i=0;i<ptr.size();i++) { if(ptr[i]) cout<<"1"; else cout<<"0"; } }
[编辑] 外部連結
- 有關哈夫曼壓縮技術的原文：D.A. Huffman, "A method for the construction of minimum-redundancy codes", Proceedings of the I.R.E., sept 1952, pp 1098-1102
- 哈夫曼树图形演示
- Animation of the Huffman Algorithm: Algorithm Simulation by Simon Mescal
- Background story: Profile: David A. Huffman, Scientific American, Sept. 1991, pp. 54-58
- n-ary Huffman Template Algorithm
- Huffman codes' connection with Fibonacci and Lucas numbers
- Fibonacci connection between Huffman codes and Wythoff array
- Sloane A098950 Minimizing k-ordered sequences of maximum height Huffman tree
- Computing Huffman codes on a Turing Machine
- Mordecai J. Golin, Claire Kenyon, Neal E. Young "Huffman coding with unequal letter costs", STOC 2002: 785-791
- Huffman Coding, implemented in python
|
||||||||||||||||||||||||||||||||||||||||||||||||||||
