Huffman编码文献综述

1、Huffman编码文献综述前言Huffman算法对于电码的压缩编译进行分析和实现，通过实践验证Huffman算法在电码的压缩中可以取得良好的压缩效果。本文献综述介绍了Huffman算法的原理与应用及其实现。通过此文献综述，有助于读者快速深刻地学习Huffman编码。 摘要目前，进行快速远距离通信的主要手段是电报，即将需要传送的文字转换成由二进制的字符组成的字符串。而哈夫曼编码作为一种高效的数据压缩技术，被广泛应用于节省数据文件的存储空间和计算机网络的传送时间，从而提高信道利用率，降低运输成本。和所有的编译码系统一样，哈夫曼编码译码系统分为编码和译码两大部分，编码使用了带权路径长度最小二叉树算法

2、，译码则使用了，已知哈夫曼树的情况下，通过左右子树的遍历最终达到叶子节点译出字母。关键词压缩；最优二叉树；编码；译码主题 在互联网时代，在数据通信传送和下载中，媒体数据（包括视频媒体和音频媒体等）采用数字化的格式，大量的数据资源给存储器的存储容量、通信信道带宽和计算机处理速度带来很大的负担，但因当前科学技术发展有限，很多硬件技术还无法完全满足计算机存储资源的需求，与带宽之间差距还很大，仅靠通过增加存储容量、扩充信道容量以及提高计算机处理速度等方法来解决这个问题还有一定难度，这就需要考虑压缩。压缩的关键技术在于设计合理的编码技术，如果在计算机通信数据传输过程中，根据各字符在电文中出现的频率的高低

3、，采用变长的二进制位表示，出现频率高的字符则编码较短，出现频率低的则编码较短的原则对报文字符重新进行编码，从而使原本很长的电文代码大大缩短，得到平均长度最短的电文编码，使报文在存储和传输中，存储空间降低，信息传输效率提高，实现压缩目的1计算机数据编码方式有哈夫曼编码、限定长度变化编码、算法编码等。作为一种无损数据压缩编码，哈夫曼编码广泛应用于文本、图像、视频压缩、通信数据传输、密码等信息压缩编码标准中。当然，在传送电文时，希望总长尽可能的短，如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，则传送电文的总长便可减少，如果设计A，B,C,D的编码分别为0、00、1

4、和01，则可能会出现译码冲突，产生多种译码，因此，若要设计长短不等的编码，则必须是任一字符的编码都不可以是另一个字符的编码的前提，这种编码叫做前缀编码。因此，我们可以利用二叉树来设计二进制的前缀编码，使出现的字符作为叶子结点，且约定左分支表示为“0”，右分支表示为“1”，则可以从根结点到叶子结点的路径上分支字符串作为该叶子结点字符的编码。如此得到的必为二进制前缀编码。为了得到使电文总长最短的二进制前缀编码，假设每种字符在电文出现的次数为i，其编码长度为i，电文中只有N种字符，则电文总长为（n，i=1）ii。对应到二叉树上，若置i为叶子结点的权，i恰为从根到叶子的路径长度。则（n，i=1）ii为

5、二叉树上带权路径长度。由此可见，设计电文总长最短的二进制前缀编码即为以N种字符出现的频率做权，设计一棵哈夫曼树的问题，由此得到的二进制前缀编码便称为哈夫曼编码。哈夫曼树中没有度为1的结点，则一棵有N个叶子结点的哈夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中。在构成哈夫曼树之后，为求编码需从叶子结点出发走一条以叶子到根的路径；而为译码需从根出发走一条从根到叶子的路径。则对每个结点而言，既需知双亲的信息，又需要知道孩子结点的信息。（以下是存储结构）/-哈夫曼树和哈夫曼编码的存储表示-Typedef structUnsigned int weight;Unsigned int

6、parent,lchild,rchild;HTNode, *HuffmanTree;Typedef char * *HuffmanCode;Void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)/w存放n个字符的权值,构造哈夫曼树HT,并求出N个字符的哈夫曼编码HCIf(n=1)return;m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);For(p=HT,i=1;i=n;+i,+p,+w)*p=*w,0,0,0;For(;i=m;+i,+p) *p=0,0,0,0;

