哈夫曼樹

基本概念

最優二叉樹，也稱哈夫曼（Haffman）樹，是指對于一組帶有确定權值的葉結點，構造的具有最小帶權路徑長度的二叉樹。

那麼什麼是二叉樹的帶權路徑長度呢？nn在前面我們介紹過路徑和結點的路徑長度的概念，而二叉樹的路徑長度則是指由根結點到所有葉結點的路徑長度之和。如果二叉樹中的葉結點都具有一定的權值，則可将這一概念加以推廣。

由此可見，由相同權值的一組葉子結點所構成的二叉樹有不同的形态和不同的帶權路徑長度，那麼如何找到帶權路徑長度最小的二叉樹（即哈夫曼樹）呢？根據哈夫曼樹的定義，一棵二叉樹要使其WPL 值最小，必須使權值越大的葉結點越靠近根結點，而權值越小的葉結點越遠離根結點。哈夫曼（Haffman）依據這一特點提出了一種方法，這種方法的基本思想是：n（1）由給定的n 個權值{W1，W2，…，Wn}構造n 棵隻有一個葉結點的二叉樹，從而得到一個二叉樹的集合F＝{T1，T2，…，Tn}；n（2）在F 中選取根結點的權值最小和次小的兩棵二叉樹作為左、右子樹構造一棵新的二叉樹，這棵新的二叉樹根結點的權值為其左、右子樹根結點權值之和；n（3）在集合F 中删除作為左、右子樹的兩棵二叉樹，并将新建立的二叉樹加入到集合F 中；n（4）重複（2）（3）兩步，當F 中隻剩下一棵二叉樹時，這棵二叉樹便是所要建立的哈夫曼樹。

簡介

在計算機數據處理中，哈夫曼編碼使用變長編碼表對源符号（如文件中的一個字母）進行編碼，其中變長編碼表是通過一種評估來源符号出現機率的方法得到的，出現機率高的字母使用較短的編碼，反之出現機率低的則使用較長的編碼，這便使編碼之後的字符串的平均長度、期望值降低，從而達到無損壓縮數據的目的。

例如，在英文中，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）中發表了這個編碼方法。

構造

假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。 n個權值分别設為 w1、w2、…、wn，則哈夫曼樹的構造規則為：

(1) 将w1、w2、…，wn看成是有n 棵樹的森林(每棵樹僅有一個結點)；

(2) 在森林中選出兩個根結點的權值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；

(3)從森林中删除選取的兩棵樹，并将新樹加入森林；

(4)重複(2)、(3)步，直到森林中隻剩一棵樹為止，該樹即為所求得的哈夫曼樹。

多叉哈夫曼樹

哈夫曼樹也可以是k叉的，隻是在構造k叉哈夫曼樹時需要先進行一些調整。構造哈夫曼樹的思想是每次選k個權重最小的元素來合成一個新的元素，該元素權重為k個元素權重之和。但是當k大于2時，按照這個步驟做下去可能到最後剩下的元素少于k個。解決這個問題的辦法是假設已經有了一棵哈夫曼樹(且為一棵滿k叉樹)，則可以計算出其葉節點數目為(k-1)nk+1,式子中的nk表示子節點數目為k的節點數目。于是對給定的n個權值構造k叉哈夫曼樹時,可以先考慮增加一些權值為0的葉子節點，使得葉子節點總數為(k-1)nk+1這種形式,然後再按照哈夫曼樹的方法進行構造即可。

實現方法

數據壓縮

實現哈夫曼編碼的方式主要是創建一個二叉樹和其節點。這些樹的節點可以存儲在數組裡，數組的大小為符号（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（min（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"，所以還原時一定要考慮何時停止，不要還原到錯誤的值，如在數據壓縮時時加上每筆數據的長度等。

相關應用

哈夫曼編碼

