一、問題描述

　　信源編解碼是通信系統(tǒng)的重要組成部分。本實驗旨在通過程序設(shè)計實現(xiàn)基于哈夫曼編碼的信源編解碼算法。程序具備以下功能：

對于給定的源文檔SourceDoc.txt，

　　1)?統(tǒng)計其中所有字符的頻度（某字符的頻度等于其出現(xiàn)的總次數(shù)除以總字符數(shù)），包括字母（區(qū)分大小寫）、標(biāo)點符號及格式控制符（空格、回車等）。

　　2)?按頻度統(tǒng)計結(jié)果生成哈夫曼編碼碼表。

　　3)?基于哈夫曼碼表進(jìn)行編碼，生成對應(yīng)的二進(jìn)制碼流，并輸出到文件Encode.dat。

　　4)?對二進(jìn)制碼流進(jìn)行哈夫曼解碼，把結(jié)果輸出到文件DecodeDoc.txt。

　　5)?判斷DecodeDoc.txt與SourceDoc.txt內(nèi)容是否一致，以驗證編解碼系統(tǒng)的正確性。

　　這是一個綜合應(yīng)用c語言各項簡單特性并且跟信息工程比較貼合的一個編程訓(xùn)練題目，在c語言入門提高時還是可以作為一個比較好的訓(xùn)練題目。

二、實驗主體的算法描述

　　2.1數(shù)據(jù)流及位運算部分主要算法

　　2.1.1中英文歸一化處理的算法描述

　　　　中文實際上是使用GB2313格式存儲（也可以通過UTF-8存儲，但此時為3字節(jié)），是由16位2進(jìn)制數(shù)構(gòu)成，并且將其拆解成為兩個8位二進(jìn)制數(shù)（char型）后，首個char一定為負(fù)值。基于以上認(rèn)識，對于中英文的處理算法如下：

　　　　S1:從文件中讀入一個char，判斷是否>0

　　　　S2:如果是，將其通過位運算方式（與一個a（short型）進(jìn)行或（|）操作，再左移（<<）8位）暫存起來，從文件中讀入第二個char，再將其存入暫存中（操作與之前類似，只是不進(jìn)行左移），輸出暫存即可得到中文字符。

　　　　S3：如果否，直接輸出該char。

　　　　2.1.2基于位運算的輸出壓縮算法

　　　　在得到了Huffman編碼的基礎(chǔ)上，要輸出到文件Encode.dat時，考慮到Huffman時壓縮算法，為了最大限度的保證壓縮效果，將字符一次轉(zhuǎn)化為0-1二進(jìn)制編碼，直接拼接，每8位一輸出，確保在最后一個8位之前，每一位二進(jìn)制均含有信息，達(dá)到最大的壓縮效果。

　　　　算法如下：

　　　　S1：得到該字符的Huffman編碼，將每一位0-1編碼通過或運算并入暫存器H中，每并1位，計數(shù)器y++

　　　　S2：判斷y是否等于7，如果是，將H輸出至Encode.dat中，H=0，y=0；如果否，回到S1.

　　　　S3：持續(xù)運行S1及S2，直到讀完整篇文檔為止。

　　2.2鏈表及排序部分主要算法

　　　　鏈表排序選用了快速排序。

　　　　單鏈表的快排序和數(shù)組的快速排序基本思想相同，同樣是基于劃分，但是又有很大的不同：

　　　　單鏈表不支持基于下標(biāo)的訪問，故把待排序的鏈表拆分為2個子鏈表。為了簡單起見，選擇鏈表的第一個節(jié)點作為基準(zhǔn)，然后進(jìn)行比較，比基準(zhǔn)小得節(jié)點放入左面的子鏈表，比基準(zhǔn)大的放入右邊的子鏈表。在對待排序鏈表掃描一遍之后，左邊子鏈表的節(jié)點值都小于基準(zhǔn)的值，右邊子鏈表的值都大于基準(zhǔn)的值，然后把基準(zhǔn)插入到鏈表中，并作為連接兩個子鏈表的橋梁。然后分別對左、右兩個子鏈表進(jìn)行遞歸快速排序，以提高性能。

