談談哈夫曼編碼

摘要：在當今信息爆炸時代，如何采用有效的數據壓縮技術來節省數據文件的存儲空間和計算機網絡的傳送時間已越來越引起人們的重視。哈夫曼編碼正是一種應用廣泛且非常有效的數據壓縮技術。本文從哈夫曼編碼的基本原理展開論述，對其具體應用進行分析，對哈夫曼編碼中的一些問題進行有益探討。

關鍵詞：數據結構 數據壓縮 編碼

0 引言

隨著計算機的普遍應用與日益發展，其應用早已不局限于簡單的數值運算，而涉及到問題的分析、數據結構框架的設計以及設計最短路線等復雜的非數值處理和操作。算法與數據結構旨在分析研究計算機加工的數據對象的特性，以便選擇適當的數據結構和存儲結構，從而使建立在其上的解決問題的算法達到最優。數據結構是在整個計算機科學與技術領域上廣泛被使用的術語。它用來反映一個數據的內部構成，即一個數據由那些成分數據構成，以什么方式構成，呈什么結構。數據結構有邏輯上的數據結構和物理上的數據結構之分。邏輯上的數據結構反映成分數據之間的邏輯關系，而物理上的數據結構反映成分數據在計算機內部的存儲安排。

1 哈夫曼編碼的原理

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

2 哈夫曼編碼的構造過程

通常我們把數據壓縮的過程稱為編碼，解壓縮的過程為解碼。電報通信是傳送文字的二進制碼形式的字符串。但在信息傳遞時，總希望總長度能盡可能短，即采用最短碼。舉例說明，先前快速遠距離通信的主要手段是電報，即將需傳送的文字轉換成由二進制的字符組成的字符串。在傳送電文時，希望總長盡可能地短，如果對每個字符設計長度不等的編碼，且讓電文中出現次數較多的字符采用盡可能短的編碼，以減少經費。哈夫曼樹就是根據此原理設計出來的一種存儲結構。

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

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

現在討論能縮短傳送電文的總長度，從而縮短傳送時間這樣一個務實的問題。我們應該想到，若采用不等長編碼，讓出現頻率高的字符具有較短的編碼，讓出現頻率低的字符具有較長的編碼，這樣可能縮短傳送電文的總長度。

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

因此，設計電文總長最短的二進制前綴編碼，就是以n種字符出現的頻率作權，構造一顆哈夫曼樹，此構造過程稱為哈夫曼編碼。此過程的實現分為在步：①哈夫曼樹的建立；②哈夫曼編碼的生成；③編碼文件的譯碼。

為了使不等長編碼為前綴編碼，可用該字符集中的每個字符作為葉子結點生成一棵編碼二叉樹，為了獲得傳送電文的最短長度，可將每個字符出現頻率作為字符結點的權值賦予給結點上，求出此樹的最小帶權路徑長度就等于求出了傳送電文的最短長度。假設每種字符在電文中出現的次數為Wi，編碼長度為Li，電文中有n種字符，則電文編碼總長為∑WiLi。若將此對應到二叉樹上，Wi為葉結點的權，Li為根結點到葉結點的路徑長度。那么，∑WiLi恰好為二叉樹上帶權路徑長度。因此，求傳送電文的最短長度問題就轉化為求由字符集中的所有字符作為葉子結點，由字符的出現頻率作為其權值所產生的哈夫曼樹的問題。

3 總結

隨著計算機硬件系統的發展，信息技術己成為當代知識經濟的核心技術。我們時刻都在和數據打交道。比如在銀行查詢存款、通過互聯網查看新聞、遠程教育報名等，所有這些都在與數據發生關系。實際上，現實世界中的實體經過抽象以后，就可以成為計算機上所處理的數據。哈夫曼編碼將會在各個領域發揮重要的作用，同時基于哈夫曼編碼的研究也將逐步完善。

參考文獻：

[1]陳媛.《算法與數據結構》2005年4月第1版清華大學出版社.

[2]嚴蔚敏，吳偉民.數據結構.(C語言版).1997年4月第1版清華大學出版社.

[3]王學軍，方建文.數據結構.2007年8月第1版中國計劃出版社.