哈夫曼樹的應(yīng)用_哈夫曼樹代碼實(shí)現(xiàn)

一、簡介

哈夫曼樹又稱為最優(yōu)樹。


1、路徑和路徑長度


在一棵樹中，從一個結(jié)點(diǎn)往下可以達(dá)到的孩子或子孫結(jié)點(diǎn)之間的通路，稱為路徑。通路中分支的數(shù)目稱為路徑長度。若規(guī)定根結(jié)點(diǎn)的層數(shù)為1，則從根結(jié)點(diǎn)到第L層結(jié)點(diǎn)的路徑長度為L-1。


2、結(jié)點(diǎn)的權(quán)及帶權(quán)路徑長度


若將樹中結(jié)點(diǎn)賦給一個有著某種含義的數(shù)值，則這個數(shù)值稱為該結(jié)點(diǎn)的權(quán)。結(jié)點(diǎn)的帶權(quán)路徑長度為：從根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長度與該結(jié)點(diǎn)的權(quán)的乘積。


3、樹的帶權(quán)路徑長度


樹的帶權(quán)路徑長度規(guī)定為所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和，記為WPL


二、哈夫曼樹的應(yīng)用


1、哈夫曼編碼


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


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

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


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


2、哈夫曼譯碼

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

三、二叉樹實(shí)現(xiàn)哈夫曼編碼


/*************************
? ? ? ? Filename :Linkqueue.h
? ? ? ? **************************/


typedef struct _tree_
? ? ? ? {
? ? ? ? ? ? ? ? char ch;
? ? ? ? ? ? ? ? int weight;
? ? ? ? ? ? ? ? char code[10];
? ? ? ? ? ? ? ? struct _tree_ *next, *lchild, *rchild;
? ? ? ? } bitree;


typedef bitree *datatype;


typedef struct _node_
? ? ? ? {
? ? ? ? ? ? ? ? datatype data;
? ? ? ? ? ? ? ? ?struct _node_ *next;
? ? ? ? } listnode;


typedef struct
? ? ? ? ?{
? ? ? ? ? ? ? ? listnode *front;
? ? ? ? ? ? ? ? ?listnode *rear;
? ? ? ? } linkqueue;


linkqueue *CreateEmptyLinkqueue();


int EmptyLinkqueue(linkqueue *q);


void EnQueue(linkqueue *q, datatype x);


datatype DeQueue(linkqueue *q);


/*************************
? ? ? ? Filename :Huffman.c
? ? ? ? **************************/


＃i nclude
? ? ? ? ＃i nclude
? ? ? ? ＃i nclude
? ? ? ? ＃i nclude "linkqueue.h"


bitree *CreateEmptyList()
? ? ? ? {
? ? ? ? bitree *h;
? ? ? ? h = (bitree *)malloc(sizeof(bitree));
? ? ? ? h->next = h->lchild = h->rchild = NULL;
? ? ? ? return h;
? ? ? ? }


void InsertList(bitree *h, bitree *q)
? ? ? ? {
? ? ? ? ? ? ? ? while (h->next && (h->next->weight < q->weight))
? ? ? ? {
? ? ? ? ? ? ? ? h = h->next;
? ? ? ? }
? ? ? ? ? ? ? ? q->next = h->next;
? ? ? ? ? ? ? ? h->next = q;
? ? ? ? ? ? ? ? return;
? ? ? ? ?}


void VisitList(bitree *h)
? ? ? ? {
? ? ? ? ? ? ? ? h = h->next;
? ? ? ? ? ? ? ? while ( h )
? ? ? ? {
? ? ? ? ? ? ? ? printf("%d ", h->weight);
? ? ? ? ? ? ? ? h = h->next;
? ? ? ? }
? ? ? ? ? ? ? ? printf("n");
? ? ? ? ? ? ? ? return;
? ? ? ? }


