文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 电子/电路 > 基于查找表的自适应Huffman编码算法
侵权投诉

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

Huffman压缩编码作为一种高效而简单的可变长编码而被广泛应用于信源编码。但现有的Huffman编码算法普遍存在着效率不高的问题,因此,提出一种自适应查找表Huffman编码算法。该算法对数据进行编码的依据是动态变化的表,对于首次出现的字符使用“KEY”的码字进行编码,将“KEY”下移,等待下一个首次出现的字符。与其他算法相比,改进算法Huffman编码的效率得以提高。

2 1年 9月 01 第1 6卷第 5期

西安邮电学院学报 J OUR L OFX’ N UNI R I Y O P TSA NA IA VE ST F OS ND TE E OMMUNI A ONS L C C TI

Sp 0 1 e .2 1 V 11 o 5 o. 6N .

基于查找表的自适应 H f n编码算法 u ma f 雒莎, 葛海波 (.西安邮电学院通信与信息工程学院, 1陕西西安 7 0 2;.西安邮电学院电子工程学院, 1 1 12陕西西安 70 2) 1 1 1

摘要: f n压缩编码作为一种高效而简单的可变长编码而被广泛应用于信源编码。但现有的 Huf n编码算 Hu ma f ma法普遍存在着效率不高的问题,因此,出一种自适应查找表 Huf n编码算法。该算法对数据进行编码的依据提 f ma 是动态变化的表,于首次出现的字符使用“ E的码字进行编码,“ Y”移,待下一个首次出现的字符。对 K Y”将 KE下等

与其他算法相比,改进算法 Huf n编码的效率得以提高。 f ma 关键词:查找袁; f n编码;If a树 Huf ma Iuf n - m 中图分类号: N9 1 T l文献标识码: A文章编号:0 7 3 6 (0 1 0—0 7—0 1 0— 2 42 1 )5 0 6 4

Huf n编码是一种无损压缩的变长度编码。 f ma

主要有静态 Huf n编码、态 Huf n编码等。 f ma动 f ma 静态编码压缩率高,缺点是压缩时间长;动态 Huf f -

1 Huf n编码原理 fma Huf n编码是一种变长度编码方法,方法 f ma此

ma n编码压缩时间短,压缩率相对于静态 Huf n f ma 编码较低[。]

需要知道字符出现的概率,以字符出现的概率为根据,产生字符的码字,符出现的概率高,字则码字短。 反之,码字长。这样就实现很好的压缩效果。则 Huf n编码算法为每一个符号提供一个包含了 f ma这个符号和概率值的叶结点,图 1如。

自适应 Huf n编码就是对第+1个字符进 f ma行编码,根据原数据中前£字符得到的 Huf是个 f - ma n树来进行的。自适应 Huf n编码克服传统 f ma Huf n编码必须对文本进行扫描两遍的缺点, f ma压缩效率大幅度提高[6

。它的缺点就是对第一次出 4] _

现的字符进行编码的同时修改 H f a树, uf n必须保 m存这些压缩过程中的 Huf a f n树, m以方便解码。 Hahmi se a n方法的查找表 Huf n编码,面增长 f ma单

图 1叶结点概率值

先按照概率从小到大对字符进行排列,将两个最前边的叶结点安排在同一个父结点下,父结点的概率值等于两个子结点的概率值之和。而 S 1和 S 2 结为兄弟结点,图 2如。

树以r的大小分区。将稀疏的单面增长树分成子树集,它们的高度不大于 r而不是为整个单面增长树,建立一个大表,为每个分开的子树建立一个查找表。 为子组织设置的子树建立一个总表[。 7。 。但是,此 方法需要先扫描一遍被压缩文件,知道字符的总量, 对所有的字符进行编码,后进行压缩。为克服以然 上编码方法的缺点,出了基于查找表的自适应提

o o o o o 图 2父结点概率值

Huf n编码, f ma此方法克服了自适应编码需要存储编码过程中的 Hu f n树和基于查找表的单面增 f ma 长树需要提前扫描的缺点。 收稿日期:0 1 6 0 2 1—0— 9

将父节点作为新的叶节点,次按照概率进行再排列,前边两个叶节点重复进行连接。例如,边将上

作者简介:雒

莎( 9 7)女, 1 8一,硕士研究生,研究方向:线阵 C E ma:0 5 2 7@q .o葛海波( 9 3)男, A D, - i 4 6 3 6 0 q cm l 16一,教授,硕士,

研究方向:高频电路。

、

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

第1页

你可能喜欢

热门文档

相关文档

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