一、问题描述
信源编解码是通信系统的重要组成部分。本实验旨在通过程序设计实现基于哈夫曼编码的信源编解码算法。程序具备以下功能：
对于给定的源文档SourceDoc.txt，
1) 统计其中所有字符的频度（某字符的频度等于其出现的总次数除以总字符数），包括字母（区分大小写）、标点符号及格式控制符（空格、回车等）。
2) 按频度统计结果生成哈夫曼编码码表。
3) 基于哈夫曼码表进行编码，生成对应的二进制码流，并输出到文件Encode.dat。
4) 对二进制码流进行哈夫曼解码，把结果输出到文件DecodeDoc.txt。
5) 判断DecodeDoc.txt与SourceDoc.txt内容是否一致，以验证编解码系统的正确性。
这是一个综合应用c语言各项简单特性并且跟信息工程比较贴合的一个编程训练题目，在c语言入门提高时还是可以作为一个比较好的训练题目。
二、实验主体的算法描述
2.1数据流及位运算部分主要算法
2.1.1中英文归一化处理的算法描述
中文实际上是使用GB2313格式存储（也可以通过UTF-8存储，但此时为3字节），是由16位2进制数构成，并且将其拆解成为两个8位二进制数（char型）后，首个char一定为负值。基于以上认识，对于中英文的处理算法如下：
S1:从文件中读入一个char，判断是否>0
S2:如果是，将其通过位运算方式（与一个a（short型）进行或（|）操作，再左移（<<）8位）暂存起来，从文件中读入第二个char，再将其存入暂存中（操作与之前类似，只是不进行左移），输出暂存即可得到中文字符。
S3：如果否，直接输出该char。
2.1.2基于位运算的输出压缩算法
在得到了Huffman编码的基础上，要输出到文件Encode.dat时，考虑到Huffman时压缩算法，为了最大限度的保证压缩效果，将字符一次转化为0-1二进制编码，直接拼接，每8位一输出，确保在最后一个8位之前，每一位二进制均含有信息，达到最大的压缩效果。
算法如下：
S1：得到该字符的Huffman编码，将每一位0-1编码通过或运算并入暂存器H中，每并1位，计数器y++
S2：判断y是否等于7，如果是，将H输出至Encode.dat中，H=0，y=0；如果否，回到S1.
S3：持续运行S1及S2，直到读完整篇文档为止。
2.2链表及排序部分主要算法
链表排序选用了快速排序。
单链表的快排序和数组的快速排序基本思想相同，同样是基于划分，但是又有很大的不同：
单链表不支持基于下标的访问，故把待排序的链表拆分为2个子链表。为了简单起见，选择链表的第一个节点作为基准，然后进行比较，比基准小得节点放入左面的子链表，比基准大的放入右边的子链表。在对待排序链表扫描一遍之后，左边子链表的节点值都小于基准的值，右边子链表的值都大于基准的值，然后把基准插入到链表中，并作为连接两个子链表的桥梁。然后分别对左、右两个子链表进行递归快速排序，以提高性能。
但是，由于单链表不能像数组那样随机存储，和数组的快排序相比较，还是有一些需要注意的细节：
1、支点的选取，由于不能随机访问第K个元素，因此每次选择支点时可以取待排序那部分链表的头指针。
2、遍历链表方式，由于不能从单链表的末尾向前遍历，因此使用两个指针分别向前向后遍历的策略实效，
事实上，可以采用一趟遍历的方式将较小的元素放到单链表的左边。具体方法为：
1)定义两个指针pslow，pfast，其中pslow指向单链表的头结点，pfast指向单链表头结点的下一个结点;
2)使用pfast遍历单链表，每遇到一个比支点小的元素，就令pslow=pslow->next，然后和pslow进行数据交换。
3)交换数据方式，直接交换链表数据指针指向的部分，不必交换链表节点本身。根据快速排序的基本思想，链表快速排序的时间复杂度为O(nlog(n))
2.3Huffman树及压缩解码部分主要算法
2.3.1树结构
主树根左子树为哈夫曼树，右子树为二叉排序树。二叉排序树除根节点外都由哈夫曼树的叶子节点重排生成。（详见 效率分析与加速策略，排序树生成）
2.3.2树叶节点结构
数据域:
包含整形的字符，频数，以及数组形式的密码。-1标示字符为空，密码数组中以2作为结尾标示
指针域:
包括3个指针，父指针指向节点在哈夫曼树中的父节点（哈夫曼树与二叉排序树的父指针指向主根），两个叶指针指向各自的子树。
2.3.3树与压缩码 生成
链表与树的同步策略：
链表节点数据域中包含一个指向树叶的指针（初值为空）。初始化树时首先在所有链表节点下接入树叶并将树叶连接成双向链，而后在尾端接入一个空树叶并记录为二叉排序树根，再进行后续操作。
哈夫曼树生成算法（基于初始链表增序）：
S1. 建立，初始化并连接新链表节点N与树叶节点L。取有头链表头后两位数据N1、N2，对应树叶节点为L1、L2。
S2. 将L1、L2父节点置为L，L右子树置为L1，左子树置为L2。
S3. 将头节点的下一位置为N2的下一位，回收N1、N2，将N插入链表
S4. 当链表长度（不含头）大于等于1时，反复调用S1~S3
S5. 记录链表节点对应的叶子节点，即为哈夫曼树根
S6. 生成空叶子节点，右子树与二叉排序树根连接，左子树与哈夫曼树根连接。即为主根root。
压缩码生成：
S1.取root的右子树，向左遍历各节点并执行S2~S4
S2.记录父节点，若该节点为右子树，记录1；否则，记录0
S3.循环S2. 直到父节点为哈夫曼树树根（root的左子树）
S4.将记录的反码反向录入叶子数据域的密码数组中
排序树生成：
S1.取排序树树根（root的右子树），向左遍历各节点并执行S2~S3
S2.记录下一节点，并将此节点的左右子树置空。
S3.按二叉排序树插入规则，以字符对应的整形数据位键值，将此节点插入排序树
2.3.4压缩解码算法
压缩：
搜索排序树，并输出对应压缩码即可
解码：
循环读取压缩文件，在哈夫曼树中，0向左、1向右，遇到树叶即输出字符返回哈夫曼树根
2.3.5效率分析与加速策略
生成效率分析：
对有效长度为n的链表，分析如下
同步数据，时间复杂度为n
生成树，时间复杂度为n-1
生成压缩码，生成单个密码时间复杂度为O(log(n))，故，总密码生成效率为O（n*log（n））
生成排序树，由于字符按频数排序，故字符码可视为基本随机。因此，易知平均时间复杂度为O(n*log(n))
总效率为 n+n-1+2*O（n*log(n)）=O(n*log(n))
压缩解码效率分析：
对总长为m，生成频数链表有效长度为n的文本
压缩效率：
对单字的平均效率为二叉排序树效率，平均为O(log(n))，故总效率为O(m*log(n))。
解码效率:
对单字的解密效率同样为O(log(n))，故总效率为O(m*log(n))
总效率分析:
由于m>>n本算法总效率为O(m*log(n))，远高于无二叉排序树加速时的期望效率O(m*n)。当m、n有至少一个较大时有较大提升，m、n都较大时有机可观的效率提升，而仅多占用2个额外空间，优势明显。
加速策略：
本算法通过对哈夫曼树底层重排，以2个额外空间为代价，借助二叉排序树极大的提升了压缩效率，同时维持解码效率不变。实现了加速以及性能提升。
三、实现代码（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 频数 char code[50];//左 0 右 1 struct Leaf *par,*l,*r; }Leaf; typedef struct Node { int data,code; //data 频数 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 ",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 #endif void 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 ",c,d); return f; } fprintf(f,"%c ",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 "); } else if(a->word==32) { fprintf(f,"Space "); } else if(a->word==9) { fprintf(f,"Tab "); } else { f=pf(a->word,f); } fprintf(f,"p=%d code:",a->p); for(j=0;j<n;j++) { a->code[j]=c[i]; fprintf(f,"%d",c[i]); i--; } fprintf(f," "); 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("文档压缩完成后占总字节数为%d ",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;//编码区 int j=0; //有用位数 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("请正确导入文件 "); system("pause"); return 0; } fout=fopen("Encode.dat","w"); preread(); treehead=Tree(head); hafuman(); printf("编码成功,加密文件输出于Encode.dat,欢迎查看 "); fclose(fout); fclose(fin); decoder(fout,treehead); printf("解码成功，结果输出于DecodeDoc.txt,欢迎查看 "); system("pause"); return 0; }
四、实验后续
若要真正实现一个可用的压缩软件，需要一个交互式的界面，由于c语言本身开发图形界面并不算太好用，加上在设计初期并没有考虑这个问题，因此在后续想进一步加入图形界面是遇到了一些困难，我们尝试通过把程序变成.h头文件形式嵌入QT工程来实现图形界面，在QT自带开发工具下实现了这一目标，但是无法生成可用的.exe文件。若后续闲暇之时实现了这一功能，将会更新。本文基于当时实验报告简易修改而成，感谢当时的两位一起完成本工程的同学yy及yjc。限于水平有限，文中必然有所疏忽和可以改进之处，如有问题或者想交流欢迎电子邮件或者站内信联系。
作者信息：xbf 西安交通大学信息通信系本科
联系方式：664084331@qq.com