霍夫曼编码

维基百科,自由的百科全书
(重定向自哈夫曼树
跳转至: 导航搜索
這個句子“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給他們的學期報告的題目是,尋找最有效的二進制編碼。由於無法證明哪個已有編碼是最有效的,霍夫曼放棄對已有編碼的研究,轉向新的探索,最終發現了基於有序頻率二叉樹編碼的想法,並很快證明了這個方法是最有效的。

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

問題定義與解法[编辑]

Fig.1
Fig.2霍夫曼編碼演算步驟, 错误:"7-T"应在"8-R-G"的左边生成树
Fig.3

廣義[编辑]

  • 給定
一組符號(Symbol)和其對應的權重值(weight),其權重通常表示成機率(%)。


  • 欲知
一組二元的前置碼,其二元碼的長度為最短。

狹義[编辑]


  • 輸入
符號集合S = \left\{s_{1},s_{2},\cdots,s_{n}\right\},其S集合的大小為n
權重集合W = \left\{w_{1},w_{2},\cdots,w_{n}\right\},其W集合不為負數且w_{i} = \mathrm{weight}\left(s_{i}\right), 1\leq i \leq n


  • 輸出
一組編碼C \left(S,W\right) = \left\{c_{1},c_{2},\cdots,c_{n}\right\},其C集合是一組二進制編碼且c_{i}s_{i}相對應的編碼,1\leq i \leq n


  • 目標
L \left(C\right) = \sum_{i=1}^{n}{w_{i}\times\mathrm{length}\left(c_{i}\right)}C的加權的路徑長,對所有編碼T \left(S,W\right),則L\left(C\right) \leq L\left(T\right)

範例[编辑]


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

演算過程[编辑]

(一)進行霍夫曼編碼前,我們先建立一個霍夫曼樹。

⒈將每個英文字母依照出現頻率由小排到大,最小在左,如Fig.1
⒉每個字母都代表一個終端節點(葉節點),比較F.O.R.G.E.T五個字母中每個字母的出現頻率,將最小的兩個字母頻率相加合成一個新的節點。如Fig.2所示,發現FO的頻率最小,故相加2+3=5。
⒊比較5.R.G.E.T,發現RG的頻率最小,故相加4+4=8。
⒋比較5.8.E.T,發現5E的頻率最小,故相加5+5=10。
⒌比較8.10.T,發現8T的頻率最小,故相加8+7=15。
⒍最後剩10.15,沒有可以比較的對象,相加10+15=25。


最後產生的樹狀圖就是霍夫曼樹,參考Fig.2

(二)進行編碼

1.給霍夫曼樹的所有左鏈結'0'與右鏈結'1'。
2.從樹根至樹葉依序記錄所有字母的編碼,如Fig.3

實現方法[编辑]

資料壓縮[编辑]


實現霍夫曼編碼的方式主要是創建一個二元樹和其節點。這些樹的節點可以儲存在陣列裡,陣列的大小為符號(symbols)數的大小n,而節點分為是終端節點(葉節點)與非終端節點(內部節點)。
一開始,所有的節點都是終端節點,節點內有三個欄位:

1.符號(Symbol)
2.權重(Weight、Probabilities、Frequency)
3.指向父節點的鏈結(Link to its parent node)

而非終端節點內有四個欄位:

1.權重(Weight、Probabilities、Frequency)
2.指向兩個子節點的 鏈結(Links to two child node)
3.指向父節點的鏈結(Link to its parent node)

基本上,我們用'0'與'1'分別代表指向左子節點與右子節點,最後為完成的二元樹共有n個終端節點與n-1個非終端節點,去除了不必要的符號並產生最佳的編碼長度。

過程中,每個終端節點都包含著一個權重(Weight、Probabilities、Frequency),兩兩終端節點結合會產生一個新節點,新節點的權重是由兩個權重最小的終端節點權重之總和,並持續進行此過程直到只剩下一個節點為止。

實現霍夫曼樹的方式有很多種,可以使用優先佇列(Priority Queue)簡單達成這個過程,給與權重較低的符號較高的優先順序(Priority),演算法如下:

⒈把n個終端節點加入優先佇列,則n個節點都有一個優先權Pi,1 ≤ i ≤ n
⒉如果佇列內的節點數>1,則:

⑴從佇列中移除兩個最大的Pi節點,即連續做兩次remove(max(Pi), Priority_Queue)
⑵產生一個新節點,此節點為(1)之移除節點之父節點,而此節點的權重值為(1)兩節點之權重和
⑶把(2)產生之節點加入優先佇列中

⒊最後在優先佇列裡的點為樹的根節點(root)

而此演算法的時間複雜度( Time Complexity)為O(n log n);因為有n個終端節點,所以樹總共有2n-1個節點,使用優先佇列每個迴圈須O(log n)。
此外,有一個更快的方式使時間複雜度降至線性時間(Linear Time)O(n),就是使用兩個佇列(Queue)創件霍夫曼樹。第一個佇列用來儲存n個符號(即n個終端節點)的權重,第二個佇列用來儲存兩兩權重的合(即非終端節點)。此法可保證第二個佇列的前端(Front)權重永遠都是最小值,且方法如下:

⒈把n個終端節點加入第一個佇列(依照權重大小排列,最小在前端)
⒉如果佇列內的節點數>1,則:

⑴從佇列前端移除兩個最低權重的節點
⑵將(1)中移除的兩個節點權重相加合成一個新節點
⑶加入第二個佇列

⒊最後在第一個佇列的節點為根節點

雖然使用此方法比使用優先佇列的時間複雜度還低,但是注意此法的第1項,節點必須依照權重大小加入佇列中,如果節點加入順序不按大小,則需要經過排序,則至少花了O(n log n)的時間複雜度計算。
但是在不同的狀況考量下,時間複雜度並非是最重要的,如果我們今天考慮英文字母的出現頻率,變數n就是英文字母的26個字母,則使用哪一種演算法時間複雜度都不會影響很大,因為n不是一筆龐大的數字。

資料解壓縮[编辑]


簡單來說,霍夫曼碼樹的解壓縮就是將得到的前置碼(Prefix Huffman code)轉換回符號,通常藉由樹的追蹤(Traversal),將接收到的位元串(Bits stream)一步一步還原。但是要追蹤樹之前,必須要先重建霍夫曼樹 ;某些情況下,如果每個符號的權重可以被事先預測,那麼霍夫曼樹就可以預先重建,並且儲存並重複使用,否則,傳送端必須預先傳送霍夫曼樹的相關資訊給接收端。

最簡單的方式,就是預先統計各符號的權重並加入至壓縮之位元串,但是此法的運算量花費相當大,並不適合實際的應用。若是使用Canonical encoding,則可精準得知樹重建的資料量只占B2^B位元(其中B為每個符號的位元數(bits))。如果簡單將接收到的位元串一個位元一個位元的重建,例如:'0'表示父節點,'1'表示終端節點,若每次讀取到1時,下8個位元則會被解讀是終端節點(假設資料為8-bit字母),則霍夫曼樹則可被重建,以此方法,資料量的大小可能為2~320位元組不等。雖然還有很多方法可以重建霍夫曼樹,但因為壓縮的資料串包含"traling bits",所以還原時一定要考慮何時停止,不要還原到錯誤的值,例如:在資料壓縮時時加上每筆資料的長度等等...。

資料長度[编辑]


設符號集合S = \left\{s_{1},s_{2},\cdots,s_{n}\right\}
P\left(s_{j}\right) :  s_{j}發生的機率
L\left(s_{j}\right) :  s_{j}編碼的長度

  • 熵(Entropy)
entropy = \sum_{j=1}^{J}{ P \left(s_{j}\right)\times\log {1 \over P \left(s_{j}\right)}  } 
  • 霍夫曼碼平均長度
 mean \left(L \right) = \sum_{j=1}^{J}{P \left(s_{j}\right)\times\ L \left(s_{j}\right)} 
  • 霍夫曼碼的長度
Shannon編碼定理: entropy \over logk mean \left(L \right)entropy \over logk + 1   ,若使用k進位的編碼

霍夫曼碼的平均編碼長度:b = mean \left(L \right) N N為資料長度

N entropy \over logkbN entropy \over logk + N  

示範程式[编辑]

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

外部連結[编辑]