赫夫曼編譯碼系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)
摘要:在信息快速傳輸和存儲(chǔ)過程中,數(shù)據(jù)壓縮有著重要的作用。從赫夫曼樹定義及算法出發(fā),介紹了一個(gè)赫夫曼編譯碼系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)過程。這對(duì)于深入理解數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計(jì)有益。
關(guān)鍵詞:赫夫曼樹;赫夫曼編碼;赫夫曼譯碼
在數(shù)據(jù)結(jié)構(gòu)課程的實(shí)踐環(huán)節(jié)中,通常會(huì)讓學(xué)生利用赫夫曼編碼進(jìn)行文本壓縮與解壓縮。由于教材上只是給出了赫夫曼樹的定義及算法,學(xué)生會(huì)感到無從下手。本文將從赫夫曼樹定義及算法出發(fā),通過實(shí)例介紹赫夫曼編譯碼系統(tǒng)的具體設(shè)計(jì)與實(shí)現(xiàn)過程。
1 設(shè)計(jì)內(nèi)容
1.1 赫夫曼編譯碼系統(tǒng)功能模塊
(1)赫夫曼建樹模塊:根據(jù)輸入的字符和頻率,完成赫夫曼樹的構(gòu)造,并根據(jù)赫夫曼樹求赫夫曼編碼。
(2)編碼模塊:讀取文本文件進(jìn)行編碼,編碼結(jié)果存入到新文件。
(3)譯碼模塊:讀取編碼文件并解碼,打開存儲(chǔ)編碼的文件,根據(jù)所讀取的編碼文件中的每個(gè)字符,利用赫夫曼樹進(jìn)行解碼。
(4)輸出模塊:將解碼后的每個(gè)字母寫入到一個(gè)新的文件中。
1.2 測試數(shù)據(jù)
用表1給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立赫夫曼樹,并實(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è)計(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)建赫夫曼樹
一般而言,給定n個(gè)實(shí)數(shù)w1,w2,…,w3其中,n≥2,求一個(gè)具有n個(gè)結(jié)點(diǎn)的二叉數(shù),使其帶權(quán)路徑長度最小??梢宰C明赫夫曼樹的帶權(quán)路徑長度是最小的。
(1)根據(jù)與n個(gè)權(quán)值|w1,w2,…,w3|對(duì)應(yīng)的n個(gè)結(jié)點(diǎn)構(gòu)成具有n棵二叉樹的森林F={HT1,HT2,…,HTn},其中第i棵二叉樹HTi(1≤i≤n)都只有一個(gè)權(quán)值為wi的根結(jié)點(diǎn),其左、右子樹均為空。
(2)在森林F中選出兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為一棵新樹的左、右子樹,且置新樹的根結(jié)點(diǎn)的權(quán)值為其左、右子樹上根結(jié)點(diǎn)權(quán)值之和。
(3)從F中刪除構(gòu)成新樹的那兩棵,同時(shí)把新樹加入F中。
(4)重復(fù)第1和第3步,直到F中只含有一棵為止,此樹便為赫夫曼樹。
2.2 赫夫曼編碼
赫夫曼編碼是根據(jù)可變長最佳編碼定理,應(yīng)用赫夫曼算法而產(chǎn)生的一種編碼,是消除編碼冗余度最常用的方法。它的平均碼字長度在具有相同輸入概率集合的前提下,比其它任何一種可譯碼都小,因此,也常被稱為緊湊碼。
(1)給定字符集的赫夫曼樹生成后,求赫夫曼編碼的具體實(shí)現(xiàn)過程是:依次以葉子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文件。
評(píng)論