赫夫曼編譯碼系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

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

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

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

    設(shè)計(jì)調(diào)試環(huán)境為Microsoft Visual C++6．0系統(tǒng)。

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

    以下是部分編碼的代碼段


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

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

4 結(jié)束語(yǔ)
    赫夫曼編碼是已被證明的一種有效的熵編碼方式，在諸如文本、圖像、視頻壓縮及通信、密碼等信息壓縮編碼標(biāo)準(zhǔn)中被廣泛使用。目前廣泛應(yīng)用的許多其他高效數(shù)據(jù)壓縮算法，例如算術(shù)編碼、可預(yù)測(cè)編碼也是在赫夫曼編碼的基礎(chǔ)上發(fā)展起來(lái)的，所以研究赫夫曼編碼的思想，對(duì)于深入理解數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計(jì)學(xué)科中的相關(guān)課題有益。