動(dòng)態(tài)哈夫曼編碼的改進(jìn)--

1、動(dòng)態(tài)哈夫曼編碼的改進(jìn) -                         計(jì)算機(jī)世界月刊1994年7月號所登載的動(dòng)態(tài)哈夫曼編碼的數(shù)據(jù)壓縮方法一文給出了一種實(shí)時(shí)性較強(qiáng)的數(shù)據(jù)壓縮方法，該方法的最大特點(diǎn)是不需預(yù)先對原始數(shù)據(jù)進(jìn)行一遍掃描以建立哈夫曼樹，而改為以動(dòng)態(tài)變化的哈夫曼樹對數(shù)據(jù)編碼。該文所附的動(dòng)態(tài)哈夫曼編碼數(shù)據(jù)壓縮與解壓源程序中的UpDate函數(shù)是動(dòng)態(tài)修改哈夫

2、曼樹的關(guān)鍵部分，該函數(shù)對動(dòng)態(tài)哈夫曼樹的一種可能情況無法正確修改，針對這一點(diǎn)，本文附上對該函數(shù)的一個(gè)修正定義，以使該壓縮與解壓程序更加完善。以下就舉例說明原UpDate函數(shù)無法正確修改的一種哈夫曼樹。例如若要壓縮“TThhis”字符串，則在壓縮完“TTh”之后的動(dòng)態(tài)哈夫曼樹為圖所示(設(shè)根結(jié)點(diǎn)序號為1000)：04A07700.GIF;圖 壓縮完“TTh”之后的動(dòng)態(tài)哈夫曼樹此時(shí)若再將字符h進(jìn)行壓縮編碼，則在輸出h的編碼“01”后需調(diào)整哈夫曼樹，以997號葉結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)，則與當(dāng)前結(jié)點(diǎn)具有同樣重量的且序號最大的結(jié)點(diǎn)為998號結(jié)點(diǎn)，而該結(jié)點(diǎn)是997號結(jié)點(diǎn)的父結(jié)點(diǎn)，對二者按原文所提供的UpDa

3、te函數(shù)進(jìn)行交換，則將導(dǎo)致998號結(jié)點(diǎn)變成葉結(jié)點(diǎn)，996號結(jié)點(diǎn)變成997號結(jié)點(diǎn)的左孩子，997號結(jié)點(diǎn)則既為自己的父結(jié)點(diǎn)又是自己的右孩子，這樣在對后繼字符i進(jìn)行壓縮編碼時(shí)，首先就無法輸出996號空結(jié)點(diǎn)的編碼了，此時(shí)壓縮程序陷入死循環(huán)。顯然這時(shí)可以簡單地將998和997號結(jié)點(diǎn)的重量加1，然后以998號結(jié)點(diǎn)的父結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)進(jìn)行調(diào)整，根據(jù)這種思想對原文提供的UpDate函數(shù)進(jìn)行修正所得新的UpDate函數(shù)附后。void UpDate(struct Node *Temp)struct Node * Tempa, * Tem

4、pc, * 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;

5、if(Temp=Tempa->Parent)Tempa->Weight+;Tempa->After=Tempa->Front=NULL;Temp->After=NULL;InsertWeight(Tempa);elsePointer=Temp->LeftChild;if(Pointer !=NULL)Pointer->Parent=Tempa;Temp->LeftChild=Tempa->LeftChild;if(Temp->LeftChild !=NULL)Temp->LeftChild->Paren

6、t=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->

7、;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

8、->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; 作者：劉飛 孫揚(yáng)聲