霍夫曼编码

维基百科，自由的百科全书
（重定向自哈夫曼树）
跳转至： 导航、 搜索
這個句子“this is an example of a huffman tree”中得到的字母頻率來建構霍夫曼樹。句中字母的編碼和頻率如下。編碼此句子句子需要135 bit（不包括保存树所用的空間）
字母 頻率 編碼
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給他們的學期報告的題目是，尋找最有效的二進制編碼。由於無法證明哪個已有編碼是最有效的，霍夫曼放棄對已有編碼的研究，轉向新的探索，最終發現了基於有序頻率二叉樹編碼的想法，並很快證明了這個方法是最有效的。

由於這個算法，學生终于青出於藍，超過了他那曾經和信息論創立者克劳德·香农共同研究過類似編碼的導師。霍夫曼使用自底向上的方法構建二叉樹，避免了次優算法香農-范諾編碼的最大弊端──自頂向下構建樹。

示範程式 [编辑]

//以下為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";
        }
}

外部連結 [编辑]
无损数据压缩
RLE · LZ77/78 · LZSS · LZW · LZWL · LZO · DEFLATE · LZMA · LZX · LZJB
其他
CTW · BWT · PPMd · DMC
音频
LPC  · WLPC · CELP · ACELP · A-law · μ-law · MDCT · 傅里叶变换 · 音响心理学
其他
图像
条件
方法
其他
视频
条件
其他
率失真理论（CBR · ABR · VBR）
来自“http://zh.wikipedia.org/w/index.php?title=霍夫曼编码&oldid=26275021”