　　　　但是，由于單鏈表不能像數(shù)組那樣隨機存儲，和數(shù)組的快排序相比較，還是有一些需要注意的細(xì)節(jié)：

　　　　1、支點的選取，由于不能隨機訪問第K個元素，因此每次選擇支點時可以取待排序那部分鏈表的頭指針。

　　　　2、遍歷鏈表方式，由于不能從單鏈表的末尾向前遍歷，因此使用兩個指針分別向前向后遍歷的策略實效，

　　　　事實上，可以采用一趟遍歷的方式將較小的元素放到單鏈表的左邊。具體方法為：

?　　　 ?1)定義兩個指針pslow，pfast，其中pslow指向單鏈表的頭結(jié)點，pfast指向單鏈表頭結(jié)點的下一個結(jié)點;

　　　　2)使用pfast遍歷單鏈表，每遇到一個比支點小的元素，就令pslow=pslow->next，然后和pslow進(jìn)行數(shù)據(jù)交換。

　　　　3)交換數(shù)據(jù)方式，直接交換鏈表數(shù)據(jù)指針指向的部分，不必交換鏈表節(jié)點本身。根據(jù)快速排序的基本思想，鏈表快速排序的時間復(fù)雜度為O(nlog(n))

　　2.3Huffman樹及壓縮解碼部分主要算法

　　2.3.1樹結(jié)構(gòu)

　　　　主樹根左子樹為哈夫曼樹，右子樹為二叉排序樹。二叉排序樹除根節(jié)點外都由哈夫曼樹的葉子節(jié)點重排生成。（詳見 效率分析與加速策略，排序樹生成）

　　2.3.2樹葉節(jié)點結(jié)構(gòu)

　　　　數(shù)據(jù)域:

　　　　包含整形的字符，頻數(shù)，以及數(shù)組形式的密碼。-1標(biāo)示字符為空，密碼數(shù)組中以2作為結(jié)尾標(biāo)示

　　　　指針域:

　　　　包括3個指針，父指針指向節(jié)點在哈夫曼樹中的父節(jié)點（哈夫曼樹與二叉排序樹的父指針指向主根），兩個葉指針指向各自的子樹。

　　　　2.3.3樹與壓縮碼 生成

　　　　鏈表與樹的同步策略：

　　　　鏈表節(jié)點數(shù)據(jù)域中包含一個指向樹葉的指針（初值為空）。初始化樹時首先在所有鏈表節(jié)點下接入樹葉并將樹葉連接成雙向鏈，而后在尾端接入一個空樹葉并記錄為二叉排序樹根，再進(jìn)行后續(xù)操作。

　　　　哈夫曼樹生成算法（基于初始鏈表增序）：

　　　　S1. 建立，初始化并連接新鏈表節(jié)點N與樹葉節(jié)點L。取有頭鏈表頭后兩位數(shù)據(jù)N1、N2，對應(yīng)樹葉節(jié)點為L1、L2。

　　　　S2. 將L1、L2父節(jié)點置為L，L右子樹置為L1，左子樹置為L2。

　　　　S3. 將頭節(jié)點的下一位置為N2的下一位，回收N1、N2，將N插入鏈表

　　　　S4. 當(dāng)鏈表長度（不含頭）大于等于1時，反復(fù)調(diào)用S1~S3

　　　　S5. 記錄鏈表節(jié)點對應(yīng)的葉子節(jié)點，即為哈夫曼樹根

　　　　S6. 生成空葉子節(jié)點，右子樹與二叉排序樹根連接，左子樹與哈夫曼樹根連接。即為主根root。

　　　　壓縮碼生成：

　　　　S1.取root的右子樹，向左遍歷各節(jié)點并執(zhí)行S2~S4

　　　　S2.記錄父節(jié)點，若該節(jié)點為右子樹，記錄1；否則，記錄0