在數據通信中，需要将傳送的文字轉換成二進制的字符串，用0，1碼的不同排列來表示字符。例如，需傳送的報文為“AFTER DATA EAR ARE ART AREA”，這裡用到的字符集為“A，E，R，T，F，D”，各字母出現的次數為{8，4，5，3，1，1}。現要求為這些字母設計編碼。要區别6個字母，最簡單的二進制編碼方式是等長編碼，固定采用3位二進制，可分别用000、001、010、011、100、101對“A，E，R，T，F，D”進行編碼發送，當對方接收報文時再按照三位一分進行譯碼。顯然編碼的長度取決報文中不同字符的個數。若報文中可能出現26個不同字符，則固定編碼長度為5。然而，傳送報文時總是希望總長度盡可能短。在實際應用中，各個字符的出現頻度或使用次數是不相同的，如A、B、C的使用頻率遠遠高于X、Y、Z，自然會想到設計編碼時，讓使用頻率高的用短碼，使用頻率低的用長碼，以優化整個報文編碼。

為使不等長編碼為前綴編碼(即要求一個字符的編碼不能是另一個字符編碼的前綴)，可用字符集中的每個字符作為葉子結點生成一棵編碼二叉樹，為了獲得傳送報文的最短長度，可将每個字符的出現頻率作為字符結點的權值賦予該結點上，求出此樹的最小帶權路徑長度就等于求出了傳送報文的最短長度。因此，求傳送報文的最短長度問題轉化為求由字符集中的所有字符作為葉子結點，由字符出現頻率作為其權值所産生的哈夫曼樹的問題。利用哈夫曼樹來設計二進制的前綴編碼，既滿足前綴編碼的條件，又保證報文編碼總長最短。

哈夫曼靜态編碼：

它對需要編碼的數據進行兩遍掃描：第一遍統計原數據中各字符出現的頻率，利用得到的頻率值創建哈夫曼樹，并必須把樹的信息保存起來，即把字符0-255(2^8=256)的頻率值以2-4BYTES的長度順序存儲起來，（用4Bytes的長度存儲頻率值，頻率值的表示範圍為0--2^32-1，這已足夠表示大文件中字符出現的頻率了）以便解壓時創建同樣的哈夫曼樹進行解壓；第二遍則根據第一遍掃描得到的哈夫曼樹進行編碼，并把編碼後得到的碼字存儲起來。 

哈夫曼動态編碼：

動态哈夫曼編碼使用一棵動态變化的哈夫曼樹，對第t+1個字符的編碼是根據原始數據中前t個字符得到的哈夫曼樹來進行的，編碼和解碼使用相同的初始哈夫曼樹，每處理完一個字符，編碼和解碼使用相同的方法修改哈夫曼樹，所以沒有必要為解碼而保存哈夫曼樹的信息。編碼和解碼一個字符所需的時間與該字符的編碼長度成正比，所以動态哈夫曼編碼可實時進行。 

哈夫曼譯碼

在通信中，若将字符用哈夫曼編碼形式發送出去，對方接收到編碼後，将編碼還原成字符的過程，稱為哈夫曼譯碼。

程序實現

Basic

VERSION 1.0 CLASS

BEGIN

MultiUse = -1 'True

Persistable = 0 'NotPersistable

DataBindingBehavior = 0 'vbNone

DataSourceBehavior = 0 'vbNone

MTSTransactionMode = 0 'NotAnMTSObject

END

Attribute VB_Name = "clsBinTree"

Attribute VB_GlobalNameSpace = False

Attribute VB_Creatable = True

Attribute VB_PredeclaredId = False

Attribute VB_Exposed = False

Private Type BinTreeType

LChild As Integer

RChild As Integer

Parents As Integer

Power As Long

End Type

Private BinTree() As BinTreeType

Public UB As Integer

Public Sub InitData(Power As Long, LChild As Integer, RChild As Integer)

If UB = 0 Then UB = 1

ReDim Preserve BinTree(1 To UB)

BinTree(UB).Power = Power

BinTree(UB).LChild = LChild

BinTree(UB).RChild = RChild

UB = UB + 1

End Sub

Private Sub Min(Min1 As Integer, Min2 As Integer, ErrTag As Integer)

Dim P As Integer, Q As Integer

P = 1

While BinTree(P).Parents > 0

P = P + 1

Wend

For I = P + 1 To UB - 1

If BinTree(I).Power < BinTree(P).Power And BinTree(I).Parents = 0 Then P = I

Next

Q = 1

While BinTree(Q).Parents > 0 Or Q = P

Q = Q + 1

If Q = UB Then

ErrTag = 1

Exit Sub

End If

Wend

For I = Q + 1 To UB - 1

If BinTree(I).Power < BinTree(Q).Power And Q <> P And BinTree(I).Parents = 0 Then Q = I

