【文章內(nèi)容簡介】 T 結點。要對49號結點執(zhí)行權值“加一操作”，但49號結點不具有所在塊中的最大結點編號，因此需要先與50號結點進行交換位置操作。步驟51(47)0NYT(45)1c(46)1b(48)2(50)1a(49)3(51)新的50號結點權值加一。對51號結點執(zhí)行權值“加一操作”。步驟63(51)2(50)1(45)1(47)1a(49)1b(48)1c(46)0NYT(43)1a(44)輸入符號：d輸出編碼：100d使用包含新NYT結點和字符d結點的子樹，替換舊的NYT 結點。將要對47號結點執(zhí)行權值“加一操作”，但47號結點不具有所在塊中的最大結點編號，因此需要先與49號結點進行交換位置操作。步驟74(51)2(50)2(49)1(45)1c(46)1a(47)1b(48)0NYT(43)1d(44)新的49號結點權值加一。對51號結點執(zhí)行權值“加一操作”。步驟84(51)2(50)2(49)1(45)1c(46)1a(47)1b(48)0NYT(43)1d(44)輸入符號：d輸出編碼：001將要對44號結點執(zhí)行權重值“加一操作”，但44號結點不具有所在的塊中的最大結點編號，因此需要先與48號結點進行交換位置操作。步驟95(51)3(50)2(49)1(45)1c(46)1a(47)2b(48)0NYT(43)1d(44)新的48號結點權值加一。對50號結點執(zhí)行權值“加一操作”。對51號結點執(zhí)行權值“加一操作”。步驟105(51)3(50)2(49)1(45)1c(46)1a(47)2d(48)0NYT(43)1b(44)輸入符號：b輸出編碼：001將要對44號結點執(zhí)行權重值“加一操作”，但44號結點不具有所在的塊中的最大結點編號，因此需要先與47號結點進行交換位置操作。步驟116(51)3(50)2(47)1(45)1c(46)1b(49)2d(48)0NYT(43)1a(44)新的47號結點權值加一。對50號結點執(zhí)行權值“加一操作”。對51號結點執(zhí)行權值“加一操作”。步驟125(51)3(50)2(47)1(45)1c(46)1b(49)2d(48)0NYT(43)1a(44)輸入符號：b輸出編碼：10將要對47號結點執(zhí)行權值“加一操作”，但47號結點不具有所在塊中的最大結點編號，因此需要先與49號結點進行交換位置操作。步驟131a(44)0NYT(43)1c(46)2d(48)3b(49)2(47)1(45)4(50)7(51)新的49號結點權值加一。對51號結點執(zhí)行權值“加一操作”。 通過觀察以上步驟，容易發(fā)現(xiàn)動態(tài)哈夫曼編碼的幾個特征：(1) 在步驟13 得到的編碼樹與靜態(tài)哈夫曼編碼樹基本相同，除了NYT節(jié)點和符號a節(jié)點組成的子樹替代了靜態(tài)哈夫曼編碼樹中的符號a 的葉節(jié)點之外；(2) 在每一次輸入新的符號之前，編碼樹都處于完整可用的正常狀態(tài)；(3) 同一個輸入符號，可能產(chǎn)生多種不同的輸出。例如三次輸入的符號b，產(chǎn)生的輸出分別為0b、001 和10；(4) 同樣的輸出結果，可能由不同的輸入產(chǎn)生。例如第二次輸入的符號d 與第二次輸入的符號b，都產(chǎn)生了001 作為輸出結果。這些特征首先說明了動態(tài)哈夫曼編碼樹與靜態(tài)哈夫曼編碼樹等同，完全符合哈夫曼樹的定義。同時，由于每一個輸入符號都對編碼樹產(chǎn)生了影響，因此解碼過程無法從哈夫曼編碼數(shù)據(jù)流的某一個中間位置開始進行，而必須從頭至尾逐bit 處理。由于動態(tài)哈夫曼編碼算法采用了先編碼，后調(diào)整編碼樹的方案，相應的解碼算法比較簡單。解碼算法也使用僅有唯一的NYT 節(jié)點的編碼樹作為初始狀態(tài)，然后根據(jù)哈夫曼編碼數(shù)據(jù)流，對符號進行還原。每次處理完一個符號，就使用這個符號調(diào)整編碼樹。這樣，在每一次輸入新的符號之前，哈夫曼樹都處于與進行編碼時使用的哈夫曼樹完全相同的狀態(tài)，保證了解碼的正確性。 利用動態(tài)哈夫曼編碼壓縮與還原圖像的C語言實現(xiàn) 數(shù)據(jù)結構typedef struct tree {int leaf[SYMBOL_COUNT ]。int next_free_node。struct node {unsigned int weight。int parent。int child_is_leaf。int child。} nodes[NODE_TABLE_COUNT ]。} TREE。 其中l(wèi)eaf[SYMBOL_COUNT ]指明每個字符在哈夫曼樹中葉子結點的位置，它被初始化為1；next_free_node 指明首次出現(xiàn)的字符插入哈夫曼樹中的位置；weight 指明每個結點的權值；parent 指明該結點的父結點位置；child_is_leaf 指明該結點是否是葉子結點，若是則置child_is_leaf = 0；若不是則置child_is_leaf = 1；child指明該結點是葉結點，則葉子上存放字符的值，否則指明該結點左孩子的位置，其右孩子的位置是child+1；NODE_TABLE_COUNT =( SYMBOL_COUNT * 2 ) 1。結點符號有258 種可能的取值, 0到255 表示真實的字節(jié)值，256指文件結束標志，257表示空葉結點，用NYT(not yettransmitted)表示，它有兩重含義：其一在編碼流中代表其后跟隨的8 bit 不再是編碼，而是一個新的符號；其二內(nèi)存中的NYT 結點代表新結點的插入位置。故定義END_OF_STREAM的值為256，定義NYT的值為257，定義SYMBOL_COUNT的值為258。 壓縮的實現(xiàn)(1) 壓縮算法流程圖 首先，初始化哈夫曼樹，然后，對每一個字符進行兩種操作：編碼，更新哈夫曼樹，當遇到符號END_OF_STREAM時，結束。具體實現(xiàn)過程如圖33所示：圖33 動態(tài)哈夫曼壓縮流程圖(2) 代碼實現(xiàn)詳見附錄：3．動態(tài)哈夫曼編碼對圖像壓縮的實現(xiàn)代碼 解壓縮的實現(xiàn)(1) 解壓流程圖 首先，初始化哈夫曼樹，然后，對每一個字符進行兩種操作：解碼，更新哈夫曼樹，直到符號END_OF_STREAM。具體實現(xiàn)過程如圖34所示：圖34 動態(tài)哈夫曼解壓縮流程圖(2) 實現(xiàn)代碼詳見附錄：4．動態(tài)哈夫曼編碼對圖像解壓的實現(xiàn)代碼 圖像壓縮實例對于第二章壓縮的圖像，利用上述算法壓縮后，大小為999KB。運行界面如圖35所示：圖35 ，無失真，運行界面如圖36所示：圖36 靜態(tài)哈夫曼編碼與動態(tài)哈夫曼編碼的比較 如前所述,靜態(tài)哈夫曼編碼的缺點在于需對原始數(shù)據(jù)進行兩遍掃描。第一遍掃描統(tǒng)計字符出現(xiàn)頻率并建樹，第二遍掃描根據(jù)所建哈夫曼樹進行編碼。由此，在壓縮時，將會降低壓縮速度。同時，為保存哈夫曼樹以供解壓時用，也將浪費一部分存儲空間。由于靜態(tài)建樹，其壓縮率也有所下降。動態(tài)哈夫曼 編碼對數(shù)據(jù)的壓縮是依據(jù)動態(tài)變化的哈夫曼編碼樹，亦即對第i+1個字符的編碼是由原始數(shù)據(jù)中前i個字符所建立的哈夫曼樹確定。壓縮和解壓子程序具有相同的初始化樹，每處理完一個字符，壓縮和解壓縮使用相同的算法 更新哈夫曼樹，不必為解壓而保存哈夫曼樹的有關信息，從而大大提高了壓縮率。但是，由于動態(tài)哈夫曼編碼算法在解壓時采用與壓縮時相同的方法建樹，增加了解壓時間，從而降低了還原速度。而靜態(tài)哈夫曼編碼由于對哈夫曼樹進行保存，還原時不必重新建樹,節(jié)省了還原時間。 下面給出靜態(tài)哈夫曼編碼和動態(tài)哈夫曼編碼在圖像壓縮中的比較，如表32所示。表32 靜態(tài)哈夫曼編碼和動態(tài)哈夫曼編碼在圖像壓縮中的比較文件名采用的編碼算法壓縮前的大小壓縮后的大小壓縮比壓縮時間解壓縮時間(16 色位圖)動態(tài)哈夫曼234KB40 KB靜態(tài)哈夫曼234KB (24 位位圖) 動態(tài)哈夫曼999kB靜態(tài)哈夫曼 由上表可以看出，當圖像容量小時，雖然利用動態(tài)哈夫曼 編碼算法壓縮圖像，不用保存哈夫曼 樹，從而大大提高了壓縮比，但是針對圖像的特點，大量的時間消耗在了更新編碼樹上，這樣卻延長了壓縮時間和解壓縮時間；當圖像容量大時，一定程度上提高了壓縮比，而且縮短了壓縮時間，但又延長了解壓縮時間。所以在第4 章中將對哈夫曼 編碼進行改進，使得這種無損壓縮方法更加實用。第四章 對哈夫曼編碼的改進 在哈夫曼編碼中引入堆排序 堆排序算法（HEAPSORT）由1991 年計算機先驅獎獲得者、斯坦福大學計算機科學系教授羅伯特弗洛伊德(Robert W．Floyd)和威廉姆斯(J．Williams)在1964 年共同發(fā)明。堆排序是一樹形選擇排序，堆頂元素是堆中的最大(或最小)元素，且堆的每一條路徑上的元素都是有序的。堆排序正是利用了堆頂元素最大(或最小)這一特征，使得在當前無序區(qū)中選取最大(或最小)關鍵字變得簡單。 堆排序中的堆分為大頂堆和小頂堆，其中大頂堆指根結點(亦稱為堆頂)的關鍵字是堆里所有關鍵字中最大者的堆。小頂堆指根結點(亦稱為堆頂)的關鍵字是堆里所有關鍵字中最小者的堆。當排序元素不再變化時，利用堆排序可一次求出所需序列。這時，堆排序的時間復雜度恒為O(nlog(n)),不會像其他排序那樣有出入，而且空間復雜度為V(n),是最低的。 在哈夫曼編碼算法中，為了從R[1..n]中選出兩個頻率最小的元素，需要進行兩趟循環(huán)，每次進行n1 次比較。事實上，在第二趟的n1 次比較中，有許多比較可能已經(jīng)在第一趟循環(huán)中做過，但由于前一趟比較時未保留這些比較結果，所以后一趟排序時又重復執(zhí)行了這些比較操作。而堆排序可通過樹形結構保存部分比較結果，可減少比較次數(shù)，從而縮短了壓縮時間。 在哈夫曼編碼算法中引入堆排序思想后，與靜態(tài)哈夫曼編碼、動態(tài)哈夫曼編碼的比較如表41 所示：表41 引入堆排序后的哈夫曼編碼與靜、動態(tài)哈夫曼編碼的比較文件名采用的編碼算法壓縮前的大小壓縮后的大小壓縮時間(16 位色位圖)靜態(tài)哈夫曼編碼234KB動態(tài)哈夫曼編碼234KB40 KB加入堆排序后的哈夫曼編碼234KB(24 位位圖)靜態(tài)哈夫曼編碼動態(tài)哈夫曼編碼999kB加入堆排序后的哈夫曼編碼 模擬哈夫曼樹的創(chuàng)建 在靜態(tài)哈夫曼編碼算法中，必須保存統(tǒng)計出的結果以便解碼時構造相同的哈夫曼樹，或者直接保存哈夫曼樹本身，這要占用大量的空間，也就意味著壓縮效率的下降。在動態(tài)哈夫曼編碼算法中，雖然克服了前者的缺點，但是算法復雜，而且解壓縮耗費時間長，若用于通信，就會引起較大的延時。實際上，我們進行壓縮時，所關心的是字符編碼的單值性，基于這種壓縮思想，沒有必要構造哈夫曼樹，用一個二維數(shù)組就可以模擬哈夫曼樹的創(chuàng)建過程并得到各字符的編碼。實現(xiàn)思想如下： 先統(tǒng)計每個編碼長度Ni (二叉樹上的Ni 層) 上對應數(shù)據(jù)的數(shù)目，再分別對Ni 層上的符號以遞增順序分