　　　　S3.循環(huán)S2. 直到父節(jié)點為哈夫曼樹樹根（root的左子樹）

　　　　S4.將記錄的反碼反向錄入葉子數(shù)據(jù)域的密碼數(shù)組中

　　　　排序樹生成：

　　　　S1.取排序樹樹根（root的右子樹），向左遍歷各節(jié)點并執(zhí)行S2~S3

　　　　S2.記錄下一節(jié)點，并將此節(jié)點的左右子樹置空。

　　　　S3.按二叉排序樹插入規(guī)則，以字符對應(yīng)的整形數(shù)據(jù)位鍵值，將此節(jié)點插入排序樹

　　　　2.3.4壓縮解碼算法

　　　　壓縮：

　　　　搜索排序樹，并輸出對應(yīng)壓縮碼即可

　　　　解碼：

　　　　循環(huán)讀取壓縮文件，在哈夫曼樹中，0向左、1向右，遇到樹葉即輸出字符返回哈夫曼樹根

　　　　2.3.5效率分析與加速策略

　　　　生成效率分析：

　　　　對有效長度為n的鏈表，分析如下

　　　　同步數(shù)據(jù)，時間復(fù)雜度為n

　　　　生成樹，時間復(fù)雜度為n-1

　　　　生成壓縮碼，生成單個密碼時間復(fù)雜度為O(log(n))，故，總密碼生成效率為O（n*log（n））

　　　　生成排序樹，由于字符按頻數(shù)排序，故字符碼可視為基本隨機。因此，易知平均時間復(fù)雜度為O(n*log(n))

　　　　總效率為 n+n-1+2*O（n*log(n)）=O(n*log(n))

　　　　壓縮解碼效率分析：

　　　　對總長為m，生成頻數(shù)鏈表有效長度為n的文本

　　　　壓縮效率：

　　　　對單字的平均效率為二叉排序樹效率，平均為O(log(n))，故總效率為O(m*log(n))。

　　　　解碼效率:

　　　　對單字的解密效率同樣為O(log(n))，故總效率為O(m*log(n))

　　　　總效率分析:

　　　　由于m>>n本算法總效率為O(m*log(n))，遠(yuǎn)高于無二叉排序樹加速時的期望效率O(m*n)。當(dāng)m、n有至少一個較大時有較大提升，m、n都較大時有機可觀的效率提升，而僅多占用2個額外空間，優(yōu)勢明顯。

　　　　加速策略：

　　　　本算法通過對哈夫曼樹底層重排，以2個額外空間為代價，借助二叉排序樹極大的提升了壓縮效率，同時維持解碼效率不變。實現(xiàn)了加速以及性能提升。

三、實現(xiàn)代碼（c語言）

3.1 ?link.h

#include<stdio.h> #include<stdlib.h> #include<malloc.h> #ifndef LINK_H #define LINK_H #endif typedef struct Leaf {int word,p; //word 字 p 頻數(shù) char code[50];//左 0 右 1 struct Leaf *par,*l,*r; }Leaf;typedef struct Node {int data,code; //data 頻數(shù) code 編碼 int letter; // 字 struct Node *next;Leaf *leaf; //指向樹 }Node;struct Node *head;void create() {head=malloc(sizeof(*head));head->next=NULL; head->leaf=NULL; }void print() {struct Node *p=head->next;while(p!=NULL){printf("%d ",p->data);printf("%d ",p->letter);printf("%d ",p->code);printf("%d \n",p->next);p=p->next;} }void in(int n,int value,int codes,int letters) {struct Node *q=head,*a;int i;a=malloc(sizeof(*a));a->next=NULL;a->data=value;a->letter=letters;a->code=codes;a->leaf=NULL;for(i=0;i<n;i++){q=q->next;}a->next=q->next;q->next=a;} void del(int n) {struct Node *q=head;int i;struct Node *a;for(i=0;i<n;i++){q=q->next;}a=q->next;q->next=a->next;free(a);a=NULL; }void destroy() {struct Node *q=head->next,*r=q->next;while(q!=NULL){free(q);q=r;if(r!=NULL)r=r->next;}free(q);q=NULL;r=NULL;free(head);head=NULL; }void my_swap(int *a,int *b) { int temp; temp=*a; *a=*b; *b=temp; } Node *findlength(){Node *q=head->next;while(q!=NULL){q=q->next;}return q; } void sort_slist(Node *x, Node *y) { if(x==NULL) {return;}if(y==x){return;} Node *pslow = x; Node *pfast = x->next; Node *ptemp = x; while(pfast!= y) { if(pfast->data < x->data) { ptemp = pslow; pslow = pslow->next; my_swap(&pslow->data , &pfast->data);my_swap(&pslow->letter , &pfast->letter); } pfast = pfast->next; } my_swap(&pslow->data , &x->data); my_swap(&pslow->letter , &x->letter);sort_slist(x , pslow); sort_slist(pslow->next , y); }

