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