談?wù)劰蚵幋a

王俊平　李加彥

摘要：在當(dāng)今信息爆炸時(shí)代，如何采用有效的數(shù)據(jù)壓縮技術(shù)來(lái)節(jié)省數(shù)據(jù)文件的存儲(chǔ)空間和計(jì)算機(jī)網(wǎng)絡(luò)的傳送時(shí)間已越來(lái)越引起人們的重視。哈夫曼編碼正是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。本文從哈夫曼編碼的基本原理展開(kāi)論述，對(duì)其具體應(yīng)用進(jìn)行分析，對(duì)哈夫曼編碼中的一些問(wèn)題進(jìn)行有益探討。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)壓縮 編碼

0 引言

隨著計(jì)算機(jī)的普遍應(yīng)用與日益發(fā)展，其應(yīng)用早已不局限于簡(jiǎn)單的數(shù)值運(yùn)算，而涉及到問(wèn)題的分析、數(shù)據(jù)結(jié)構(gòu)框架的設(shè)計(jì)以及設(shè)計(jì)最短路線(xiàn)等復(fù)雜的非數(shù)值處理和操作。算法與數(shù)據(jù)結(jié)構(gòu)旨在分析研究計(jì)算機(jī)加工的數(shù)據(jù)對(duì)象的特性，以便選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，從而使建立在其上的解決問(wèn)題的算法達(dá)到最優(yōu)。數(shù)據(jù)結(jié)構(gòu)是在整個(gè)計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域上廣泛被使用的術(shù)語(yǔ)。它用來(lái)反映一個(gè)數(shù)據(jù)的內(nèi)部構(gòu)成，即一個(gè)數(shù)據(jù)由那些成分?jǐn)?shù)據(jù)構(gòu)成，以什么方式構(gòu)成，呈什么結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)有邏輯上的數(shù)據(jù)結(jié)構(gòu)和物理上的數(shù)據(jù)結(jié)構(gòu)之分。邏輯上的數(shù)據(jù)結(jié)構(gòu)反映成分?jǐn)?shù)據(jù)之間的邏輯關(guān)系，而物理上的數(shù)據(jù)結(jié)構(gòu)反映成分?jǐn)?shù)據(jù)在計(jì)算機(jī)內(nèi)部的存儲(chǔ)安排。

1 哈夫曼編碼的原理

哈夫曼編碼(Huffman Coding)是一種編碼方式，哈夫曼編碼是可變字長(zhǎng)編碼(VLC)的一種。Huffman于1952年提出一種編碼方法，該方法完全依據(jù)字符出現(xiàn)概率來(lái)構(gòu)造異字頭的平均長(zhǎng)度最短的碼字，有時(shí)稱(chēng)之為最佳編碼，一般就叫作Huffman編碼。以哈夫曼樹(shù)─即最優(yōu)二叉樹(shù)，帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)，經(jīng)常應(yīng)用于數(shù)據(jù)壓縮。在計(jì)算機(jī)信息處理中，“哈夫曼編碼”是一種一致性編碼法(又稱(chēng)“熵編碼法”)，用于數(shù)據(jù)的無(wú)損耗壓縮。這一術(shù)語(yǔ)是指使用一張?zhí)厥獾木幋a表將源字符(例如某文件中的一個(gè)符號(hào))進(jìn)行編碼。這張編碼表的特殊之處在于，它是根據(jù)每一個(gè)源字符出現(xiàn)的估算概率而建立起來(lái)的(出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的則使用較長(zhǎng)的編碼，這便使編碼之后的字符串的平均期望長(zhǎng)度降低，從而達(dá)到無(wú)損壓縮數(shù)據(jù)的目的)。這種方法是由David.A.Huffman發(fā)展起來(lái)的。例如，在英文中，e的出現(xiàn)概率很高，而z的出現(xiàn)概率則最低。當(dāng)利用哈夫曼編碼對(duì)一篇英文進(jìn)行壓縮時(shí)，e極有可能用一個(gè)位(bit)來(lái)表示，而z則可能花去25個(gè)位(不是26)。用普通的表示方法時(shí)，每個(gè)英文字母均占用一個(gè)字節(jié)(byte)，即8個(gè)位。二者相比，e使用了一般編碼的1/8的長(zhǎng)度，z則使用了3倍多。倘若我們能實(shí)現(xiàn)對(duì)于英文中各個(gè)字母出現(xiàn)概率的較準(zhǔn)確的估算，就可以大幅度提高無(wú)損壓縮的比例。哈夫曼樹(shù)的應(yīng)用最廣泛地是在編碼技術(shù)上，它能夠容易地求出給定字符集及其概率分布的最優(yōu)前綴碼(最優(yōu)前綴碼就是平均碼長(zhǎng)最小的前綴碼)。哈夫曼編碼的構(gòu)造很容易，只要構(gòu)造好了哈夫曼樹(shù)，按分支情況在左路徑上寫(xiě)代碼0，右路徑上寫(xiě)代碼1，然后從上到下到葉結(jié)點(diǎn)的相應(yīng)路徑上的代碼的序列就是該結(jié)點(diǎn)的最優(yōu)前綴碼。

