Huffman算法的分析与应用

2009 NO.28|中国科教创新导刊理论前沿China Education Innovation HeraldHuffman算法的分析与应用牛雷婷1.2(1.聊城教育学院(聊城大学东昌学院)电子科学系山东聊城252000; 2.山东科技大学信息科学与工程学院山东青 岛.266510)摘要:在目前的信息科学领域,数据压鳊技术占有重要地住，而Huffman算法在数据压缩场合的应用甚为广泛。除此之外，Huffman算法在数据库系统及网络通信等领域发挥着越来越重要的作用，究其原因,主要是由于通过Huffman算法可实现存储结构、编码方式及最小权值的选择,从而获得明显的压蝙效果。关键词:Huffman算法数据压鳊 分析应用中图分类号:G642文献标识码: A文章编号:1673-9795(2009)10(a)-0087-01信息科学领域中数据压缩技术发挥着种无损压缩,可对压缩后的数据进行安全重要作用，通过数据压缩，可使文件所占存.恢复,它不仅可缩小文件的存储空间,还可储空间变小，更重要的是,它可使模块间的四以提高模块间的数据交换速度,因而有着数据交换速度大大提高。数据压缩的主要特别广泛的应用范围.针对不同的应用场任务是采用不等长的二进制码去缩短文件⑦合,赫夫曼树中叶子结点的权值对应不同中出现频率高的字符,从而减少不必要的的意义,如利用Huffman算法可实现最佳的空间浪费,而Huffman算法是利用二叉树去自白判定过程,此时权值是作为字符或符号出构造前缀编码,它按照权值大小去选择两现的频率存在的,而在面对排序问题时,权个最小结点组成子树，重复组树从而最终图3值又被视为序列长度值。除此之外，建成一棵新的带权路径长度最小的二叉Huffman算法还可应用于数据传送、视频信树。因此在目前的数据压缩领域,Huffman号压缩等领域。算法的应用越来越广泛，除此之外，例2:用Huffman算法对文件内容进行Huffman算法在信息检索系统、数据库系压缩.统、网络通信等场合也有着广泛的应用。压缩过程可分以下三步:(1)计算文件中数据的出现频率,以此构造赫夫曼树,并1 Huffman算法简介对数据进行编码;(2)在上步的基础上,将数1.1 Huffman算法的定义据译为赫夫曼编码;(3)不同数据对照不同所谓Huffman算法,是由赫夫曼(D.A.要求进行数据压缩,最终完成对所有文件Huffman)在1952针对构造带权路径长度内容的压缩。WPL最小的二叉树而给出的带有一般规律图4以"verygood"8个字符为例，按照上述的算法.即设有n个权值{ W1, W2, ..Wn},步骤，可将字符个数最终压缩到3个字符，构造一棵有n个叶子叶子的二又树,每个叶2 存在的问题及改进措施而重复的字符个数越多,压缩比例就会越子结点带有权值Wi,且带权路径长度WPL 2.1 存在的问题方。在上述Huffman算法描述的第(2)步中,1.2 Huffman算法的算法描述选取权值最小的两个结点作为左右子树组4结语(1)根据给定的n个权值{W1, W2,..成新的二叉树,形成新的结点,此时若出现学习数据结构的目标之一便是能将Wn}构成n棵二叉树的集合F={T1,T2,-,多个权值相同的结点,按上述算法描述则Huffman算法 灵活运用,这看似简单，但真Tn},其中每棵二叉树Ti中只有一个带权为不能解决此问题,因为若单纯按照规定去正实现需要结合数据结构中的其他算法，Wi的根结点,其左右子树均空。构遣新二叉树,则由于根结点权值相同的应 首先掌握Huffman算法的基本原理，了解(2)在F中选取两棵根结点的权值最小多棵子树 ，深度却不同,选择不同子树所得Huffman算 法的应用领域，从而为能最终灵的树作为左右子树构造一新的二叉树,置的新二叉 树的深度也是不相同的。因而,同活运用该算法打好 基础。新二叉树的根结点权值为其左、右子树上样一组待编码元素可能构建出多棵深度和.根结点的权值之和。结构都不相同的赫夫曼树。参考文献(3)在F中删除这两棵树，同时将得到的2.2 改进措施[1]严蔚敏,吴伟民.数据结构(C语言版)M].新二叉树加入到F中。由以上描述可知,在选取权值最小的清华大学出版社,2008.(4)重复(2).(3)至F只含一棵树为止,这两个结点构造新二叉树过程中,一旦遇到[2] 韩俊英，韩虎.Hufman算法的分析与改棵树便是赫夫曼树。多个结点权值相同的情况,选择结点不同，进[J]. 兰州铁道学院学报，2003(6).例1:给定一组权值{8,7,4,1}构造赫夫最终构造的赫夫曼树也不同，如此将 [3] 王文莉. Huffman算法的实现[J].郑州铁曼树。Huffman算法应用到不同场合时,便无法取路职业技术学院学报, 2005(6).分析:按上述Huffman算法构造赫夫曼得 预期效果.由此可将Huffman算法完善改[4] 杨利华,李娟,彭永康.哈夫曼算法的改树图示如图1-4. .进如下:进与应用[J].电脑知识与技术,2005第(1).(3). (4)步保持不变,第(2)步改(11).⑧⑦④➊为:在F中选取两棵根结点的权值最小的树作为左右子树构造- .新的二叉树，当存在.图1多棵子树根结点的权值相同的情况时,选取深度小的子树用于构造新的新二叉树的根结点权值为其左中国煤化工TYHCNMHG.3 Huffman算法的应用图2Huffman算法是数据压缩场合中的一中国科教创新导刊China Education Innovation Herald87