當(dāng)前位置:首頁(yè) > 測(cè)試測(cè)量 > 測(cè)試測(cè)量
[導(dǎo)讀]摘要:在信息快速傳輸和存儲(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ù);赫夫曼編碼;赫

摘要:在信息快速傳輸和存儲(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)度最小??梢宰C明赫夫曼樹(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)度在具有相同輸入概率集合的前提下,比其它任何一種可譯碼都小,因此,也常被稱(chē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)課題有益。

本站聲明: 本文章由作者或相關(guān)機(jī)構(gòu)授權(quán)發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點(diǎn),本站亦不保證或承諾內(nèi)容真實(shí)性等。需要轉(zhuǎn)載請(qǐng)聯(lián)系該專(zhuān)欄作者,如若文章內(nèi)容侵犯您的權(quán)益,請(qǐng)及時(shí)聯(lián)系本站刪除。
換一批
延伸閱讀

9月2日消息,不造車(chē)的華為或?qū)⒋呱龈蟮莫?dú)角獸公司,隨著阿維塔和賽力斯的入局,華為引望愈發(fā)顯得引人矚目。

關(guān)鍵字: 阿維塔 塞力斯 華為

倫敦2024年8月29日 /美通社/ -- 英國(guó)汽車(chē)技術(shù)公司SODA.Auto推出其旗艦產(chǎn)品SODA V,這是全球首款涵蓋汽車(chē)工程師從創(chuàng)意到認(rèn)證的所有需求的工具,可用于創(chuàng)建軟件定義汽車(chē)。 SODA V工具的開(kāi)發(fā)耗時(shí)1.5...

關(guān)鍵字: 汽車(chē) 人工智能 智能驅(qū)動(dòng) BSP

北京2024年8月28日 /美通社/ -- 越來(lái)越多用戶(hù)希望企業(yè)業(yè)務(wù)能7×24不間斷運(yùn)行,同時(shí)企業(yè)卻面臨越來(lái)越多業(yè)務(wù)中斷的風(fēng)險(xiǎn),如企業(yè)系統(tǒng)復(fù)雜性的增加,頻繁的功能更新和發(fā)布等。如何確保業(yè)務(wù)連續(xù)性,提升韌性,成...

關(guān)鍵字: 亞馬遜 解密 控制平面 BSP

8月30日消息,據(jù)媒體報(bào)道,騰訊和網(wǎng)易近期正在縮減他們對(duì)日本游戲市場(chǎng)的投資。

關(guān)鍵字: 騰訊 編碼器 CPU

8月28日消息,今天上午,2024中國(guó)國(guó)際大數(shù)據(jù)產(chǎn)業(yè)博覽會(huì)開(kāi)幕式在貴陽(yáng)舉行,華為董事、質(zhì)量流程IT總裁陶景文發(fā)表了演講。

關(guān)鍵字: 華為 12nm EDA 半導(dǎo)體

8月28日消息,在2024中國(guó)國(guó)際大數(shù)據(jù)產(chǎn)業(yè)博覽會(huì)上,華為常務(wù)董事、華為云CEO張平安發(fā)表演講稱(chēng),數(shù)字世界的話(huà)語(yǔ)權(quán)最終是由生態(tài)的繁榮決定的。

關(guān)鍵字: 華為 12nm 手機(jī) 衛(wèi)星通信

要點(diǎn): 有效應(yīng)對(duì)環(huán)境變化,經(jīng)營(yíng)業(yè)績(jī)穩(wěn)中有升 落實(shí)提質(zhì)增效舉措,毛利潤(rùn)率延續(xù)升勢(shì) 戰(zhàn)略布局成效顯著,戰(zhàn)新業(yè)務(wù)引領(lǐng)增長(zhǎng) 以科技創(chuàng)新為引領(lǐng),提升企業(yè)核心競(jìng)爭(zhēng)力 堅(jiān)持高質(zhì)量發(fā)展策略,塑強(qiáng)核心競(jìng)爭(zhēng)優(yōu)勢(shì)...

關(guān)鍵字: 通信 BSP 電信運(yùn)營(yíng)商 數(shù)字經(jīng)濟(jì)

北京2024年8月27日 /美通社/ -- 8月21日,由中央廣播電視總臺(tái)與中國(guó)電影電視技術(shù)學(xué)會(huì)聯(lián)合牽頭組建的NVI技術(shù)創(chuàng)新聯(lián)盟在BIRTV2024超高清全產(chǎn)業(yè)鏈發(fā)展研討會(huì)上宣布正式成立。 活動(dòng)現(xiàn)場(chǎng) NVI技術(shù)創(chuàng)新聯(lián)...

關(guān)鍵字: VI 傳輸協(xié)議 音頻 BSP

北京2024年8月27日 /美通社/ -- 在8月23日舉辦的2024年長(zhǎng)三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會(huì)上,軟通動(dòng)力信息技術(shù)(集團(tuán))股份有限公司(以下簡(jiǎn)稱(chēng)"軟通動(dòng)力")與長(zhǎng)三角投資(上海)有限...

關(guān)鍵字: BSP 信息技術(shù)
關(guān)閉
關(guān)閉