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

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

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

维普资讯 doc.guandang.net

7 6

西华师范大学学报 (自然科学版 )

20 06年

具有与 P中非叶子节点部分完全相同. 因此,了和上面“为结构相容’区别,们引入“构基本相容” !相我结的概念 .棵目标子树与一个模式 P“一结构基本相容”是指具有与 P中非叶子节点部分形状相同 (不, 但

要求对应节点的具体内容相同)的结构, P中的叶子节点与中相应部分(且 可能是叶子节点,也可能是子 树 )相容”所以上例中目标,和 T和模式 P: o (p表示任意符号 )构基本相容.“ . 3 x py o 结

4哈夫曼编码的改进型算法 由以上分析可得,若由权值最小的两个结点合并成新结点时,其权值大于或等于其他任意两个 (或多 个)结点的权时,得到的哈夫曼树的高度最低,所哈夫曼编码效果最好 .一方面,夫曼编码的一般作法是另哈

分两步,先构造哈夫曼树,再进行哈夫曼编码.如果在构造哈夫曼树的同时就进行哈夫曼编码,就将大大提高算法效率.为此对常规算法作出如下改进. 4 1充分利用短编码及存储结构的改进 .

要降低哈夫曼树的高度,就应该充分利用短编码,在有很多与合并之后得到的权值相等时尤其如此.为 此对算法的前期工作作出如下调整:

首先,按所有信源符号出现的概率由小到大排序,到信源符号的概率序列{。P, P}其中P≤得 P,:…,, 。 p2…罨 p -≤

然后选择前面两个最小的

进行合并,设合并之后得到的概率和为 P,在 ( P,,中找到第一假则 P,… P )

个大于 p的值 P, i现在就把 p放在 P的位置, P至 P往后平移一个位置. i而 通常采用顺序存储结构来存放 这些概率值,这会导致大量的元素移动而降低效率,方便元素的插入和删除操作,而改为链式存储.相应结构 定义如下: t p d fsr c u f s y e e t th f i u i t

{ l nT p eg Ee ty ew i me h;

i g/标志结点是叶结点或非叶结点 n t;/ ta sr c uf o e jne t tu th fn d I x; E

} ufi; H f s Lt

另外,哈夫曼编码时,无须对所有结点进行编码,只对哈夫曼树中非叶子结点进行编码即可,因为叶结点是共享非叶结点的 (图 3所示 )只对口 bc如,,,和 d4个结点编码,样既减少了编码结点的个数又缩短编码的长度 .且在 这而存储时对叶结点和非叶结点区别对待会降低存储空间复杂度 (相应的结构定义如下所示 )但是在合并时, .可能是非叶结点和非叶结点 (叶结点 )间进行之合并,一个队列来保存这些已被合并而得的非叶结点,用由合并的顺序保证从

O

。

图 3只对非叶结点编码 F g3 i. Huf n c dn f f ma o igo

队首到队尾的元素的权值依次递增.如果在进行合并时有非叶结点参与就从队列中取出队首元素即可.因此得到如下算法思想:当前得到的两个权值最对

No .e fn d s n. a o e 1

小的结点(自单链表中)。 P,来 P和:它们是否叶结点有以下 3种情况: 1都为叶结点:2都为非叶结点: () () () 3一个叶结点和一个非叶结点.对第一种情况,分配两个 La类型结点存放其权值而作为哈夫曼树的叶结 ef点,再分配一个 N tef o a类型结点存放其合并后的权值作为两个 L a类型结点的父亲而成为哈夫曼树的非 L e f 叶结点,然后把该非叶结点进入队列保存 (图 4 b d )同时插入单链表中相应位置;如 (,),对第二种情况,配分 一

个 N te类型结点,队列中取出队首的两个元素分别作该 N tef型结点的左孩子和右孩子 (图 4 oLa f从 oLa类如

(,), f )然后合

并所得新权值进入单链表和对应结点进入队列保存(图 4 h )对第三种情况, g如 ();叶结点按 第一种情况来操作,非叶结点按第二种情况来操作即可 . 4就是用该算法思想于上例来构树的整个过程 .图 tp d fsr c t a y e e t t u Nol f e t p d fsr c e y e e t t a u lf

{ l nTp eg; Ee tyew i me h

{ l nTp eg: Ee tyew i me h

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

上一页第3页

你可能喜欢

热门文档

相关文档

  • 哈夫曼树实验报告

    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