3.2 ?leaf1.2.h

#include <stdio.h> #include <stdlib.h> #ifndef LEAF_H #define LEAF_H #ifndef STDIO_H #define STDIO_H #endif #ifndef STDLIB_H #define STDLIB_H #endif#ifndef LINK_H #define LINK_H #endifvoid fpf(FILE *fout,int a) {int b=0;int c=0,d=0;if(a>255){d=(a|d)&0x000000ff;c=(a|c);c=c>>8;c=c&0x000000ff;fprintf(fout,"%c%c",c,d);return ;}fprintf(fout,"%c",a);return ; }FILE *pf(int a,FILE *f) {int b=0;int c=0,d=0;if(a>255){d=(a|d)&0x000000ff;c=(a|c);c=c>>8;c=c&0x000000ff;fprintf(f,"%c%c\t",c,d);return f;}fprintf(f,"%c\t",a);return f; }Node *Node_Cre(); int ins (Node *h,Node *node);Leaf *Leaf_Cre(void); int Leaf_Copy(Node *node); int Leaf_Link(Node *node); Leaf *Leaf_LinkAll(Node *h); int Leaf_Fus(Node *h); Leaf *Leaf_Xyz(Node *h); int Leaf_Pen(Leaf *root,Leaf *leaf); int Leaf_Syn(Leaf *root);// Tree，coder，decoder是對外接口 Leaf *Tree(Node *h); //建樹 char *Coder(int word,Leaf *root); //加密 int decoder(char *d,Leaf *root); // 解密 Node *Node_Cre() {Node *node;node=(Node *)calloc(1,sizeof(Node));node->data=0;node->letter=-1;node->leaf=NULL;node->next=NULL;return node; }int ins (Node *h,Node *node) {Node *a,*b=node;for (a=h;a->next!=NULL;a=a->next){if(b->data<a->next->data){b->next=a->next;a->next=b;return 1;}}if (a->next==NULL){a->next=b;}return 1; }Leaf *Leaf_Cre(void) {Leaf *leaf=(Leaf *)calloc(1,sizeof(Leaf));int i;leaf->word=-1;leaf->p=0;leaf->l=NULL;leaf->par=NULL;leaf->r=NULL;for(i=0;i<50;i++){leaf->code[i]=2;}return leaf; }int Leaf_Copy(Node *node) {Leaf *leaf;if (node==NULL){return 0;}else if(node->leaf==NULL){return 0;}else{leaf=node->leaf;leaf->word=node->letter;leaf->p=node->data;return 1;} }int Leaf_Link(Node *node) {Leaf *leaf;if(node==NULL){return 0;}else if(node->leaf==NULL){leaf=Leaf_Cre();node->leaf=leaf;}Leaf_Copy(node);return 1; }Leaf *Leaf_LinkAll(Node *h)// 右邊是上一個 ，即從右向左 {Node *a,*b;Leaf *root,*leaf,*t;int k;a=h;for (a=h;a->next!=NULL;a=a->next){b=a->next;k=Leaf_Link(a);k=Leaf_Link(b);t=a->leaf;t->r=b->leaf;b->leaf->l=a->leaf;}root=Leaf_Cre();a->leaf->r=root;root->l=a->leaf;a=h;leaf=a->leaf;free(leaf);a=h->next;a->leaf->l=NULL;return root; }int Leaf_Fus(Node *h) {Node *a=h->next,*b,*c;int k;if(a==NULL){return 0;}else if(a->next==NULL){return 0;}else{b=a->next;c=Node_Cre();k=Leaf_Link(c);c->leaf->r=a->leaf;c->leaf->l=b->leaf;c->data=a->data+b->data;c->leaf->p=c->data;a->leaf->par=c->leaf;b->leaf->par=c->leaf;h->next=b->next;k=ins(h,c);free(a);free(b);return 1;} }Leaf *Leaf_Xyz(Node *h)// 左子樹解密 右子樹加密 {Leaf *root,*t;Node *a=h,*b;root=Leaf_Cre();t=Leaf_LinkAll(h);root->r=t;for (b=a->next;b->next!=NULL;b=a->next){Leaf_Fus(a);}root->l=b->leaf;b->leaf->par=root;free(a);free(b);return root; }int Leaf_Pen(Leaf *root,Leaf *leaf) // 左小右大 {Leaf *roo=root,*lea=leaf;int a=1;lea->r=NULL;lea->l=NULL;while(lea->word!=roo->word){if(lea->word>roo->word){if(roo->r==NULL){roo->r=lea;return 1;}roo=roo->r;}else{if(roo->l==NULL){roo->l=lea;return 1;}roo=roo->l;}}return 0; }int Leaf_Syn(Leaf *root) {Leaf *a=root->r,*b1,*b2,*r=root->r;char c[50];FILE *f=fopen("Statistic.txt","w");int i,j,n,k;for (i=0;i<50;i++){c[i]=2;}a=a->l;r->l=NULL;r->word=0;while(a!=NULL){b1=a;b2=b1->par;i=0;k=0;while (b2!=root){if(b1!=b2->r){c[i]=0;}else{c[i]=1;}i++;b1=b2;b2=b2->par;}n=i;i--;if(a->word==10){fprintf(f,"Enter\t");}else if(a->word==32){fprintf(f,"Space\t");}else if(a->word==9){fprintf(f,"Tab\t");}else{f=pf(a->word,f);}fprintf(f,"p=%d\tcode:",a->p);for(j=0;j<n;j++){a->code[j]=c[i];fprintf(f,"%d",c[i]);i--;}fprintf(f,"\n");b1=a;a=a->l;Leaf_Pen(r,b1);}fclose(f);return 1; }Leaf *Tree(Node *h) {Leaf *root;root=Leaf_Xyz(h);Leaf_Syn(root);return root; }char *Coder(int word,Leaf *root) {int w=word;char *c;Leaf *leaf=root->r;if(w==0){return NULL;}while(leaf!=NULL){if(w==leaf->word){c=leaf->code;return c;}else if(w>leaf->word){leaf=leaf->r;}else{leaf=leaf->l;}}if(leaf==NULL){return NULL;} }int decoder(char *d,Leaf *root) {unsigned char c=1,t,j;FILE *fou,*fi;Leaf *leaf=root->l;int ii = 0;//fin=fopen(d,"r");fi=fopen("Encode.dat","rb");fou=fopen("DecodeDoc.txt","w");while (1){ii++;c=0;fscanf(fi,"%c",&c);if(feof(fi)){break;}t=1<<7;while (t!=0){j=((t&c)!=0);if (j){leaf=leaf->r;}else{leaf=leaf->l;}if(leaf->word!=-1){fpf(fou,leaf->word);leaf=root->l;}t=t>>1;}}printf("文檔壓縮完成后占總字節(jié)數(shù)為%d\n",ii);fclose(fi);fclose(fou);return 1; } #endif

