动态哈夫曼编码的改进
BAIDU_CLB_singleFillSlot("10979"); 《计算机世界月刊》1994 年 7 月号所登载的《动
态哈夫曼编码的数据压缩方法》一文给出了一种实时性较强的数据压缩方法，该方法的最
大特点是不需预先对原始数据进行一遍扫描以建立哈夫曼树，而改为以动态变化的哈夫曼
树对数据编码。该文所附的动态哈夫曼编码数据压缩与解压源程序中的 UpDate 函数是动
态修改哈夫曼树的关键部分，该函数对动态哈夫曼树的一种可能情况无法正确修改，针对
这一点，本文附上对该函数的一个修正定义，以使该压缩与解压程序更加完善。中国论文
联盟 编辑。以下就举例说明原 UpDate 函数无法正确修改的一种哈夫曼
树。例如若要压缩“TThhis”字符串，则在压缩完“TTh”之后的动态哈夫曼树为图所示(设根结
点序号为 1000)：@@;图 压缩完“TTh”之后的动态哈夫曼树@@此时若再将
字符 h 进行压缩编码，则在输出 h 的编码“01”后需调整哈夫曼树，以 997 号叶结点为当前
结点，则与当前结点具有同样重量的且序号最大的结点为 998 号结点，而该结点是 997
号结点的父结点，对二者按原文所提供的 UpDate 函数进行交换，则将导致 998 号结点变
成叶结点，996 号结点变成 997 号结点的左孩子，997 号结点则既为自己的父结点又是
自己的右孩子，这样在对后继字符 i 进行压缩编码时，首先就无法输出 996 号空结点的编
码了，此时压缩程序陷入死循环。显然这时可以简单地将 998 和 997 号结点的重量加 1
，然后以 998 号结点的父结点为当前结点进行调整，根据这种思想对原文提供的 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){Tempa=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->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->LeftChild==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;}}转贴于中国论文联盟