Next

Min1 = P: Min2 = Q: ErrTag = 0

End Sub

Public Sub Huffman()

Dim ErrorHappen As Integer

Dim Min1 As Integer, Min2 As Integer

Dim I As Integer

Min Min1, Min2, ErrorHappen

Do Until ErrorHappen

InitData BinTree(Min1).Power + BinTree(Min2).Power, Min1, Min2

BinTree(Min1).Parents = UB - 1

BinTree(Min2).Parents = UB - 1

Min Min1, Min2, ErrorHappen

Loop

End Sub

Public Function HuffmanCode(I As Integer) As String

HuffmanCode = I & ", LChild:" & BinTree(I).LChild & " RChild:" & BinTree(I).RChild & " Parents:" & BinTree(I).Parents & " Power:" & BinTree(I).Power

End Function

Attribute VB_Name = "Module1"

Public HT As New clsBinTree

Private Word As String, Ping() As Integer, PUB As Integer

Public Sub CreatHT(Words As String)

Dim Temp As String, I As Integer

Word = ""

For I = 1 To Len(Words)

Temp = Mid(Words, I, 1)

P = InStr(1, Word, Temp)

If P > 0 Then

Ping(P - 1) = Ping(P - 1) + 1

Else

Word = Word & Temp

ReDim Preserve Ping(PUB)

Ping(PUB) = 1

PUB = PUB + 1

End If

Next

Form1.Text2.SelText = Word & vbCrLf

For I = 0 To PUB - 1

Form1.Text2.SelText = Ping(I) & ","

HT.InitData CLng(Ping(I)), 0, 0

Next

Form1.Text2.SelText = vbCrLf & vbCrLf

HT.Huffman

For I = 1 To HT.UB - 1

Form1.Text2.SelText = HT.HuffmanCode(I) & vbCrLf

Next

End Sub

Pascal

Program huffman_tree(input,output);

const max=32767;n=20;m=2*n-1

Type tnode=RECORD

data:integer;

Lc,Rc:integer;

END;

Var tree:ARRAY[0..m] of tnode;

weight:ARRAY[0..n] of integer;

im,num:integer;

procedure initial;

var i:integer;

begin

write('First input nun(<',n:2,')');

readln(num);

writeln('Please input weight:');

for i:=0 to num-1 do read(weight[i])

end;

function minimum:integer;

var i:integer;

begin

min:=max;

for i:=0 to num-1 do

if (min>weight[i]) then

begin

min:=weight[i];

im:=i;

end;

weight[im]:=max;

minimum:=min;

end;

procedure huffman;

var i,k:integer;

begin

for i:=num to 2*num-1 do

begin

tree[i].Lc:=minimum;

tree[i].Rc:=minimum;

tree[i].data:=tree[i].Lc:+tree[i].Rc;

weight[im]:=tree[i].data

end;

writeln;

writeln('The result of huffman tree:');

k:=1;

for i:=2*num-2 downto num do

begin

write(tree[i].data:6,':',tree[i].Lc:3,tree[i].Rc:3);

if (k mod 3=0) then writeln; k:=k+1;

end

writeln

end;

procedure printd;

var i:integer;

begin

write('The weight of tree:');

for i:=0 to num-1 do

write{weight[i]:3}

end;

begin {main}

initial;

printd;

huffman

end.

C++

#include

#include

using namespace std;

const int MaxValue = 10000; //初始設定的權值最大值

const int MaxBit = 4; //初始設定的最大編碼位數

const int MaxN = 10; //初始設定的最大結點個數

struct HaffNode //哈夫曼樹的結點結構

{

int weight; //權值

int flag; //标記

int parent; //雙親結點下标

int leftChild; //左孩子下标

int rightChild; //右孩子下标

};

struct Code //存放哈夫曼編碼的數據元素結構

{

int bit[MaxN]; //數組

int start; //編碼的起始下标

int weight; //字符的權值

};

void Haffman(int weight[], int n, HaffNode haffTree[])

//建立葉結點個數為n權值為weight的哈夫曼樹haffTree

