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

動(dòng)態(tài)哈夫曼編碼的改進(jìn) 《計(jì)算機(jī)世界月刊》1994年7月號(hào)所登載的《動(dòng)態(tài)哈夫曼編碼的數(shù)據(jù)壓縮方法》一文給出了一種實(shí)時(shí)性較強(qiáng)的數(shù)據(jù)壓縮方法，該方法的最大特點(diǎn)是不需預(yù)先對(duì)原始數(shù)據(jù)進(jìn)行一遍掃描以建立哈夫曼樹，而改為以動(dòng)態(tài)變化的哈夫曼樹對(duì)數(shù)據(jù)編碼。
該文所附的動(dòng)態(tài)哈夫曼編碼數(shù)據(jù)壓縮與解壓源程序中的UpDate函數(shù)是動(dòng)態(tài)修改哈夫曼樹的關(guān)鍵部分，該函數(shù)對(duì)動(dòng)態(tài)哈夫曼樹的一種可能情況無法正確修改，針對(duì)這一點(diǎn)，本文附上對(duì)該函數(shù)的一個(gè)修正定義，以使該壓縮與解壓程序更加完善。
以下就舉例說明原UpDate函數(shù)無法正確修改的一種哈夫曼樹。例如若要壓縮“TThhis”字符串，則在壓縮完“TTh”之后的動(dòng)態(tài)哈夫曼樹為圖所示(設(shè)根結(jié)點(diǎn)序號(hào)為1000)：
@@04A07700.GIF;圖 壓縮完“TTh”之后的動(dòng)態(tài)哈夫曼樹@@
此時(shí)若再將字符h進(jìn)行壓縮編碼，則在輸出h的編碼“01”后需調(diào)整哈夫曼樹，以997號(hào)葉結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)，則與當(dāng)前結(jié)點(diǎn)具有同樣重量的且序號(hào)最大的結(jié)點(diǎn)為998號(hào)結(jié)點(diǎn)，而該結(jié)點(diǎn)是997號(hào)結(jié)點(diǎn)的父結(jié)點(diǎn)，對(duì)二者按原文所提供的UpDate函數(shù)進(jìn)行交換，則將導(dǎo)致998號(hào)結(jié)點(diǎn)變成葉結(jié)點(diǎn)，996號(hào)結(jié)點(diǎn)變成997號(hào)結(jié)點(diǎn)的左孩子，997號(hào)結(jié)點(diǎn)則既為自己的父結(jié)點(diǎn)又是自己的右孩子，這樣在對(duì)后繼字符i進(jìn)行壓縮編碼時(shí)，首先就無法輸出996號(hào)空結(jié)點(diǎn)的編碼了，此時(shí)壓縮程序陷入死循環(huán)。
顯然這時(shí)可以簡單地將998和997號(hào)結(jié)點(diǎn)的重量加1，然后以998號(hào)結(jié)點(diǎn)的父結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)進(jìn)行調(diào)整，根據(jù)這種思想對(duì)原文提供的UpDate函數(shù)進(jìn)行修正所得新的UpDate函數(shù)附后。
void UpDate(struct Node *Temp)
{
struct Node * Tempa, * Tempc, * Pointer;
struct LeafNode *p,*q,*b;
unsigned char Letter;
while(Temp!=Root)
{
if(Temp-

【動(dòng)態(tài)哈夫曼編碼的改進(jìn)】相關(guān)文章：

計(jì)算機(jī)畢業(yè)論文-動(dòng)態(tài)哈夫曼編碼的改進(jìn)03-06

漢字的動(dòng)態(tài)編碼與顯示方案03-18

針對(duì)硬件實(shí)現(xiàn)的H.264視頻編碼算法改進(jìn)03-18

2.4Kbps MELP低速率語音編碼技術(shù)研究與改進(jìn)03-30

Tunstall編碼與自適應(yīng)編碼算法03-07

Video Object編碼技術(shù)01-07

視音頻素材的編碼轉(zhuǎn)換03-19

自適應(yīng)算術(shù)編碼的FPGA實(shí)現(xiàn)03-18

對(duì)于緊致碼在三種編碼方法下的編碼特性研究03-19