哈夫曼树

基本概念

最优二叉树，也称哈夫曼（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;

}