动态哈夫曼编码的改进
《动态哈夫曼编码的改进》由会员分享,可在线阅读,更多相关《动态哈夫曼编码的改进(6页珍藏版)》请在装配图网上搜索。
1、动态哈夫曼编码的改进 计算机世界月刊1994年7月号所登载的动态哈夫曼编码的数据压缩方法一文给出了一种实时性较强的数据压缩方法,该方法的最大特点是不需预先对原始数据进行一遍扫描以建立哈夫曼树,而改为以动态变化的哈夫曼树对数据编码。 该文所附的动态哈夫曼编码数据压缩与解压源程序中的UpDate函数是动态修改哈夫曼树的关键部分,该函数对动态哈夫曼树的一种可能情况无法正确修改,针对这一点,本文附上对该函数的一个修正定义,以使该压缩与解压程序更加完善。 以下就举例说明原UpDate函数无法正确修改的一种哈夫曼树。例如若要压缩“TThhis”字符串,则在压缩完“TTh”之后的动态哈夫曼树为图所示(设根结
2、点序号为1000): 04A07700.GIF;图 压缩完“TTh”之后的动态哈夫曼树 此时若再将字符h进行压缩编码,则在输出h的编码“01”后需调整哈夫曼树,以997号叶结点为当前结点,则与当前结点具有同样重量的且序号最大的结点为998号结点,而该结点是997号结点的父结点,对二者按原文所提供的UpDate函数进行交换,则将导致998号结点变成叶结点,996号结点变成997号结点的左孩子,997号结点则既为自己的父结点又是自己的右孩子,这样在对后继字符i进行压缩编码时,首先就无法输出996号空结点的编码了,此时压缩程序陷入死循环。 显然这时可以简单地将998和997号结点的重量加1,然后以9
3、98号结点的父结点为当前结点进行调整,根据这种思想对原文提供的UpDate函数进行修正所得新的UpDate函数附后。 void UpDate(struct Node *Temp) struct Node * Tempa, * Tempc, * Pointer; struct LeafNode *p,*q,*b; unsigned char Letter; while(Temp!=Root) if(Temp-Weight) P=Weight; while(p-Next-CharNode-Weight !=Temp-Weight) p=p-Next; if(Temp-Front!=NULL) Te
4、mpa=Temp; while(Temp-Front !=NULL) Temp=Temp-Front; if(Temp=Tempa-Parent) Tempa-Weight+; Tempa-After=Tempa-Front=NULL; Temp-After=NULL; InsertWeight(Tempa); else Pointer=Temp-LeftChild; if(Pointer !=NULL) Pointer-Parent=Tempa; Temp-LeftChild=Tempa-LeftChild; if(Temp-LeftChild !=NULL) Temp-LeftChild-
5、Parent=Temp; Tempa-LeftChild=Pointer; Pointer=Temp-RightChild; if(Pointer !=NULL) Pointer-Parent=Tempa; Temp-RightChild=Tempa-RightChild; if(Temp-RightChild !=NULL) Temp-RightChild-Parent=Temp; Tempa-RightChild=Pointer; Letter=Temp-Letter; Temp-Letter=Tempa-Letter; Tempa-Letter=Letter; if(Tempa-Left
6、Child=NULL)&(Tempa-RightChild=NULL) b=leaf; while(b!=NULL) if(b-CharNode=Temp) b-CharNode=Tempa; break; else b=b-Next; if(Temp-LeftChild=NULL)&(Temp-RightChild+NULL) b=Leaf; while(b!=NULL) if(b-CharNode=Tempa) b-CharNode=Temp; break; else b=b-Next; p-Next-CharNode=Temp-After; if(Temp-After=NULL) q=p-Next; p-Next=q-Next; free(q); else Temp-After-Front=NULL; Temp-Weight+; Temp-After=Temp-Front=NULL; InsertWeight(Temp); Temp=Temp-Parent; 第 6 页 共 6 页
- 温馨提示:
1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。