void CreateHaffmanTree(bitree *h)
? ? ? ? {
? ? ? ? ? ? ? ? bitree *p;
? ? ? ? ? ? ? ? ?while (h->next && h->next->next)
? ? ? ? ? ? ? ? ?{
? ? ? ? ? ? ? ? ? ? ? ? p = (bitree *)malloc(sizeof(bitree));
? ? ? ? ? ? ? ? ? ? ? ? p->lchild = h->next;
? ? ? ? ? ? ? ? ? ? ? ? ?p->rchild = h->next->next;
? ? ? ? ? ? ? ? ? ? ? ? ?p->weight = p->lchild->weight + p->rchild->weight;
? ? ? ? ? ? ? ? ? ? ? ? ?h->next = p->rchild->next;
? ? ? ? ? ? ? ? ? ? ? ? ?InsertList(h, p);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? return;
? ? ? ? }


void NoOrder(bitree *root)
? ? ? ? {
? ? ? ? ? ? ? ? bitree *p;
? ? ? ? ? ? ? ? ?linkqueue *queue;
? ? ? ? ? ? ? ? queue = CreateEmptyLinkqueue();
? ? ? ? ? ? ? ? EnQueue(queue, root);
? ? ? ? ? ? ? ? while ( !EmptyLinkqueue(queue) )
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? ?p = DeQueue(queue);
? ? ? ? ? ? ? ? ? ? ? ? if ((p->lchild == NULL) && (p->rchild == NULL))
? ? ? ? ? ? ? ? ? ? ? ? {?
? ? ? ? ? ? ? ? ? ? ? ? printf("%c[%2d] : %sn", p->ch, p->weight, p->code);
? ? ? ? ? ? ? ? ? ? ? ? ?continue;
? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? if (p->lchild)?
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? ?strcpy(p->lchild->code, p->code);
? ? ? ? ? ? ? ? ? ? ? ? strcat(p->lchild->code, "0");
? ? ? ? ? ? ? ? ? ? ? ? ?EnQueue(queue, p->lchild);
? ? ? ? ? ? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ? ? ? ? ? if (p->rchild)?
? ? ? ? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? strcpy(p->rchild->code, p->code);
? ? ? ? ? ? ? ? ? ? ? ? strcat(p->rchild->code, "1");
? ? ? ? ? ? ? ? ? ? ? ? ?EnQueue(queue, p->rchild);
? ? ? ? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? return;
? ? ? ? }


int main(int argc, char *argv[])
? ? ? ? {
? ? ? ? ? ? ? ? int i, value;
? ? ? ? ? ? ? ? char ch;
? ? ? ? ? ? ? ? bitree *h, *p;
? ? ? ? ? ? ? ? h = CreateEmptyList();
? ? ? ? ? ? ? ? while (scanf("%c %dn", &ch, &value) == 2)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? ? p = (bitree *)malloc(sizeof(bitree));
? ? ? ? ? ? ? ? ? ? ? ? ?p->ch = ch;
? ? ? ? ? ? ? ? ? ? ? ? p->weight = value;
? ? ? ? ? ? ? ? ? ? ? ? p->code[0] = '';
? ? ? ? ? ? ? ? ? ? ? ? p->lchild = p->rchild = NULL;
? ? ? ? ? ? ? ? ? ? ? ? InsertList(h, p);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? VisitList(h);
? ? ? ? ? ? ? ? CreateHaffmanTree(h);
? ? ? ? ? ? ? ? NoOrder(h->next);
? ? ? ? ? ? ? ? return 0;
? ? ? ? }


/*************************
? ? ? ? Filename :Linkqueue.c
? ? ? ? **************************/


＃i nclude
? ? ? ? ?＃i nclude
? ? ? ? ?＃i nclude "linkqueue.h"
? ? ? ? linkqueue *CreateEmptyLinkqueue()
? ? ? ? {
? ? ? ? ? ? ? ? linkqueue *q;
? ? ? ? ? ? ? ? q = (linkqueue *)malloc(sizeof(linkqueue));
? ? ? ? ? ? ? ? q->front = q->rear = (listnode *)malloc(sizeof(listnode));
? ? ? ? ? ? ? ? ?q->front->next = NULL;
? ? ? ? ? ? ? ? return q;
? ? ? ? }


int EmptyLinkqueue(linkqueue *q)
? ? ? ? ?{
? ? ? ? ? ? ? ? ?return (q->front == q->rear);
? ? ? ? }


void EnQueue(linkqueue *q, datatype r)
? ? ? ? {
? ? ? ? ? ? ? ? listnode *p;
? ? ? ? ? ? ? ? p = (listnode *)malloc(sizeof(listnode));
? ? ? ? ? ? ? ? p->data = r;
? ? ? ? ? ? ? ? p->next = NULL;
? ? ? ? ? ? ? ? q->rear->next = p;
? ? ? ? ? ? ? ? q->rear = p;
? ? ? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? datatype DeQueue(linkqueue *q)
? ? ? ? {
? ? ? ? ? ? ? ?listnode *p;
? ? ? ? ? ? ? ? p = q->front;
? ? ? ? ? ? ? ? q->front = p->next;
? ? ? ? ? ? ? ? free(p);
? ? ? ? ? ? ? ? return q->front->data;
? ? ? ? }