動態哈夫曼編碼的改進

動態哈夫曼編碼的改進

　 《計算機世界月刊》1994年7月號所登載的《動態哈夫曼編碼的數據壓縮方法》一文給出了一種實時性較強的數據壓縮方法，該方法的最大特點是不需預先對原始數據進行一遍掃描以建立哈夫曼樹，而改為以動態變化的哈夫曼樹對數據編碼。
該文所附的動態哈夫曼編碼數據壓縮與解壓源程序中的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函數附后。
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;
}
}

【動態哈夫曼編碼的改進】相關文章：

漢字的動態編碼與顯示方案08-06

LHARC中的動態限長編碼壓縮算法08-06

針對硬件實現的H.264視頻編碼算法改進08-06

嵌入式零樹小波編碼及其改進算法的研究08-06

動態的歷史與動態的歷史教學08-07

Video Object編碼技術08-06

視音頻素材的編碼轉換08-06

《數字編碼》教學反思04-28

曼巴精神作文12-20