文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 自然科学 > 数学 > 自适应Huffman编码算法研究
侵权投诉

自适应Huffman编码算法研究

·196·

价值工程

自适应Huffman编码算法分析及研究

AnalysisandResearchonAdaptiveHuffmanCoding

彭文艺PENGWen-yi

(华中科技大学武昌分校,武汉430064)

(HuazhongUniversityofScienceandTechnologyWuchangBranch,Wuhan430064,China)

摘要:Huffman编码作为一种高效而简单的可变长编码常用于信源编码。但现有的Huffman编码算法存在效率不高,同时应用受

到一些限制,因此,提出一种自适应Huffman编码算法,该算法与其他的Huffman编码相比效率更高,应用范围更广。

Abstract:Huffmancoding,asanefficientandsimplevariablelengthcoding,isusedinsourcecoding.ButtheexistingHuffmancodingalgorithmefficiencyisnothigh,butapplicationisalsolimited,therefore,thispaperproposesanadaptiveHuffmancodingalgorithm,thisalgorithmwithotherHuffmanencodingcomparedwithhighefficiency,wideapplicationrange.

关键词:数据压缩;Huffman编码;自适应Huffman编码Keywords:datacompression;Huffmancoding;adaptiveHuffmancoding中图分类号:TP39文献标识码:A文章编号:1006-4311(2012)35-0196-03

0引言

如何采用有效的数据压缩技术在信息科学领域发挥着重要的作用,Huffman编码在数据压缩技术中得到了广泛的应用,笔者对Huffman编码的原理和存在的不足进行探讨,并在此基础上提出了自适应Huffman编码方法,从而解决Huffman编码的不足。

1Huffman编码的原理和构造过程

Huffman编码是1952年由Huffman提出的一种比较常用的变长编码方法,其主导思想是根据数据符号发生的概率进行编码。在数据中出现概率越高的符号,相应的码长越短;出现概率越低的符号,其码长越长,从而达到用尽可能少的码符号表示源数据。Huffman编码需对原始数据进行两遍扫描,第一遍统计原始数据中各字符出现的频率,由此创建Huffman树并将其有关信息保存起来,以便解压时使用;第二遍则根据所得到的Huffman树对原始数据进行编码,并将编码信息保存起来。创建Huffman树的过程如下:

①根据源数据符号出现的概率,求出各个符号出现的权值{W1,W2,…Wn}构成n棵二叉树的集合F={T1,T2…Tn},其中每棵二叉树Ti中只有一个带权为Wi的根结点,其左右子数为空。

②在F中选取两棵根结点的权值最小的树作为左右子树构造一新的二叉树,设置新二叉树的根结点的权值为左、右子树上根结点权值之和。

③在F中删除所选取的两棵子树,同时将构成得到新二叉树加入到F中。

④重复②、③直到F中只包含一个二叉树为止,这棵树便是Huffman树。

以abcddbb为例作为待编码的原始数据符号。首先,统计出a、b、c、d四个字符在表1原始数据中各

字符出现的权重原始数据中出现的概率(权

符号

自适应Huffman编码算法研究

abcd重),结果如表1所示。

权重1312根据上述Huffman树构———————————————————————

作者简介:彭文艺(1977-),男,湖北广水人,工程硕士,华中科技

“abcddbb”原始数据构造的Huffman树的过程造过程,对

如图1~4所示。

大学武昌分校计算机与电子系(讲师),主要研究方向为计算机算法。

从Huffman编码的根结点出发,经右子树、左子树、左子树三步,到达包含字符a的叶结点,获得a字符的二进制编码:100。从根结点出发,经过左子树前进一步,就到达包含字符b的叶结点,获得b字符的二进制编码为:0,类似可得到c字符的二进制编码为:101,d字符的二进制编码为11,abcddbb的编码结果为:1000101111100。

这种Huffman编码算法进行编码时,必须进行两次扫描,第一次扫描统计字符出现的概率(权重),并据此进行构造Huffman树;第二次扫描是按Huffman树的字符进行编码。在存储和传输Huffman编码时,必须先存储和传输Huffman树,在实际应用系统中它有很大的局限性,特别在诸如通信等实时传输、处理的系统中,更不允许这种两次处理过程。因此,为改进该编码算法,提出了自适应Huffman编码方案。

2自适应Huffman编码原理和构造过程在叙述自适应Huffman编码之前,必须给每个结点引入两个新属性:结点编号和所属块。结点编号是一个全局唯一值,不同的结点拥有不同的点编号,而所属块是指具有相同权重的一组结点。其中结点编号需要具有以下特征:

①权重越大的结点,结点编号越大。②父结点的编号总是大于子结点的编号。以上两点成为兄弟属性。

自适应Huffman编码的过程主要包括Huffman树初始和Huffman树更新。

第1页

你可能喜欢

  • 编码译码huffman
  • huffman编码
  • huffman算法
  • 编码解码huffman
  • huffman树进行编码解码算法
  • 香农编码huffman

热门文档

相关文档

  • 【论文】基于C语言的自适应Huffman编码算法分析及实现...

    基于C语言的自适应Huffman编码算法分析及实现研究_专业资料。通过C语言程序,动态统计信源符号概率,逐步构造Huffman编码树,实现了自适应Huffman编码,解决了静态编码树不...

  • 【论文】基于查找表的自适应Huffman编码算法

    基于VC++的Huffman编码算... 49人阅读 1页 0.50 G.729自适应码书搜索算法... 29人阅读 4页 2.00基于查找表的自...

  • 基于C语言的自适应Huffman编码算法分析及实现研究

    静态 Huffman 编码算法给出的编码树构造方法, 2期 文国知: 基于 C 语言的自适应 Huffman 编码算法分析及实现研究 55 56 武 汉 工 业 学 院 学 报 2011 ...

  • 基于查找表的自适应Huffman编码算法

    2011 V ol 16 N o 5 基于查找表的自适应 H uf fman 编码算法雒 莎 , ...: Huffman 压缩编码作为一种高效而简 单的可变长编码而被广泛应用于信源编码。...

  • Huffman编码算法实现

    实验一一、实验目的 Huffman 编码算法实现 1、加深对压缩理论和技术的理解; 2、增进对压缩编码算法的设计和编写能力; 3、掌握 Vc++和 Huffman 编码。 二、实验...

  • Huffman编解码及其快速算法研究

    2自适应Huffman编码 上述的Huffman编码是利用压缩对象出现频率的 不等性进行编码的一种常用的无损数据压缩方法。不 论从算法的复杂度还是在实现的难度以及对数据压缩...

  • 【论文】基于VC++的Huffman编码算法设计及实现

    基于VC++的Huffman编码算法设计及实现_专业资料。本文介绍了Huffman编码原理,并给出算法设计和用VC++语言程序实现编码的方法.专题研究 ZHU AN TI YAN J IU ...

  • 静态图像自适应编码的一种实现方法

    一种基于自适应网络卷积编... 暂无评价 6页 免费 Huffman编码的一种实现方法...一种自适应压缩编码算法[ J] . 华南理工大学学报. 李人厚, 张平安. 精通 ...

  • Quake3 自适应Huffman 编码

    Quake3 自适应Huffman 编码_IT/计算机_专业资料。Quake3 自适应Huffman 编码 本文介绍quake3 源代码中的huffman.c 文件,该源代码实现了自适应Huffman 算法。源...

  • Huffman编解码及其快速算法研究

    Huffman编解码及其快速算法研究Huffman编解码及其快速算法研究隐藏>> 信号处理 李...2 自适应 Huff man 编码 图3 解码树 ( 2) 在结点集中选取两棵根结点的...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email