2 哈夫曼編碼的構(gòu)造過(guò)程

通常我們把數(shù)據(jù)壓縮的過(guò)程稱(chēng)為編碼，解壓縮的過(guò)程為解碼。電報(bào)通信是傳送文字的二進(jìn)制碼形式的字符串。但在信息傳遞時(shí)，總希望總長(zhǎng)度能盡可能短，即采用最短碼。舉例說(shuō)明，先前快速遠(yuǎn)距離通信的主要手段是電報(bào)，即將需傳送的文字轉(zhuǎn)換成由二進(jìn)制的字符組成的字符串。在傳送電文時(shí)，希望總長(zhǎng)盡可能地短，如果對(duì)每個(gè)字符設(shè)計(jì)長(zhǎng)度不等的編碼，且讓電文中出現(xiàn)次數(shù)較多的字符采用盡可能短的編碼，以減少經(jīng)費(fèi)。哈夫曼樹(shù)就是根據(jù)此原理設(shè)計(jì)出來(lái)的一種存儲(chǔ)結(jié)構(gòu)。

在電報(bào)通訊中，電文是以二進(jìn)制的0、1序列傳送的。在發(fā)送端需要將電文中的字符序列轉(zhuǎn)換成二進(jìn)制0、1序列(即編碼)，在接收端又需要把接受的0、1序列轉(zhuǎn)換成對(duì)應(yīng)的字符序列(即譯碼)。利用哈夫曼樹(shù)求得的用于通信的二進(jìn)制編碼稱(chēng)為哈夫曼編碼。樹(shù)中從根到每個(gè)葉子都有一條路徑，對(duì)路徑上的各分支約定：指向左子樹(shù)的分支表示“0”碼，指向右子樹(shù)的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為各個(gè)葉子對(duì)應(yīng)的自已的編碼，就可以完成正確的編碼譯碼工作。

最簡(jiǎn)單的二進(jìn)制編碼方式是等長(zhǎng)編碼。例如，假定電文中只使用A、B、C、D、E、F這六種字符，若進(jìn)行等長(zhǎng)編碼，它們分別需要3位二進(jìn)制字符，可依次編碼為000、001、010、011、100、101。由常識(shí)可知，電文中的每個(gè)字符的出現(xiàn)頻率一般是不同的。假定在一份電文中，這6個(gè)字符的出現(xiàn)頻率分別為4、2、6、8、3、2，則電文被編碼后的總長(zhǎng)度L為:L=3×(4+2+6+8+3+2)=75。

現(xiàn)在討論能縮短傳送電文的總長(zhǎng)度，從而縮短傳送時(shí)間這樣一個(gè)務(wù)實(shí)的問(wèn)題。我們應(yīng)該想到，若采用不等長(zhǎng)編碼，讓出現(xiàn)頻率高的字符具有較短的編碼，讓出現(xiàn)頻率低的字符具有較長(zhǎng)的編碼，這樣可能縮短傳送電文的總長(zhǎng)度。

