文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 哈夫曼编码的一种基于树型模式匹配的改进型算法
侵权投诉

哈夫曼编码的一种基于树型模式匹配的改进型算法

一般情况下,哈夫曼编码所采用的存储结构及构树方法,不仅影响编码效率,而且也没充分利用存储空间.本文改顺序存储为链式存储,对叶结点和非叶结点采用不同的存储结构来降低空间复杂度.在编码时,充分利用短码字且基于树型模式匹配进行编码,提高了编码性能和传输效率.

维普资讯 doc.guandang.net

第2 7卷第 1期 Vo. 7 12 No .1

西华师范大学学报 (自然科学版 ) Ju a o hn s N r l nvri N trl c n e) o r l f iaWet oma U iesy( a a S i cs n C t u e

20 0 6年 3月 M a. 0 6 r2 0

文章编号:0 182 ( 06 0 -0 40 10—20 2 0 ) 1 7 -5 0

哈夫曼编码的一种基于树型模式匹配的改进型算法 刘晓锋,亚娟吴 (华师范大学计算机学院,西四川南充 67 0 30 2)

摘要:一般情况下,哈夫曼编码所采用的存储结构及构树方法,不仅影响编码效率,而且也没充分利用存储空 间.本文改顺序存储为链式存储,对叶结点和非叶结点采用不同的存储结构来降低空间复杂度 .编码时,分利在充

用短码字且基于树型模式匹配进行编码,提高了编码性能和传输效率 . 关键词:哈夫曼树;哈夫曼编码;树型模式匹配;算法

中图分类号: P 0 . T 3 16

文献标识码: A

1引言 与计算机相关的任何一个应用领域几乎都涉及到编码的概念 .码的主要目的是使数据便于计算机处编理及高效率传输 .哈夫曼编码是由哈夫曼于 15 92年最早提出的一种基于统计模型的非等长的编码方案,它

主要用在数据压缩和加密等应用场合.尤其在知道信源中各字符出现的频率的情况下,它不失为一种优秀的编码方案, M E 2的视频电视信号的压缩处理.如 P G一

2哈夫曼编码的传统算法 哈夫曼编码本身并不复杂,是一种基于贪心算法自下而上构造最优前缀码的过程 .其基本思想是根据信

源中待编码字符出现的频率(或概率 )的大小构造一棵最优二又树.构造一棵最优二叉树是基于如下定理. 定理 1在变长编码中, 对以较大概率出现的字符赋于较短的编码,而对较小概率出现的字符赋于较长的编码,即按照各字符出现的概率由小到大分别赋于由长到短的编码,则编码结果平均码长小于其他任何编 码方式所得到的平均码长 . 证明 (用反证法 ) f n)示信源 S中某字符 a采设 ( i表出现的频率,为其编码长度,平均码长为厶则

L=; f n)按定理中描述, L * C .对任意两个不同字符 n和 a, i若有 L>,, n),

n) 工且 (< (,成立,则平均码长

L=; L

n)最小 (如图 1 a )现作出如下反面假设:工且f ) f )如图 1 b )平均码长为 ().厶> C > C,时( n n (),

工,时有L< .图 1示.此 L如所 现对两平均码长作差,有工一L= C L+ C f L, fⅡ) L - C,工. fⅡ) f。) - C‘ ‘ fⅡ), 由图 1 6可得,=,=所以有 () L L, L,

工一L= ( i工+。)工一 ( i L - ( 工= 厂Ⅱ) f f i,Ⅱ) i fⅡ),

f n)— + ( )工一 ) L一 )f )一 ( )> . C ( L), ( =( (C/, n) 0 a .

所以有L>这与假设的结论L<Z矛盾.以假设不成立. - . ' - '所

根据定理 1整个编码过程就是,,首先确定信源中所有编码信号出现的概率形成一个码表,对经常出现 收稿日期:05—1—1 20 1 O

基金项目:华师范大学校级科研基金资助项目(4 0 1西 0A 2 )

作者简介:刘晓锋( 9 2一)男, 17,重庆石柱人,西华师范大学计算机学院硕士研究生,研究方向为并行算法理论与研究、网 格计算及基于网络的计算机应用 .

哈夫曼编码的一种基于树型模式匹配的改进型算法

第1页

你可能喜欢

热门文档

相关文档

  • 哈夫曼树实验报告

    2、 关键算法的时间、空间复杂度 关键算法 1:统计...也就是说,实际是哈夫曼树的 另一种组成编码方式。...实际上,还可以 通过模式匹配,根据定义好的编码表,...

  • 【论文】哈夫曼编码的另一种实现算法

    传统哈夫曼编码借助树形结构构造,算法实现时使用链表或静态链表结构,空间的每个结点内有左、右子树、双亲指针。本文给出了哈夫曼编码的另一种实现算法,该算法抛开树...

  • 哈夫曼编码

    太原科技大学 毕业设计 哈夫曼编码器的实现 信息与计算科学 081801 王乐琦 200818030123 摘 要 Huffman 编码是一种可变长编码方式,是二叉树的一种特殊转化形式。它...

  • 一种基于自顶向下的哈夫曼编码方法

    陕 西省科 技项 目2o0oo2) 本算法采用对二 叉树进 行层 次遍 历 的方式 ,用 利 队列对整个二叉树进 行一 次扫描 , 即可得到 节点 的哈 夫曼编码 。...

  • 基于哈夫曼编码的图像压缩技术研究

    关键词 哈夫曼编码;二叉树;熵;无损压缩 1. 前言 哈夫曼编码是一种常用的压缩编码算法,采用变长码编码,属于无损压缩算法的一 种,在无损压缩的编码范畴中,哈...

  • 一种易于硬件实现的快速自适应哈夫曼编码算法

    自适应哈夫曼编码由于良好的实用性,特别适用于通信系统等对速度要求高的场合,为此提出一种新的自适应哈夫曼编码算法。自适应哈夫曼编码由于良好的实用性,特别适用...

  • 一种基于自顶向下的哈夫曼编码方法

    5.期刊论文 刘晓锋.吴亚娟.LIU Xiao-feng.WU Ya-juan 哈夫曼编码的一种基于树型模式匹配的改进型算法 -西华 师范大学学报(自然科学版)2006,27(1) 一般情况...

  • 【论文】哈夫曼编码应用的一种改进——范式哈夫曼编码

    本文主要介绍一种改进方法——范式哈夫曼编码及译码算法,以解决其应用的不足。维普资讯 http://www.cqvip.com T技术 哈夫曼 编码 应用的 一种 改进 邵 天增 ...

  • 浅谈哈夫曼编码

    由此可见,哈夫曼编码的码长是变化的,对于出现频率高的信息,编码的长度 较短;而对于出现频率低的,编码长度较长。 生成霍夫曼编码算法基于一种称为“编码树”(...

  • 一种高速精确单模式串匹配算法

    一种改进的多模式串匹配算... 6页 5财富值 串的模式匹配算法 21页 免费 ... 高性能精确单模式串匹配算... 82页 2财富值 哈夫曼编码与译码 5页 1财富...

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