{

int j, m1, m2, x1, x2;

//哈夫曼樹haffTree初始化。n個葉結點的哈夫曼樹共有2n-1個結點

for(int i = 0; i < 2 * n - 1 ; i++)

{

if(i < n)

haffTree[i].weight = weight[i];

else haffTree[i].weight = 0;

haffTree[i].parent = 0;

haffTree[i].flag = 0;

haffTree[i].leftChild = -1;

haffTree[i].rightChild = -1;

}

//構造哈夫曼樹haffTree的n-1個非葉結點

for(int i = 0;i < n-1;i++)

{

m1 = m2 = MaxValue;

x1 = x2 = 0;

for(j = 0; j < n+i;j++)

{

if (haffTree[j].weight < m1 && haffTree[j].flag == 0)

{

m2 = m1;

x2 = x1;

m1 = haffTree[j].weight;

x1 = j;

}

else

if(haffTree[j].weight < m2 && haffTree[j].flag == 0)

{

m2 = haffTree[j].weight;

x2 = j;

}

}

//将找出的兩棵權值最小的子樹合并為一棵子樹

haffTree[x1].parent = n+i;

haffTree[x2].parent = n+i;

haffTree[x1].flag = 1;

haffTree[x2].flag = 1;

haffTree[n+i].weight = haffTree[x1].weight+haffTree[x2].weight;

haffTree[n+i].leftChild = x1;

haffTree[n+i].rightChild = x2;

}

}

void HaffmanCode(HaffNode haffTree[], int n, Code haffCode[])

//由n個結點的哈夫曼樹haffTree構造哈夫曼編碼haffCode

{

Code *cd = new Code;

int child, parent;

//求n個葉結點的哈夫曼編碼

for(int i = 0; i < n; i++)

{

cd->start = n-1; //不等長編碼的最後一位為n-1

cd->weight = haffTree[i].weight; //取得編碼對應權值的字符

child = i;

parent = haffTree[child].parent;

//由葉結點向上直到根結點

while(parent != 0)

{

if(haffTree[parent].leftChild == child)

cd->bit[cd->start] = 0; //左孩子結點編碼0

else

cd->bit[cd->start] = 1;//右孩子結點編碼1

cd->start--;

child = parent;

parent = haffTree[child].parent;

}

//保存葉結點的編碼和不等長編碼的起始位

for(int j = cd->start+1; j < n; j++)

haffCode[i].bit[j] = cd->bit[j];

haffCode[i].start = cd->start;

haffCode[i].weight = cd->weight; //保存編碼對應的權值

}

}

int main()

{

int i, j, n = 4;

int weight[] = {1,3,5,7};

HaffNode *myHaffTree = new HaffNode[2*n+1];

Code *myHaffCode = new Code[n];

if(n > MaxN)

{

cout << "定義的n越界，修改MaxN! " << endl;

exit(0);

}

Haffman(weight, n, myHaffTree);

HaffmanCode(myHaffTree, n, myHaffCode);

//輸出每個葉結點的哈夫曼編碼

for(i = 0; i < n; i++)

{

cout << "Weight = " << myHaffCode[i].weight << " Code = ";

for(j = myHaffCode[i].start+1; j < n; j++)

cout << myHaffCode[i].bit[j];

cout << endl;

}

return 0;

}

C

#include

#include

#define N 8

typedef struct node{

int item;

struct node* l;

struct node* r;

}* link;

link *h;

int Nq = N;

link NODE(int item, link l, link r)

{

link t = malloc(sizeof *t);

t->l = l;

t->r = r;

t->item = item;

return t;

}

void shif_up(int i)

{

int j;

while(i > 1)

{

j = i/2;

if()

}

}

void insert(link t)

{

h[++Nq] = t;

shif_up(Nq);

}

link delmin()

{

swap(1, Nq--);

shif_down(1,Nq);

return h[Nq+1];

}

link creat_heap(int freq, int len)

{

int i;

for(i = 0; i < len; i++)

h[i] = NODE(freq[i], NULL, NULL);

for(i = N/2; i >= 0; i--)

shif_down(i, N);}

void huffman(int freq[], int len)

{

h = malloc(len * sizeof(link));

creat_heap(h, freq, len);

while(Nq > 1)

{

link t1 = delmin();

link t2 = delmin();

insert(NODE(t1->item + t2->item, t1, t2));

}

}

int main(void)

{

int freq[N] = {5, 29, 7, 8, 14, 23, 3, 11};

huffman(freq, N);

return 0;

}