【动态哈夫曼编码的改进】哈夫曼编码

该文所附的动态哈夫曼编码数据压缩与解压源程序中的UpDate函数是动态修改哈夫曼树的关键部分，该函数对动态哈夫曼树的一种可能情况无法正确修改，针对这一点，本文附上对该函数的一个修正定义，以使该压缩与解压程序更加完善。

以下就举例说明原UpDate函数无法正确修改的一种哈夫曼树。例如若要压缩“TThhis”字符串，则在压缩完“TTh”之后的动态哈夫曼树为图所示(设根结点序号为1000)：

@@04A07700.GIF;图压缩完“TTh”之后的动态哈夫曼树@@

此时若再将字符h进行压缩编码，则在输出h的编码“01”后需调整哈夫曼树，以997号叶结点为当前结点，则与当前结点具有同样重量的且序号最大的结点为998号结点，而该结点是997号结点的父结点，对二者按原文所提供的UpDate函数进行交换，则将导致998号结点变成叶结点，996号结点变成997号结点的左孩子，997号结点则既为自己的父结点又是自己的右孩子，这样在对后继字符i进行压缩编码时，首先就无法输出996号空结点的编码了，此时压缩程序陷入死循环。

显然这时可以简单地将998和997号结点的重量加1，然后以998号结点的父结点为当前结点进行调整，根据这种思想对原文提供的UpDate函数进行修正所得新的UpDate函数附后。

voidUpDate(structNode*Temp)

{

structNode*Tempa,*Tempc,*Pointer;

structLeafNode*p,*q,*b;

unsignedcharLetter;

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;

peak;

}

elseb=b->Next;

}

}

if((Temp->LeftChild==NULL)&&(Temp->RightChild++NULL))

{

b=Leaf;

while(b!=NULL)

{

if(b->CharNode==Tempa)

{

b->CharNode=Temp;

peak;

}

elseb=b->Next;

}

}

}

}

p->Next->CharNode=Temp->After;

if(Temp->After==NULL)

{

q=p->Next;

p->Next=q->Next;

free(q);

}

elseTemp->After->Front=NULL;

}

Temp->Weight++;

Temp->After=Temp->Front=NULL;

InsertWeight(Temp);

Temp=Temp->Parent;

}

}

作者：刘飞孙扬声

推荐访问： 编码 改进 动态 哈夫曼 哈夫曼编码树 求哈夫曼编码