7、For(i=n+1;i=m;+i)/建哈夫曼树,在HT1.i-1选择parent为0且weight最小的两个结点,其序号分别为s1,s2。Select(HT,i-1,s1,s2）；HTs1.parent=i; HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/-从叶子到根逆向求每个字符的哈夫曼编码HC=(HuffmanCode)malloc(n+1)*sizeof(char*);cd=(char *)malloc(n*sizeof(char);cdn-1=”0”;For(i=1;i=n;+

8、i)Start=n-1;For(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)If(HTf.child = c) cd-start=”0”;Else cd-start=”1”;HCi=(char*)malloc(n-start)*sizeof(char);Strcpy(HCi,&cdstart);Free(cd);向量HT的前n个分量表示叶子结点,最后一个分量表示根结点,各字符的编码长度不一样,所以按实际长度动态分配空间。也可以从根出发，遍历整棵哈夫曼树，求得各个叶子结点所表示的字符的哈夫曼编码。/-无栈非递归遍历哈夫曼树,求哈夫曼编码HC=(HuffmanCo

9、de)malloc(n+1)*sizeof(char*);p=m; cdlen=0;for(i=1;i=m;+i) HTI.weight =0;While(p)If(HTp.weight=0)HTp.weight = 1;If(HTp.lchild!=0)p=HTp.lchild; cdcdlen+ = “0”else if(HTp.rchild = 0)HTp.weight= 2;If(HTp.rchild!=0)p=HTp.rchild; cdcdlen+=”1”;elseHTp.weight = 0;p=HTp.parent;-cdlen;/-以下是译码部分-#include my.h/

10、译码函数void Decodeing(HFMC C)FILE *in,*out;int i,j,k,c_max,c_len,dq,dq_len,flag,error=0;/error初始状态为假char codeMAXLEN_1,aMAXLEN,zwMAXLEN;code0=0;/打开文件codefile.dat，读取编码正文写入内存，存入数组codeif(in=fopen(codefile.dat,r)!=NULL)fscanf(in,%s,code);elseprintf(n打开文件错误!);return;fclose(in);/求编码正文长度c_lenfor(i=0;code!=0;i+

11、);c_len=i;if(c_len=0)error=1;/错误情况1/求编码库最长编码长度c_maxc_max=0;for(i=0;ifor(j=0;C.codej!=0;j+);if(c_maxc_max=j;/进行译码dq=0; /dq用来记录code数组的读取位置k=0; /k用来记录zw数组读取位置while(dqflag=1;dq_len=c_max;for(i=dq,j=0;jaj=code;aj=0;while(flag&!error)/若无错误且flag为1则继续循环for(i=0;iif(strcmp(a,C.code)=0)zwk=C.data;k+;flag=0;bre

12、ak;/若找到编码库里匹配的编码，则结束循环if(flag)dq_len-;adq_len=0;/未找到则将当前长度减一，继续寻找if(dq_len1)error=1;/译码错误情况2dq=dq+dq_len;/编码正文当前读取位置改变zwk=0;/在zw数组的最后一个位置添加字符串结束符if(error)printf(n译码错误，请重新检查!);return;else/打印编码正文以及译码正文printf(n编码为:%s,code);printf(n译码为:%s,zw);/打开文件textfile.dat，将译码正文即数组zw写入文件if(out=fopen(textfile.dat,w)!

13、=NULL)fprintf(out,%s,zw);elseprintf(n打开文件错误!);return;fclose(out);printf(n译码成功!);以下内容摘自基于改进哈夫曼编码的数据压缩方法研究。张红军，徐超目前的哈夫曼编码方式是通过对构造好的哈夫曼树进行自下向上的方式实现数据编码，该方式有一些可以待改进之处2,3：在算法的时间复杂度上，如果定义叶子节点所在的层次为第1层，其父节点为第2层，依次类推，处在第n层上的节点要被扫描n-1次，在程序运行过程中存在着许多指针移动，其时间复杂度为O(n2)。在数据压缩中，哈夫曼编码是一种变长编码，采用的是一种优化静态编码方法。具有以下不足：

14、（1）需要事先知道输入码字符集的频率分布，在不同的数据文件中，不同字符出现的频率不同。（2）需要对原始数据块扫描两次：第一次是统计原始数据中各符号出现的频率并排序，利用得到的频率值创建哈夫曼树并将树的有关信息保存起来，便于解压时使用；第二次是进行编码，根据前面得到的哈夫曼树对原始数据进行编码，并将编码信息存储起来，便于存储和传输。如果将这种方法用于数据的网络通信中两遍扫描势必会引起较大的延时，两次扫描所引发的低效率不容忽视；同时，如果用于文件数据的压缩中，重复扫描增加了磁盘访问，额外的磁盘访问将会降低该算法的数据压缩速度，从而降低压缩效率。本算法用二叉树层次遍历方式，利用队列（Queue）对整

15、棵哈夫曼树进行一次扫描，即可得到各节点的哈夫曼编码。在本结构体中，除了包含节点的编码信息域及权值之外，还应包含该节点所对应的排序码key，指向其右右孩子的指针left和right，指针其双亲结点的指针parent，具体设计如下：Typedef struct node *BT; Struct node char date,key10; Int weight; Struct node *left,*right,*parent; 本算法采用循环队列，head指向队头节点，tail指向队尾节点，numbers表示当前队列中节点的个数，queuelist是表示队列的数组。Typedef struct c

16、ircle int head,tail; int numbers; BT queuelistsize; 算法描述改进算法从哈夫曼的根节点出发，通过利用队列，按照层次遍历的方法依次对树中每个叶子节点进行编码。算法执行过程如下：（1）根据字符集c1,c2,cn和相应的权值集w1,w2,wn建立相应的哈夫曼树，并将哈夫曼树的根节点入队；（2） 当队列为非空时，递归执行以下操作：a 指针p指向当前队头节点；b.若当前队头节点无双亲节点，表示该节点为根节点将该根节点出队 （Dequeue），并让其左孩子节点和右孩子节点先后入队（Enqueue）；c若当前节点有双亲节点，则给其左、右孩子节点分别赋值为父节

17、点的哈夫曼编码，然后，若此节点为其父节点的左孩子，则在其父节点所赋给的编码后面加一个“0”，若此节点为其父节点的右孩子，则在其父节点所赋给的编码后面加一个“1”；由于根节点无编码，可以直接分别得到“O”，“1”作为自己的编码；d队头节点出队；若出队节点有左右孩子节点，则让其左右孩子分别入队，若出队节点没有左右孩子节点，转向e；e判断当前队列是否为空，若为空则编码工作完成。算法实现流程开始；将根节点入队列；判断队列是否为空；如果为空，则转向j；指针q指向队头节点；判断q是否为根节节；如果是根节点，则转向h；否则复制其父节点的编码信息；判断该节点是父节点的左孩子还是右孩子；如果是左孩子，则在复制的

18、父节点的编码后面添加一个“0”，否则在复制的父节点的编码后面添加一个“1”；队头节点出队；判断出队节点是否有左右孩子，如果有，则将出队节点的左右孩子节点入队，否则转向c；结束。结语通过对有关哈夫曼编码的文献统计与分析,可以看出以下一些结论(1) 哈夫曼除了应用于文字压缩以外,还能用于文件压缩以及图像处理,这里仅以文字压缩处理作为切入点.(2) 哈夫曼作为一种高效的数据压缩技术,有效的节省数据文件的存储空间和计算机网络的传送时间，从而提高信道利用率，降低运输成本。(3) 哈夫曼因为它的特殊以及高效性,能够不断的进行更新应用,对未来将会有极大的作用,发展前景仍然是有的。参考文献1朱怀宏,吴楠,夏黎春， 利用优化哈夫曼编码进行数据压缩的探索J，微 机发展，2002（第05期