基于改进哈夫曼编码的数据压缩方法研究

第36卷第5期2014年9月Vol.36No.5JournalofTangshanTeachersCollegeSep.2014──────────收稿日期：2014-04-10作者简介：张红军（1979-），男，河南平舆县人，硕士，讲师，研究方向为网络与多媒体技术。-40-计算机科学与技术基于改进哈夫曼编码的数据压缩方法研究张红军，徐超（安阳师范学院人文管理学院，河南安阳455000）摘要：作为一种无损压缩编码方法，哈夫曼编码在数据压缩中具有重要的应用。经典的哈夫曼编码是在构造哈夫曼的基础上自下而上进行的，通过分析哈夫曼算法的思想，给出了一种改进的哈夫曼数据压缩算法。该算法利用队列结构，从哈夫曼的根节点出发，向叶子节点进行编码，在编码过程中仅将哈夫曼树的每个叶子节点进行一次扫描便可以得到各个叶子节点的哈夫曼编码。实验表明，改进算法不仅压缩率高于以往算法，而且保证了最终生成的压缩文件的安全性。关键词：哈夫曼编码；哈夫曼算法；改进；数据压缩中图分类号：TP312文献标识码：A文章编号：1009-9115(2014)05-0040-04DOI：10.3969/j.issn.1009-9115.2014.05.015ResearchofDataCompressionMethodBasedontheImprovedHuffmanCodeAlgorithmZHANGHong-jun,XUChao(CollegeofHumanisticandManagement,AnyangNormalUniversity,Anyang455000,China)Abstract:Asanon-losingcompressingcodingalgorithm,Huffmancodinghasmanyimportantapplicationtothecurrentdatacompressionfield.TheclassicalgorithmtogetHuffmancodingisfrombottomtotoponthebasisoftheHuffmantree.ThispapergivesanimprovedHuffmanalgorithmofdatacompressionbytheanalysisoftheHuffmanalgorithm,inwhichalgorithmgofromtherootnodetoleafnodesoftheHuffmantreebyusingthequeuestructure.Inthecodingprocess,everyleafnodeisonlyscannedoncebeforegettingtheHuffmancoding.Theexperimentalresultshowsthefactthattheimprovedalgorithmnotonlythecompressionratioishigherthanclassicalgorithm,butalsoensurethesecurityandconfidentialityoftheresultingcompressed.KeyWords:Huffmancoding;Huffmanalgorithm;improve;datacompression在互联网时代，在数据通信传送和下载中，媒体数据（包括视频媒体和音频媒体等）采用数字化的格式，大量的数据资源给存储器的存储容量、通信信道带宽和计算机处理速度带来很大的负担，但因当前科学技术发展有限，很多硬件技术还无法完全满足计算机存储资源的需求，与带宽之间差距还很大，仅靠通过增加存储容量、扩充信道容量以及提高计算机处理速度等方法来解决这个问题还有一定难度，这就需要考虑压缩。压缩的关键技术在于设计合理的编码技术，如果在计算机通信数据传输过程中，根据各字符在电文中出现的频率的高低，采用变长的二进制位表示，出现频率高的字符则编码较短，出现频率低的则编码较短的原则对报文字符重新进行编码，从而使原本很长的电文代码大大缩短，得到平均长度最短的电文编码，使报文在存储和传输中，存储空间降低，信息传输效率提高，实现压缩目的[1]。计算机数据编码方式有哈夫曼编码、限定长度变化编码、算法编码等。作为一种无损数据压缩编码，哈夫曼编码广泛应用于文本、图像、视频压缩、通信数据传输、密码等信息压缩编码标准中。但目前的哈夫曼编码方式是通过对构造好的哈夫曼树进行自下向上的方式实现数据编张红军，等：基于改进哈夫曼编码的数据压缩方法研究-41-码，该方式有一些可以待改进之处[2,3]：在算法的时间复杂度上，如果定义叶子节点所在的层次为第1层，其父节点为第2层，依次类推，处在第n层上的节点要被扫描n-1次，在程序运行过程中存在着许多指针移动，其时间复杂度为O(n2)。针对以上问题，本文设计出一种改进的哈夫曼编码方式，它不仅可实现从树的根节点向叶子节点的编码，而且可以使编码的时间复杂度降低为O(n)，从而节省了程序的执行时间，达到了高效压缩的目的。1哈夫曼编码与数据压缩理论哈夫曼编码是DavidHuffman于1952年提出的一种编码方法，其理论基础是根据字符出现的频率值来构造出一棵哈夫曼树，利用该哈夫曼树来设计平均长度最短的前缀编码，从而实现用最短的编码表示最常用的数据块或出现频率最高的数据。因其编码效率最接近或达到100%，有时又称为最佳编码，通常应用在数据通信、数据传送以及对数据的压缩处理等方面。1.1数据压缩数据压缩是一种对原始的数据进行一系列的再次编码，这样可以消除掉原始数据中多余的数据，可以把数据量减低到最小，从而达到压缩处理计算机上图像、音频以及视频等各种媒体数据的目的。一般来说这种技术的产生是因为多媒体数据的量太大，很容易对计算机的存储造成负担，对网络的传输带来不便，如果按照帧的速率为25帧/秒，那么1s传输的数据量也只有25MB左右，用640MB的光盘进行存贮也只能存放仅仅25s的动态画面，因此需要对其进行数据压缩，压缩后的文件和数据到需要时通过解压或者还原，通过对数据的冗余进行很大程度的压缩，才更有可能方便计算机的存贮和传输[4]。常见的压缩方法有无损压缩方法和有损压缩方法。无损压缩方法是压缩后的数据经解压缩还原后，得到数据与原始数据是完全一样的，是一种基于信息原理的可逆编码方法。无损压缩方法常用的有游程编码、基于字典编码技术的LZW算法和基于哈夫曼编码原理的压缩算法[5]。1.2哈夫曼树哈夫曼树（Huffman的音译，又叫赫夫曼、霍夫曼），是由n个带权叶子结点构成的所有二叉树中带权路径长度WPL最小的二叉树，是一种带权路径长度最短的树，又叫最优二叉树。1.3哈夫曼树算法的构造过程（1）根据给定的n个权值{w1,w2,…,wn}对应的n个结点，构造n棵只有根结点的二叉树，n棵二叉树构成了二叉树的森林F={F1,F2,…,Fn}。（2）在森林F中选取两棵根结点权值最小的二叉树作为左、右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左、右子树根结点权值之和。（3）从森林F中删除被选中的两棵树，同时将新得到的二叉树加入森林F中。（4）重复（2）、（3）两步，直到森林中只含有一棵二叉树为止，此时得到的这棵二叉树即为哈夫曼树。例如，给定权值集合为w={5，2，7，10，4，18，32，22}，可以构造如下图1所示的哈夫曼树。图1哈夫曼树的构造1.4哈夫曼编码算法哈夫曼编码算法基本思想：以每个电文的使用频率为权值构造哈夫曼树，然后在构造好的哈夫曼树约定：叶结点表示电文字符，向左的分支（即左子树）用0表示，向右的分支（即右子树）用1表示，从根结点开始，沿线到达各频度电文字符的叶子结点，所经过的分支代码序列就构成了相应频度电文的哈夫曼编码。利用哈夫曼算法，可以设计出最优的前缀编码[6]。1.5哈夫曼编码的构造例，电文字符集{a,b,c,d,e,f,g,h}出现的频度分别为{10,4,2,5,7,18,32,22}，其哈夫曼编码构造如图2所示。图2哈夫曼编码的构造1.6现有编码的弊端在数据压缩中，哈夫曼编码是一种变长编码，采用的第36卷第5期唐山师范学院学报2014年9月-42-是一种优化静态编码方法。具有以下不足：（1）需要事先知道输入码字符集的频率分布，在不同的数据文件中，不同字符出现的频率不同。（2）需要对原始数据块扫描两次：第一次是统计原始数据中各符号出现的频率并排序，利用得到的频率值创建哈夫曼树并将树的有关信息保存起来，便于解压时使用；第二次是进行编码，根据前面得到的哈夫曼树对原始数据进行编码，并将编码信息存储起来，便于存储和传输。如果将这种方法用于数据的网络通信中．两遍扫描势必会引起较大的延时，两次扫描所引发的低效率不容忽视；同时，如果用于文件数据的压缩中，重复扫描增加了磁盘访问，额外的磁盘访问将会降低该算法的数据压缩速度，从而降低压缩效率[7]。2改进的哈夫曼编码算法本算法用二叉树层次遍历方式，利用队列（Queue）对整棵哈夫曼树进行一次扫描，即可得到各节点的哈夫曼编码。2.1数据结构设计在本结构体中，除了包含节点的编码信息域及权值之外，还应包含该节点所对应的排序码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];};2.2算法描述改进算法从哈夫曼的根节点出发，通过利用队列，按照层次遍历的方法依次对树中每个叶子节点进行编码。算法执行过程如下：（1）根据字符集｛c1,c2,…,cn｝和相应的权值集{w1,w2,…,wn}建立相应的哈夫曼树，并将哈夫曼树的根节点入队；（2）当队列为非空时，递归执行以下操作：a．指针p指向当前队头节点；b．若当前队头节点无双亲节点，表示该节点为根节点，将该根节点出队（Dequeue），并让其左孩子节点和右孩子节点先后入队（Enqueue）；c．若当前节点有双亲节点，则给其左、右孩子节点分别赋值为父节点的哈夫曼编码，然后，若此节点为其父节点的左孩子，则在其父节点所赋给的编码后面加一个“0”，若此节点为其父节点的右孩子，则在其父节点所赋给的编码后面加一个“1”；由于根节点无编码，可以直接分别得到“O”，“1”作为自己的编码；d．队头节点出队；若出队节点有左右孩子节点，则让其左右孩子分别入队，若出队节点没有左右孩子节点，转向e；e．判断当前队列是否为空，若为空则编码工作完成。编码过程如图3所示。图3(a)表示一棵已经建好但还未进行编码的二叉树。图3(b)表示对根节点的孩子进行编码。图3(c)表示先将B节点的编码“0”赋给其孩子节点D和E，而D是B的左孩子，故在编码“0”的后面加“0”，E是B的右孩子节点，故在编码“0”的后面加“1”；同理，将C节点的编码“1”赋给其孩子节点F和G，而F是C的左孩子，故在编码“1”的后面加“0”,G是C的右孩子节点，故在编码“1”的后面加“1”；图3(d)表示先将D的编码“00”赋给其孩子节点H和I，H是D的左孩子，故在编码“00”后面加“000”，I是D的右孩子，故在编码“00”后面加“001”。（a）编码前的哈夫曼树（b）给第3层节点编码（c）给第2层节点编码（d）给第1层节点编码图3编程过程示意图2.3算法具体实现流程开始；将根节点入队列；判断队列是否为空；如果为空，则转向j；指针q指向队头节点；张红军，等：基于改进哈夫曼编码的数据压缩方法研究-43-判断q是否为根节节；如果是根节点，则转向h；否则复制其父节点的编码信息；判断该节点是父节点的左孩子还是右孩子；如果是左孩子，则在复