科学研究
嗨 与赋
浅析基于哈夫曼树与哈夫曼编码的数据压缩 李玮琦 (达州职业技术学院四川达州 6 3 5 0 0 1 )
摘要:哈夫曼编码作为一种最常用的不等长无损压缩编码方法,在数据压缩程序中具有非常重要的应用。本文是基于哈夫曼树与哈弗曼编码的数据压缩算法。 关键词:哈夫曼树哈弗曼编码数据压缩算法
1 9 5 1年,正在麻省理工学院求学的哈夫曼需要完成一份学期报告,导师 Ro b e r t M. F a n o给他们的学期报告的题目是,寻找最有效的二进制编码。哈
哈夫曼编码的算法实现所采用的方法是从叶子节点向上遍历到根结 点,从哈夫曼树根结点开始,左孩子路径标示为0,右孩子路径标示为 1,一直
夫曼在研究过已有编码后发现,始终无法证明哪个编码是最有效的,因此他很快放弃了这些研究而进行了新的探索,最后他终于突破了现有编码的算法,发现了基于有序频率二叉树编码,哈夫曼使用了一种自底向上的方法来构建二叉树,这一方法很快被证明是最有效的。 在实际应用中,我们也通常要考虑如何设计一棵二叉树,使得执行路径最短,即算法的效率最高,而这正是哈夫曼所研究的最有效二进制编码,因 此最优二叉树又被称为哈夫曼树。 哈夫曼树的定义哈夫曼树,是指对于一组带有确定权值的叶结点,构造的具有最小带权路径长度的二叉树。所谓结点带权路径长度,指的是从根结点到某个结点的 一
到达叶子结点为止,然后将从树根沿每条路径到达叶子结点的代码排列起来,便得到了哈夫曼编码。 四、基于哈夫曼树与哈夫曼编码的数据压缩算法所谓数据压缩,目的在于对需要压缩的数据文件进行可逆编码,使编码的长度小于原数据的长度,通过对哈夫曼编码的研究,我们认识到只要给定字符的概率分布,哈夫曼编码算法能够计算出代码,对于给定概率分布的无前缀代码,产生的编码可以很好的达到数据压缩目标。 . 在哈夫曼编码算法中,编码过程是从叶子结点出发寻找从叶子到根的路径,而译码过程则是从根结点出发,按照0或1确定访问子结点的路径,直到叶结点,从而求得对应的字符。 文件由若干个字节组成,~个字节有8 b i t s,故有2 8= 2 5 6种字节构成形式,对应字节码为0— 2 5 5。按此2 5 6种字节出现频率可构造h a
f r n a n树进行重新编码,编码后每字节的新编码平均长度将<= 8 b i t s,将每个字节对应了压缩编码写到新文件中,从而达到压缩文件的目的。我们可以采用如下步骤实现基于哈夫曼编码的数据压缩算法: 1扫描源文件所有数据,并统计文件中每个字符出现的频率。 2 .以每个字符与频率组合建立二叉树结点。 3 .建立哈夫曼树
、
路径长度与该结点所带的权值的乘积,而树的带权路径长度则指的是树中 ’ _ C1…
所有叶子结点的带权路径长度之和,通常记作: WP L=夕 L k k= l
假设有n个权值{ Wl, W2,……, wn},试构造有n个叶子结点的二叉树, 每个叶子结点拥有一个权值w,则其中带权路径长度WP L最小的二叉树, 称为最优二叉树或哈夫曼树。 二、哈夫曼树的建立
根据哈夫曼树的定义,哈夫曼树的构造方法如下: 1 .根据给定的n个权值 ( wl, W2,……, Wn 1构成1 2棵二叉树的集合F= f T1, T 2,……, T n},其中每一棵二叉树T i中只有一个带权为Wi的根结点, 其左右子树均空。
4 .将哈夫曼树信息写入输出文件,以各解压缩使用。 5 .再度扫描源文件,将源文件的数据生成对应哈夫曼编码,写入到输出 文件。对文件做标示,最终完成源文件的压缩。 上面这一算法是根据经典的哈夫曼编码思想引出,压缩时首先扫描源
2 .在F中选出两棵根结点权值最小的树作为一棵新的二叉树的左右子树,且置新二叉树根结点的权值为两棵子树根结点的权值之和。 3 .从F中删去这两棵树,同时把新二叉树加入F中 4 .重复2和3,直到F中只有一棵树为止,此树便是哈夫曼树。 从哈夫曼树的构造方法,我们可以推导出构造哈夫曼树的算法实现原理:基于哈夫曼树没有度为1的结点,根据二叉树性质,可推导知一棵有n个叶子的哈夫曼树共有2 n - 1个结点,我们可定义大小为2 n - 1的一维数组存储哈夫曼树。这个数组的前n个位置存放的为已知的叶子结点,后( n一 1 )个位置存放的为动态生成的树内结点。在算法的大循环过程中,就是根据位置i 前面的已知结点找出结点权值最小的两个结点,然后根据这两个结点构造 出位置i的新的父结点,即一棵新树的根结点。 三、哈夫曼编码
文
件,根据源文件中数据出现频率生成字符频率表,据此构造哈夫曼树并生成长短不~的编码,再将哈夫曼编码写入压缩文件,对文件做出标示后完成压缩过程,解压缩时只要逆转编码过程即可。 这样的压缩算法能够以较高压缩率完成文件的压缩,不过分析算法步骤后发现,这一算法有明显缺陷,在于需要对源文件进行两次扫描,第一次扫描目的在于统计并建立频率表,以便解压缩使用,第二次扫描目的在于得到哈夫曼编码。如果源文件较大,扫描两次所引发的低效率不容忽视,同时重复扫描也增加了磁盘访问,再次降低压缩效率。 因此我们需要改进和优化基于哈夫曼编码的压缩算法,分析前述算法, 我们找到效率的瓶颈在于哈夫曼树的建立方式,如果我们能够动态建立哈夫曼树,那么对于源文件的扫描就无需两遍,从而带来效率的提高。 那么应当如何构建动态变化的哈夫曼树呢?我们可以考虑从如下角度入手:即动态哈夫曼编码树的建立过程中,第i+ 1个字符的编码由原始数据中前i个字符所建立的哈夫曼树为依据进行。如何动态建立哈夫曼树,关键
哈夫曼树的一个经典应用就是哈夫曼编码。在数据传输与存储中,经常需要将不同形式的信息转换成二进制字符串,这个转换过程就是编码。在实际应用中,信息的各个字符出现频率是不一样的,有的字符出现频率高,有的字符出现频率低,为了降低所传递信息的编码长度,通常做法是用短的编
码来表示高频率字符,用长的编码来表示低频率字符。哈夫曼编码就是这样种经典编码,哈夫曼编码的优点是任一字符c i的编码不会是另一字符c j ( c i c j )的编码的前缀,这样电文在译码时不会出现混淆。 哈夫曼编码是一种变长的编码方案,编码过程就根据不同字符的频率 一
在于如何将前i个字符所建立的哈夫曼树调整为前i+ 1个字符所建立的哈夫曼树,这一关键问题有待进一步研究和思考。一 参考文献
(相当于权值 )构造出哈夫曼树,然后求叶子节点到根节点的路径,其中节点的左孩子路径标识为0,右孩子路径标识为1。
【 1】朱怀宏.吴楠 .夏黎春,利用优化哈夫曼编码进行数据压缩的探索 o】,微机发展, 2 0 0 2 ( ̄0 5期) [ 2]蔡茂蓉.姜龙.丁光辉.杨文辉,哈夫曼树的实现及其在文件压缩中的应用o],现代计算机(专业版), 2
0 0 8 (第1 1期)
9