3.3 codeout.c

#include<stdio.h> #include<stdlib.h> #include<string.h> #include"link.h" #include"leaf1.2.h" unsigned char GOU=0;//編碼區(qū) int j=0; //有用位數(shù) FILE *fin,*fout; Leaf *treehead;void code(char codein[]) {if(codein==NULL){return;} //程序健壯性補充 int i=0; //記位器i=0;while(codein[i] != 2) // {if(j!=8){if(codein[i] == 0){j++;}if(codein[i]==1){switch(j){case 0: GOU=GOU|0x80;break;case 1: GOU=GOU|0x40;break;case 2: GOU=GOU|0x20;break;case 3: GOU=GOU|0x10;break;case 4: GOU=GOU|0x08;break;case 5: GOU=GOU|0x04;break;case 6: GOU=GOU|0x02;break;default: GOU=GOU|0x01;break;}j++;}}if(j == 8){fputc(GOU,fout);GOU=0;j=0;}i++;} }void hafuman() {int a0=1;char *a1;fin=fopen("SourceDoc.txt","r");while(a0!=0){a0=read();a1=Coder(a0,treehead);code(a1); }if(GOU!=0){fputc(GOU,fout);GOU=0;j=0;} }int judgechs(char c) {if(c<0){return 1;}else{return 0;} }int read() //c為文件名 {int i=0,j=0;int *ii=&i;char c=0; fscanf(fin,"%c",&c);if(judgechs(c)){j=(int)(c);j=j&0x000000ff;j=j<<8;i=i|j;j=0;fscanf(fin,"%c",&c);j=(int)c;j=j&0x000000ff;i=i|j;}else{i=(int)c;}return i; }void preread(){create();int t=0;int i=0,n=0,flag=0;t=read();struct Node *q=head->next;in(n,1,-1,t);n++; while(t!=0){ t=read();struct Node *q=head->next;for(i=1;i<=n;i++){if(q->letter==t){q->data=q->data+1;flag=1;break;}q=q->next;}if(flag==1){flag=0;continue;}in(n,1,-1,t);n++; } del(n-1);Node*z=findlength();sort_slist(head->next,z); }int main(){system("color 3b");fin=fopen("SourceDoc.txt","r");if(fin==NULL){printf("請正確導(dǎo)入文件\n");system("pause");return 0;}fout=fopen("Encode.dat","w");preread();treehead=Tree(head);hafuman();printf("編碼成功,加密文件輸出于Encode.dat,歡迎查看\n");fclose(fout);fclose(fin);decoder(fout,treehead);printf("解碼成功，結(jié)果輸出于DecodeDoc.txt,歡迎查看\n");system("pause");return 0; }

