Huffman编码文献综述2.0

Huffman编码文献综述前言Huffman算法对于电码的压缩编译进行分析和实现，通过实践验证Huffman算法在电码的压缩中可以取得良好的压缩效果。本文献综述介绍了Huffman算法的原理与应用及其实现。通过此文献综述，有助于读者快速深刻地学习Huffman编码。摘要目前，进行快速远距离通信的主要手段是电报，即将需要传送的文字转换成由二进制的字符组成的字符串。而哈夫曼编码作为一种高效的数据压缩技术，被广泛应用于节省数据文件的存储空间和计算机网络的传送时间，从而提高信道利用率，降低运输成本。和所有的编译码系统一样，哈夫曼编码译码系统分为编码和译码两大部分，编码使用了带权路径长度最小二叉树算法，译码则使用了，已知哈夫曼树的情况下，通过左右子树的遍历最终达到叶子节点译出字母。关键词压缩；最优二叉树；编码；译码主题在互联网时代，在数据通信传送和下载中，媒体数据（包括视频媒体和音频媒体等）采用数字化的格式，大量的数据资源给存储器的存储容量、通信信道带宽和计算机处理速度带来很大的负担，但因当前科学技术发展有限，很多硬件技术还无法完全满足计算机存储资源的需求，与带宽之间差距还很大，仅靠通过增加存储容量、扩充信道容量以及提高计算机处理速度等方法来解决这个问题还有一定难度，这就需要考虑压缩。压缩的关键技术在于设计合理的编码技术，如果在计算机通信数据传输过程中，根据各字符在电文中出现的频率的高低，采用变长的二进制位表示，出现频率高的字符则编码较短，出现频率低的则编码较短的原则对报文字符重新进行编码，从而使原本很长的电文代码大大缩短，得到平均长度最短的电文编码，使报文在存储和传输中，存储空间降低，信息传输效率提高，实现压缩目的[1]计算机数据编码方式有哈夫曼编码、限定长度变化编码、算法编码等。作为一种无损数据压缩编码，哈夫曼编码广泛应用于文本、图像、视频压缩、通信数据传输、密码等信息压缩编码标准中。当然，在传送电文时，希望总长尽可能的短，如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，则传送电文的总长便可减少，如果设计A，B,C,D的编码分别为0、00、1和01，则可能会出现译码冲突，产生多种译码，因此，若要设计长短不等的编码，则必须是任一字符的编码都不可以是另一个字符的编码的前提，这种编码叫做前缀编码。因此，我们可以利用二叉树来设计二进制的前缀编码，使出现的字符作为叶子结点，且约定左分支表示为“0”，右分支表示为“1”，则可以从根结点到叶子结点的路径上分支字符串作为该叶子结点字符的编码。如此得到的必为二进制前缀编码。为了得到使电文总长最短的二进制前缀编码，假设每种字符在电文出现的次数为ωi，其编码长度为ιi，电文中只有N种字符，则电文总长为∑（n，i=1）ωiιi。对应到二叉树上，若置ωi为叶子结点的权，ιi恰为从根到叶子的路径长度。则∑（n，i=1）ωiιi为二叉树上带权路径长度。由此可见，设计电文总长最短的二进制前缀编码即为以N种字符出现的频率做权，设计一棵哈夫曼树的问题，由此得到的二进制前缀编码便称为哈夫曼编码。哈夫曼树中没有度为1的结点，则一棵有N个叶子结点的哈夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中。在构成哈夫曼树之后，为求编码需从叶子结点出发走一条以叶子到根的路径；而为译码需从根出发走一条从根到叶子的路径。则对每个结点而言，既需知双亲的信息，又需要知道孩子结点的信息。（以下是存储结构）//-------------哈夫曼树和哈夫曼编码的存储表示------Typedefstruct{Unsignedintweight;Unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;Typedefchar**HuffmanCode;VoidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){//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};For(i=n+1;i=m;++i){//建哈夫曼树,在HT[1....i-1]选择parent为0且weight最小的两个结点,其序号分别为s1,s2。Select(HT,i-1,s1,s2）；HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}//--------从叶子到根逆向求每个字符的哈夫曼编码HC=(HuffmanCode)malloc((n+1)*sizeof(char*));cd=(char*)malloc(n*sizeof(char));cd[n-1]=”\0”;For(i=1;i=n;++i){Start=n-1;For(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)If(HT[f].child==c)cd[--start]=”0”;Elsecd[--start]=”1”;HC[i]=(char*)malloc((n-start)*sizeof(char));Strcpy(HC[i],&cd[start]);}Free(cd);}向量HT的前n个分量表示叶子结点,最后一个分量表示根结点,各字符的编码长度不一样,所以按实际长度动态分配空间。也可以从根出发，遍历整棵哈夫曼树，求得各个叶子结点所表示的字符的哈夫曼编码。//--------------无栈非递归遍历哈夫曼树,求哈夫曼编码HC=(HuffmanCode)malloc((n+1)*sizeof(char*));p=m;cdlen=0;for(i=1;i=m;++i)HT[I].weight=0;{While(p){If([HT[p].weight==0){HT[p].weight=1;If(HT[p].lchild!=0){p=HT[p].lchild;cd[cdlen++]=“0”}elseif(HT[p].rchild==0){HT[p].weight=2;If(HT[p].rchild!=0){p=HT[p].rchild;cd[cdlen++]=”1”;}}else{HT[p].weight=0;p=HT[p].parent;--cdlen;}}//----------------------------以下是译码部分--------------#includemy.h//译码函数voidDecodeing(HFMCC){FILE*in,*out;inti,j,k,c_max,c_len,dq,dq_len,flag,error=0;//error初始状态为假charcode[MAXLEN_1],a[MAXLEN],zw[MAXLEN];code[0]='\0';//打开文件codefile.dat，读取编码正文写入内存，存入数组codeif((in=fopen(codefile.dat,r))!=NULL){fscanf(in,%s,code);}else{printf(\n打开文件错误!);return;}fclose(in);//求编码正文长度c_lenfor(i=0;code!='\0';i++);c_len=i;if(c_len==0)error=1;//错误情况1//求编码库最长编码长度c_maxc_max=0;for(i=0;i{for(j=0;C.code[j]!='\0';j++);if(c_maxc_max=j;}//进行译码dq=0;//dq用来记录code数组的读取位置k=0;//k用来记录zw数组读取位置while(dq{flag=1;dq_len=c_max;for(i=dq,j=0;ja[j]=code;a[j]='\0';while(flag&&!error)//若无错误且flag为1则继续循环{for(i=0;i{if(strcmp(a,C.code)==0){zw[k]=C.data;k++;flag=0;break;}}//若找到编码库里匹配的编码，则结束循环if(flag){dq_len--;a[dq_len]='\0';}//未找到则将当前长度减一，继续寻找if(dq_len1)error=1;//译码错误情况2}dq=dq+dq_len;//编码正文当前读取位置改变}zw[k]='\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))!=NULL)fprintf(out,%s,zw);else{printf(\n打开文件错误!);return;}fclose(out);printf(\n译码成功!);}}————————以下内容摘自《基于改进哈夫曼编码的数据压缩方法研究》。张红军，徐超目前的哈夫曼编码方式是通过对构造好的哈夫曼树进行自下向上的方式实现数据编码，该方式有一些可以待改进之处[2,3]：在算法的时间复杂度上，如果定义叶子节点所在的层次为第1层，其父节点为第2层，依次类推，处在第n层上的节点要被扫描n-1次，在程序运行过程中存在着许多指针移动，其时间复杂度为O(n2)。在数据压缩中，哈夫曼编码是一种变长编码，采用的是一种优化静态编码方法。具有以下不足：（1）需要事先知道输入码字符集的频率分布，在不同的数据文件中，不同字符出现的频率不同。（2）需要对原始数据块扫描两次：第一次是统计原始数据中各符号出现的频率并排序，利用得到的频率值创建哈夫曼树并将树的有关信息保存起来，便于解压时使用；第二次是进行编码，根据前面得到的哈夫曼树对原始数据进行编码，并将编码信息存储起来，便于存储和传输。如果将这种方法用于数据的网络通信中．两遍扫描势必会引起较大的延时，两次扫描所引发的低效率不容忽视；同时，如果用于文件数据的压缩中，重复扫描增加了磁盘访问，额外的磁盘访问将会降低该算法的数据压缩速度，从而降低压缩效率。本算法用二叉树层次遍历方式，利用队列（Queue）对整棵哈夫曼树进行一次扫描，即可得到各节点的哈夫曼编码。在本结构体中，除了包含节点的编码信息域及权值之外，还应包含该节点所对应的排序码key，指向其右右孩子的指针left和right，指针其双亲结点的指针parent，具体设计如下：Typedefstructnode*BT;Structnode{chardate,key[10];Intweight;Structnode*left,*right,*parent;};本算法采用循环队列，head指向队头节点，tail指向队尾节点，numbers表示当前队列中节点的个数，queuelist[]是表示队列的数组。Typedefstructcircle{inthead,tail;intnumbers;BTqueuelist[size];};算法描述改进算法从哈夫曼的根节点出发，通过利用队列，按照层次遍历的方法依次对树中每个叶子节点进行编码。算法执行过程如下：（1）根据字符集｛c1,c2,…,cn｝和相应的权值集{w1,w2,…,wn}建立相应的哈夫曼树，并将哈夫曼树的根节点入队；（2）当队列为非空时，递归执行以下操作：a．指针p指向当前队头节点；b.若当前队头节点无双亲节点，表示该节点为根节