霍夫曼編碼是一種被廣泛應(yīng)用而且非常有效的數(shù)據(jù)壓縮技術(shù)，根據(jù)待壓縮數(shù)據(jù)的特征，一個可壓縮掉20%~90%。這里考慮的數(shù)據(jù)指的是字符串序列。要理解霍夫曼編碼，先要理解霍夫曼樹，即最優(yōu)二叉樹，是一類帶權(quán)路徑長度最短的樹。
路徑是指從樹中一個結(jié)點到另一個結(jié)點之間的通路，路徑上的分支數(shù)目稱為路徑長度。
樹的路徑長度是從樹根到每一個葉子之間的路徑長度之和。結(jié)點的帶權(quán)路徑長度為從該結(jié)點到樹根之間的路徑長度與該結(jié)點權(quán)的乘積，樹的帶權(quán)路徑長度為樹中所有葉子結(jié)點的帶權(quán)路徑長度之和.
霍夫曼樹是指所有葉子結(jié)點的二叉樹中帶權(quán)路徑長度最小的二叉樹.
當給定了n個葉子結(jié)點的權(quán)值后，構(gòu)造出的最優(yōu)二叉樹的結(jié)點數(shù)目m就確定了，即m=2n-1,所以可用一維結(jié)構(gòu)數(shù)組來存儲最優(yōu)二叉樹
#define MAXLEAFNUM 50 /*最優(yōu)二叉樹中最大葉子樹目*/
struct node{
char ch; /*當前結(jié)點表示的字符，對于非葉子結(jié)點，此域不用*/
int weight; /*當前結(jié)點的權(quán)值*/
int parent; /*當前結(jié)點的父結(jié)點的下標，為0時表示無父結(jié)點*/
int lchild,rchild; /*當前結(jié)點的左，右孩子結(jié)點的下標，為0時表示無孩子結(jié)點*/
}HuffmanTree[2 * MAXLEAFNUM];
typedef char *HuffmanCode[MAXLEAFNUM + 1]；
/*創(chuàng)建最優(yōu)二叉樹*/
void createHTree(HuffmanTree HT, char *c, int *w, int n)
{
/*數(shù)組c[0..n-1]和w[0..n-1]存放了n個字符及其概率，構(gòu)造霍夫樹HT*/
int i, s1, s2;
if (n <= 1)
return;
/*根據(jù)n個權(quán)值構(gòu)造n棵只有根結(jié)點的二叉樹*/
for (i=1; i<=n; i++)
{
HT[i].ch = c[i-1];
HT[i].weight = w[i-1];
HT[i].parent = HT[i].lchild = HT[i].rchild = 0;
}
for (; i<2*n; ++i)
{
HT[i].parent = 0;
HT[i].lchild = 0;
HT[i].rchild = 0;
}
/*構(gòu)造霍夫曼樹*/
for (i=n+1; i<2*n; i++)
{
/*從HT[1..i-1]中選擇parent為0且weight最小的兩棵樹，其序號為s1和s2*/
select(HT,i-1,s1,s2);
HT[s1].parent = i;
HT[s2].parent = i;
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
}
復(fù)制代碼
霍夫曼算法(構(gòu)造靍夫曼樹)
對應(yīng)于霍夫曼樹的算法也叫做霍夫曼算法。此算法的思想是：
（1）設(shè)給定的一組權(quán)值為{W1，W2，W3，……Wn}，據(jù)此生成森林F={T1，T2，T3，……Tn},F 中的每棵二叉樹只有一個帶權(quán)為W1的根節(jié)點（i=1，2，……n）。
（2）在F中選取兩棵根節(jié)點的權(quán)值最小和次小的二叉樹作為左右構(gòu)造一棵新的二叉樹，新二叉樹根節(jié)點的權(quán)值為其左、右子樹根節(jié)點的權(quán)值之和。
（3）在F中刪除這兩棵最小和次小的二叉樹，同時將新生成的二叉樹并入森林中。
（4）重復(fù)（2）（3）過程直到F中只有一棵二叉樹為止。
霍夫曼樹的應(yīng)用非常廣，在不同的應(yīng)用中葉子節(jié)點的權(quán)值可以作不同的解釋。霍夫曼樹應(yīng)用于信息編碼中，權(quán)值可以看成某個符號出現(xiàn)的頻率；應(yīng)用到判定過程中，權(quán)值可以看成某類數(shù)據(jù)出現(xiàn)的頻率；應(yīng)用到排序過程中，權(quán)值可以看成是已排好次序而等待合并的序列長度等。
應(yīng)用霍夫曼編碼
假設(shè)有一個包含100 000個字符的數(shù)據(jù)文件要壓縮存儲。各字符在該文件中的出現(xiàn)頻度見表1。僅有6種不同字符出現(xiàn)過，字符a出現(xiàn)了45000次。
a b c d e f
頻度（千字） 45 13 12 16 9 5
固定代碼字 000 001 010 011 100 101
變長代碼字 0 101 100 111 1101 1100
表1 一個字符編碼問題。大小為100 000個字符的一個數(shù)據(jù)文件僅包含字符a~f，每個字符出現(xiàn)的頻度如表中所示。如果對每個字符賦予一個三位的編碼，則該文件可被編碼為300000位。如果利用表中的可變長度編碼，該文件可被編碼為224000位。
可以用很多種方式來表示這樣一個文件。采用固定長度編碼，則需要三位二進制數(shù)字來表示六個字符：a=000，b=001，…，f=101。這種方法需要300 000來對整個原文件編碼。