采用不等長(zhǎng)編碼要避免譯碼的二義性。假設(shè)用0表示字符D，用01表示字符C，則當(dāng)接收到編碼串...01...，并譯到編碼0時(shí)，是立即譯出對(duì)應(yīng)的D，還是接著與下一個(gè)編碼1一起譯為對(duì)應(yīng)的字符C，這就產(chǎn)生了二義性。因此，若對(duì)某一字符集進(jìn)行不等長(zhǎng)編碼，則要求字符集中任一字符的編碼都不能是另一個(gè)字符的編碼的前綴。這種編碼叫做前綴編碼。顯然等長(zhǎng)編碼是前綴編碼。

因此，設(shè)計(jì)電文總長(zhǎng)最短的二進(jìn)制前綴編碼，就是以n種字符出現(xiàn)的頻率作權(quán)，構(gòu)造一顆哈夫曼樹(shù)，此構(gòu)造過(guò)程稱(chēng)為哈夫曼編碼。此過(guò)程的實(shí)現(xiàn)分為在步：①哈夫曼樹(shù)的建立；②哈夫曼編碼的生成；③編碼文件的譯碼。

為了使不等長(zhǎng)編碼為前綴編碼，可用該字符集中的每個(gè)字符作為葉子結(jié)點(diǎn)生成一棵編碼二叉樹(shù)，為了獲得傳送電文的最短長(zhǎng)度，可將每個(gè)字符出現(xiàn)頻率作為字符結(jié)點(diǎn)的權(quán)值賦予給結(jié)點(diǎn)上，求出此樹(shù)的最小帶權(quán)路徑長(zhǎng)度就等于求出了傳送電文的最短長(zhǎng)度。假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為Wi，編碼長(zhǎng)度為L(zhǎng)i，電文中有n種字符，則電文編碼總長(zhǎng)為∑WiLi。若將此對(duì)應(yīng)到二叉樹(shù)上，Wi為葉結(jié)點(diǎn)的權(quán)，Li為根結(jié)點(diǎn)到葉結(jié)點(diǎn)的路徑長(zhǎng)度。那么，∑WiLi恰好為二叉樹(shù)上帶權(quán)路徑長(zhǎng)度。因此，求傳送電文的最短長(zhǎng)度問(wèn)題就轉(zhuǎn)化為求由字符集中的所有字符作為葉子結(jié)點(diǎn)，由字符的出現(xiàn)頻率作為其權(quán)值所產(chǎn)生的哈夫曼樹(shù)的問(wèn)題。

3 總結(jié)

隨著計(jì)算機(jī)硬件系統(tǒng)的發(fā)展，信息技術(shù)己成為當(dāng)代知識(shí)經(jīng)濟(jì)的核心技術(shù)。我們時(shí)刻都在和數(shù)據(jù)打交道。比如在銀行查詢(xún)存款、通過(guò)互聯(lián)網(wǎng)查看新聞、遠(yuǎn)程教育報(bào)名等，所有這些都在與數(shù)據(jù)發(fā)生關(guān)系。實(shí)際上，現(xiàn)實(shí)世界中的實(shí)體經(jīng)過(guò)抽象以后，就可以成為計(jì)算機(jī)上所處理的數(shù)據(jù)。哈夫曼編碼將會(huì)在各個(gè)領(lǐng)域發(fā)揮重要的作用，同時(shí)基于哈夫曼編碼的研究也將逐步完善。

參考文獻(xiàn)：

[1]陳媛.《算法與數(shù)據(jù)結(jié)構(gòu)》2005年4月第1版清華大學(xué)出版社.

[2]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu).(C語(yǔ)言版).1997年4月第1版清華大學(xué)出版社.

[3]王學(xué)軍，方建文.數(shù)據(jù)結(jié)構(gòu).2007年8月第1版中國(guó)計(jì)劃出版社.