一、Huffman編碼
霍夫曼(Huffman)樹是一類帶權(quán)路徑長度最短的二叉樹樹。Huffman樹的一個(gè)非常重要的應(yīng)用就是進(jìn)行Huffman編碼以得到0-1碼流進(jìn)行快速傳輸。
在電報(bào)收發(fā)等數(shù)據(jù)通訊中，常需要將傳送的文字轉(zhuǎn)換成由二進(jìn)制字符0、1組成的字符串來傳輸。為了使收發(fā)的速度提高，就要求電文編碼要盡可能地短。此外，要設(shè)計(jì)長短不等的編碼，還必須保證任意字符的編碼都不是另一個(gè)字符編碼的前綴，目的是解決譯碼的二義性。
例如：假設(shè)有一電文“EABCBAEDBCEEEDCEBABC”，其中的字符集為C={A，B，C，D，E}，各個(gè)字符出現(xiàn)的次數(shù)集為W={3, 5, 4, 2, 6}。
以字符集C作為葉子結(jié)點(diǎn)，次數(shù)集W作為結(jié)點(diǎn)的權(quán)值來構(gòu)造 Huffman樹，則得到如下的Huffman樹：
其中樹葉結(jié)點(diǎn)就是電文中的字符，樹葉中的數(shù)字就是對(duì)應(yīng)字符出現(xiàn)的次數(shù)。
規(guī)定Huffman樹中左分支代表“0”，右分支代表“1” ，則得到如下的Huffman樹：
從根結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)所經(jīng)歷的路徑分支上的“0”或“1”所組成的字符串，為該結(jié)點(diǎn)所對(duì)應(yīng)的編碼，稱之為Huffman編碼。
各個(gè)字符的Huffman編碼結(jié)果如下：
由于每個(gè)字符都是葉子結(jié)點(diǎn)，不可能出現(xiàn)在根結(jié)點(diǎn)到其它字符結(jié)點(diǎn)的路徑上，所以一個(gè)字符的Huffman編碼不可能是另一個(gè)字符的Huffman編碼的前綴。
二、Huffman編碼算法
1.編碼方式
根據(jù)出現(xiàn)頻度(權(quán)值)Weight，對(duì)葉子結(jié)點(diǎn)的Huffman編碼有兩種方式：
1）從葉子結(jié)點(diǎn)到根逆向處理，求得每個(gè)葉子結(jié)點(diǎn)對(duì)應(yīng)字符的Huffman編碼。
2）從根結(jié)點(diǎn)開始遍歷整棵二叉樹，求得每個(gè)葉子結(jié)點(diǎn)對(duì)應(yīng)字符的Huffman編碼。
2.逆向編碼算法
本文以逆向編碼為例，給出Huffman編碼的算法。
對(duì)于每個(gè)樹葉結(jié)點(diǎn)，其Huffman編碼算法如下：
Step 1：把樹葉作為當(dāng)前結(jié)點(diǎn)，并獲取其序號(hào)（數(shù)組的下標(biāo)）
Step 2：獲取當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)的序號(hào)
Step 3：判斷當(dāng)前結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的左或者右子樹，如果是左，則編碼為’0’，否則為’1’
Step 4：如果雙親結(jié)點(diǎn)為樹根，則結(jié)束當(dāng)前樹葉的編碼；否則，更新當(dāng)前結(jié)點(diǎn)序號(hào)為其雙親的序號(hào)，返回Step 2.
注：因?yàn)槭菑臉淙~開始到樹根的編碼，因此在存儲(chǔ)編碼的時(shí)候是倒序存儲(chǔ)，即把當(dāng)前樹葉編碼的第一個(gè)字符存到數(shù)組的最后位置，然后向前依次存儲(chǔ)。
三、Huffman編碼之C程序
1.Huffman編碼算法
/******************************************************************************************
函數(shù)：void Huff_coding( int WeightNum, HTNode *HT, int NodeNum, char **HC )
功能：對(duì)Huffman樹的葉子結(jié)點(diǎn)進(jìn)行編碼。
說明：Huffman樹的結(jié)點(diǎn)存儲(chǔ)在結(jié)構(gòu)體數(shù)組HT里，其中前面WeightNum個(gè)元素為葉子結(jié)點(diǎn)，存儲(chǔ)給定信息
的權(quán)值。
輸入?yún)?shù)：WeightNum：權(quán)值的個(gè)數(shù)，也就是Huffman樹上葉子結(jié)點(diǎn)的個(gè)數(shù)
NodeNum： Huffman樹上全部結(jié)點(diǎn)的個(gè)數(shù)
HT： 存儲(chǔ)Huffman樹上所有結(jié)點(diǎn)的信息，權(quán)、雙親編號(hào)、左孩子編號(hào)、右孩子編號(hào)
輸出參數(shù)：HC： 存儲(chǔ)樹葉結(jié)點(diǎn)的Huffman編碼，每個(gè)編碼均為一個(gè)字符串
*******************************************************************************************/
void Huff_coding( int WeightNum, HTNode *HT, int NodeNum, char **HC )
{
int k, sp, p, fp;
char *cd;
cd = new char[ WeightNum + 1 ]; // 動(dòng)態(tài)分配存儲(chǔ)編碼的工作空間
cd[ WeightNum ] = '\0'; // 編碼的結(jié)束標(biāo)志
for ( k = 1; k <= WeightNum; k++ ) // 逐個(gè)求字符的編碼
{
sp = WeightNum;
//從葉子結(jié)點(diǎn)到根逆向求編碼
for( p = k, fp = HT[k].Parent; fp != 0; p = fp, fp = HT[p].Parent )
{
if ( HT[fp].Lchild == p )
cd[ --sp ] = '0';
else
cd[ --sp ] = '1';
}
HC[k] = new char[ WeightNum - sp + 1 ]; //為第k個(gè)字符分配空間
strcpy( HC[k], &cd[sp] ) ;
}
delete[] cd ;
}
2.完整的測試代碼文章來源：http://www.zghlxwxcb.cn/news/detail-467396.html
#include"stdio.h"
#include"string.h"
#define MAX_NODE 200 //Max_Node>2n-1
//存儲(chǔ)Huffman樹結(jié)點(diǎn)
typedef struct
{
char Character; //信息字符
int Weight; //權(quán)
int Parent; //雙親結(jié)點(diǎn)編號(hào)
int Lchild; //左孩子結(jié)點(diǎn)編號(hào)
int Rchild; //右孩子結(jié)點(diǎn)編號(hào)
} HTNode ;
//創(chuàng)建一棵葉子結(jié)點(diǎn)數(shù)為WeightNum的Huffman樹,生成Huffman樹后，樹的根結(jié)點(diǎn)的下標(biāo)是2WeightNum-1
void Create_Huffman( int WeightNum, HTNode *HT, int NodeNum );
//對(duì)已經(jīng)創(chuàng)建的huffman樹進(jìn)行編碼
void Huff_coding( int WeightNum, HTNode *HT, int NodeNum, char **HC );
int main()
{
int WeightNum;//已知的權(quán)值的個(gè)數(shù)，也就是葉子結(jié)點(diǎn)個(gè)數(shù)
int NodeNum; //huffman樹上全部結(jié)點(diǎn)個(gè)數(shù)
HTNode *HT; //存儲(chǔ)Huffman樹的結(jié)點(diǎn)
char **HC; //存儲(chǔ)Huffman編碼
WeightNum = 5;
NodeNum = 2 * WeightNum - 1;
//建立Huffman樹
HT = new HTNode[MAX_NODE];
Create_Huffman( WeightNum, HT, NodeNum );
//向屏幕輸出Huffman樹的結(jié)點(diǎn)
printf( "Huffman樹上的結(jié)點(diǎn)：\n" );
int i;
for( i = 1; i <= NodeNum; i++ )
{
if( i <= WeightNum )
printf( "%c %d %d %d %d\n", HT[i].Character, HT[i].Weight, HT[i].Parent, HT[i].Lchild, HT[i].Rchild );
else
printf( "%c %d %d %d %d\n", ' ', HT[i].Weight, HT[i].Parent, HT[i].Lchild, HT[i].Rchild );
}
//Huffman編碼
HC = new char*[ WeightNum + 1];
Huff_coding( WeightNum, HT, NodeNum, HC );
//向屏幕輸出Huffman編碼
printf( "Huffman編碼：\n" );
for( i = 1; i <= WeightNum; i++ )
{
printf( "%c: %s\n", HT[i].Character, HC[i] );
}
delete[] HT;
delete[] HC;
return 0;
}
/******************************************************************************************
函數(shù)：void Create_Huffman( int WeightNum, HTNode *HT, int NodeNum )
功能：對(duì)給定的權(quán)值，生成Huffman樹
說明：Huffman樹的結(jié)點(diǎn)存儲(chǔ)在結(jié)構(gòu)體數(shù)組HT里，其中前面WeightNum個(gè)元素為葉子結(jié)點(diǎn)，存儲(chǔ)給定信息
的權(quán)值。
輸入?yún)?shù)：WeightNum：權(quán)值的個(gè)數(shù)，也就是Huffman樹上葉子結(jié)點(diǎn)的個(gè)數(shù)
NodeNum： Huffman樹上全部結(jié)點(diǎn)的個(gè)數(shù)
輸出參數(shù)：HT： 存儲(chǔ)Huffman樹上所有結(jié)點(diǎn)的信息，權(quán)、雙親編號(hào)、左孩子編號(hào)、右孩子編號(hào)
*******************************************************************************************/
void Create_Huffman( int WeightNum, HTNode *HT, int NodeNum )
{
int k , j; //循環(huán)下標(biāo)
int w1, w2; //w1 , w2分別保存權(quán)值最小的兩個(gè)權(quán)值
int p1, p2; //p1 , p2保存兩個(gè)最小權(quán)值的下標(biāo)
for ( k = 1; k <= NodeNum; k++ ) //step1：初始化向量HT，即所有成員均當(dāng)做樹根
{
if( k <= WeightNum ) //輸入時(shí)，所有葉子結(jié)點(diǎn)都有權(quán)值
{
printf( "Please Input Character : Character =?" );
scanf( "%c", &HT[k].Character );
printf( "Please Input Weight : Weight =?" );
scanf( "%d", &HT[k].Weight );
getchar(); //過濾輸入數(shù)據(jù)時(shí)的換行符
}
else
HT[k].Weight = 0; //非葉子結(jié)點(diǎn)沒有權(quán)值
HT[k].Parent = HT[k].Lchild = HT[k].Rchild = 0 ;
}
for( k = WeightNum + 1; k <= NodeNum; k++ )//step2：對(duì)非葉子節(jié)點(diǎn)賦值，以生成H樹
{
p1 = 0;
p2 = 0;
w1 = 0xFFFFFFF;
w2 = w1;
for( j = 1 ; j <= k-1 ; j++) //找到權(quán)值最小的兩個(gè)值及其下標(biāo)
{
if( HT[j].Parent == 0 ) //尚未合并
{
if( HT[j].Weight < w1 )
{
w2 = w1;
p2 = p1;
w1 = HT[j].Weight;
p1 = j;
}
else if( HT[j].Weight < w2 )
{
w2 = HT[j].Weight;
p2 = j;
}
}
}
HT[k].Lchild = p1;
HT[k].Rchild = p2;
HT[k].Weight = w1 + w2;
HT[p1].Parent = k;
HT[p2].Parent = k;
}
}
/******************************************************************************************
函數(shù)：void Huff_coding( int WeightNum, HTNode *HT, int NodeNum, char **HC )
功能：對(duì)Huffman樹的葉子結(jié)點(diǎn)進(jìn)行編碼。
說明：Huffman樹的結(jié)點(diǎn)存儲(chǔ)在結(jié)構(gòu)體數(shù)組HT里，其中前面WeightNum個(gè)元素為葉子結(jié)點(diǎn)，存儲(chǔ)給定信息
的權(quán)值。
輸入?yún)?shù)：WeightNum：權(quán)值的個(gè)數(shù)，也就是Huffman樹上葉子結(jié)點(diǎn)的個(gè)數(shù)
NodeNum： Huffman樹上全部結(jié)點(diǎn)的個(gè)數(shù)
HT： 存儲(chǔ)Huffman樹上所有結(jié)點(diǎn)的信息，權(quán)、雙親編號(hào)、左孩子編號(hào)、右孩子編號(hào)
輸出參數(shù)：HC： 存儲(chǔ)樹葉結(jié)點(diǎn)的Huffman編碼，每個(gè)編碼均為一個(gè)字符串
*******************************************************************************************/
void Huff_coding( int WeightNum, HTNode *HT, int NodeNum, char **HC )
{
int k, sp, p, fp;
char *cd;
cd = new char[ WeightNum + 1 ]; // 動(dòng)態(tài)分配存儲(chǔ)編碼的工作空間
cd[ WeightNum ] = '\0'; // 編碼的結(jié)束標(biāo)志
for ( k = 1; k <= WeightNum; k++ ) // 逐個(gè)求字符的編碼
{
sp = WeightNum;
//從葉子結(jié)點(diǎn)到根逆向求編碼
for( p = k, fp = HT[k].Parent; fp != 0; p = fp, fp = HT[p].Parent )
{
if ( HT[fp].Lchild == p )
cd[ --sp ] = '0';
else
cd[ --sp ] = '1';
}
HC[k] = new char[ WeightNum - sp + 1 ]; //為第k個(gè)字符分配空間
strcpy( HC[k], &cd[sp] ) ;
}
delete[] cd ;
}
3.測試結(jié)果
文章來源地址http://www.zghlxwxcb.cn/news/detail-467396.html
到了這里，關(guān)于霍夫曼（Huffman）編碼算法詳解之C語言版的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
