摘要：在信息快速傳輸和存儲過程中，數據壓縮有著重要的作用。從赫夫曼樹定義及算法出發(fā)，介紹了一個赫夫曼編譯碼系統(tǒng)的設計與實現過程。這對于深入理解數據結構、程序設計有益。
關鍵詞：赫夫曼樹；赫夫曼編碼；赫夫曼譯碼

    在數據結構課程的實踐環(huán)節(jié)中，通常會讓學生利用赫夫曼編碼進行文本壓縮與解壓縮。由于教材上只是給出了赫夫曼樹的定義及算法，學生會感到無從下手。本文將從赫夫曼樹定義及算法出發(fā)，通過實例介紹赫夫曼編譯碼系統(tǒng)的具體設計與實現過程。

1 設計內容
1．1 赫夫曼編譯碼系統(tǒng)功能模塊
    (1)赫夫曼建樹模塊：根據輸入的字符和頻率，完成赫夫曼樹的構造，并根據赫夫曼樹求赫夫曼編碼。
    (2)編碼模塊：讀取文本文件進行編碼，編碼結果存入到新文件。
    (3)譯碼模塊：讀取編碼文件并解碼，打開存儲編碼的文件，根據所讀取的編碼文件中的每個字符，利用赫夫曼樹進行解碼。
    (4)輸出模塊：將解碼后的每個字母寫入到一個新的文件中。
1．2 測試數據
    用表1給出的字符集和頻度的實際統(tǒng)計數據建立赫夫曼樹，并實現以下報文的編碼和譯碼：“THISPROGRAM IS MY FAVORITE”。

    設計調試環(huán)境為Microsoft Visual C++6．0系統(tǒng)。

2 設計原理及算法分析
    本次要做的赫夫曼編譯碼系統(tǒng)的主要功能是：運用二叉樹來設計二進制的前綴編碼。給一個文件，先統(tǒng)計文件中每個字符出現的頻數，即作為此字符的權值，然后將里面的字符編碼成相應的赫夫曼編碼。最后，根據赫夫曼譯碼原理把所給二進制數編譯成對應的字符串。
2．1 構建赫夫曼樹
    一般而言，給定n個實數w1，w2，…，w3其中，n≥2，求一個具有n個結點的二叉數，使其帶權路徑長度最小。可以證明赫夫曼樹的帶權路徑長度是最小的。
    (1)根據與n個權值|w1，w2，…，w3|對應的n個結點構成具有n棵二叉樹的森林F={HT1，HT2，…，HTn}，其中第i棵二叉樹HTi(1≤i≤n)都只有一個權值為wi的根結點，其左、右子樹均為空。
    (2)在森林F中選出兩棵根結點權值最小的樹作為一棵新樹的左、右子樹，且置新樹的根結點的權值為其左、右子樹上根結點權值之和。
    (3)從F中刪除構成新樹的那兩棵，同時把新樹加入F中。
    (4)重復第1和第3步，直到F中只含有一棵為止，此樹便為赫夫曼樹。
2．2 赫夫曼編碼
    赫夫曼編碼是根據可變長最佳編碼定理，應用赫夫曼算法而產生的一種編碼，是消除編碼冗余度最常用的方法。它的平均碼字長度在具有相同輸入概率集合的前提下，比其它任何一種可譯碼都小，因此，也常被稱為緊湊碼。
    (1)給定字符集的赫夫曼樹生成后，求赫夫曼編碼的具體實現過程是：依次以葉子HT[i](0≤i≤n-1)為出發(fā)點，向上回溯至根為止。上溯時走左孩子則生成代碼0，走右孩子則生成代碼1。
    (2)統(tǒng)計從根到葉子的路徑上的標號依次相連，便為該葉子所對應字符的編碼。
    (3)用生成的各個字符的編碼替代原文件中的相應的字符，生成decode．txt文件。

    以下是部分編碼的代碼段


2．3 赫夫曼譯碼
    對壓縮后的數據文件進行解碼則必須借助于赫夫曼樹，其過程是：從decode．txt文件中讀取編碼后的二進制碼，從赫夫曼樹的根結點出發(fā)，若當前為0，則向左孩子；若為1，則向右孩子。到達某一葉子結點時，便譯出相應的字符。循環(huán)上步，直至解碼完成。

3 設計結果
    (1)利用Microsoft Visual C++6．0系統(tǒng)進行調試，輸入源程序，編譯、連接后生成赫夫曼編譯碼系統(tǒng)可執(zhí)行文件，如圖1所示。
    (2)運行赫夫曼編譯碼系統(tǒng)可執(zhí)行文件，輸入表1字符和頻度，編譯碼后得到運行結果，如圖2所示。

4 結束語
    赫夫曼編碼是已被證明的一種有效的熵編碼方式，在諸如文本、圖像、視頻壓縮及通信、密碼等信息壓縮編碼標準中被廣泛使用。目前廣泛應用的許多其他高效數據壓縮算法，例如算術編碼、可預測編碼也是在赫夫曼編碼的基礎上發(fā)展起來的，所以研究赫夫曼編碼的思想，對于深入理解數據結構、程序設計學科中的相關課題有益。