统计出原始数据中的每个字符 出现的频率 ,第二遍是建立哈夫曼树并进行哈夫曼 编码 ,经过编码后的文本文件 , 主要包含 2 个部分 : Huffm an 码表部分和压缩...
基于哈夫曼编码的数据压缩解压程序论文_信息与通信_工程科技_专业资料。合肥学院...- 22 -2- 一、需求分析 1.1 课程设计目的将理论教学中涉及到的知识点贯穿...
基于哈夫曼编码的文本文件压缩分析与研究薛向阳 ( 渭南职业技术学院, 渭南 714000) 摘 要 数据压缩在信息迅速 增长的时代显得越来越重要, 信息在存储、 传输等 ...
哈夫曼树与哈夫曼编码_IT/计算机_专业资料。哈...对图像数据进行编码,可以 图像处理 实现图像文件压缩... 2014教师资格材料分析辅... 2014小学教师资格考试...
数据结构-哈夫曼树和哈夫曼编码_电脑基础知识_IT/计算机_专业资料。6.8 哈...【分析】 由完全二叉树的定义可知,对于k层的完全二叉树,其上 的k-1层是一...
哈夫曼树与哈夫曼编码 201100814*** 计科 111 *** 第 1 页 数据结构实验...2、实验上要写出多批测试数据的运行结果。 3、结合运行结果,对程序进行分析。 ...
在分析了实验要求和算法分析之后,将程序分为四个功能函 数,分别如下: 首先建立一个哈夫曼树和哈夫曼编码的存储表示: typedef struct { int weight; int parent,...
的哈夫曼编码作用为地址码 的子点阵数据 字形 以供输出 采用哈夫曼树压缩 通过...分析 所不同 示 那么 由概 利用哈夫曼树可以方便地构造自动实现汉字字形压缩还...
"" # ( " & 利用优化哈夫曼编码进行数据压缩的...和 *即可得到哈夫曼编码。 由于哈夫曼树中没有度...下面对这种高效的算法作详细的分析, 为了便于 说明,...
11 1 哈夫曼编码译码 哈夫曼编码译码一、 需求分析在当今信息爆炸时代, 如何...,以哈夫曼树—即 最优二叉树,带权路径长度最小的二叉树,经常应用于数据压缩...
热门文档