四、實驗后續(xù)

　　若要真正實現(xiàn)一個可用的壓縮軟件，需要一個交互式的界面，由于c語言本身開發(fā)圖形界面并不算太好用，加上在設(shè)計初期并沒有考慮這個問題，因此在后續(xù)想進(jìn)一步加入圖形界面是遇到了一些困難，我們嘗試通過把程序變成.h頭文件形式嵌入QT工程來實現(xiàn)圖形界面，在QT自帶開發(fā)工具下實現(xiàn)了這一目標(biāo)，但是無法生成可用的.exe文件。若后續(xù)閑暇之時實現(xiàn)了這一功能，將會更新。本文基于當(dāng)時實驗報告簡易修改而成，感謝當(dāng)時的兩位一起完成本工程的同學(xué)yy及yjc。限于水平有限，文中必然有所疏忽和可以改進(jìn)之處，如有問題或者想交流歡迎電子郵件或者站內(nèi)信聯(lián)系。

作者信息：xbf ?西安交通大學(xué)信息通信系本科

聯(lián)系方式：664084331@qq.com

?

轉(zhuǎn)載于:https://www.cnblogs.com/xbfxjtuedu/p/10055097.html

總結(jié)

以上是生活随笔為你收集整理的Huffman树压缩程序（c实现）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。