哈夫曼編碼

來自 孔夫子舊書網 的圖片

哈夫曼編碼是中國的一個科技名詞。

漢字是中華民族燦爛文化展台上一顆無可取代、熠熠閃光的明珠。漢字之美，美在莊重典雅，形神兼具。她承載的是中華民族數千年的厚重歷史與燦爛文化。她的美，是無與倫比的。

目錄

名詞解釋

哈夫曼編碼(Huffman Coding)，又稱霍夫曼編碼，是一種編碼方式，哈夫曼編碼是可變字長編碼(VLC)的一種。Huffman於1952年提出一種編碼方法，該方法完全依據字符出現概率來構造異字頭的平均長度最短的碼字，有時稱之為最佳編碼，一般就叫做Huffman編碼（有時也稱為霍夫曼編碼）。

1951年，哈夫曼和他在MIT信息論的同學需要選擇是完成學期報告還是期末考試。導師Robert M. Fano給他們的學期報告的題目是，尋找最有效的二進制編碼。由於無法證明哪個已有編碼是最有效的，哈夫曼放棄對已有編碼的研究，轉向新的探索，最終發現了基於有序頻率二叉樹編碼的想法，並很快證明了這個方法是最有效的。由於這個算法，學生終於青出於藍，超過了他那曾經和信息論創立者香農共同研究過類似編碼的導師。哈夫曼使用自底向上的方法構建二叉樹，避免了次優算法Shannon-Fano編碼的最大弊端──自頂向下構建樹。

1952年，David A. Huffman在麻省理工攻讀博士時發表了《一種構建極小多餘編碼的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文，它一般就叫做Huffman編碼。

Huffman在1952年根據香農（Shannon）在1948年和范若（Fano）在1949年闡述的這種編碼思想提出了一種不定長編碼的方法，也稱霍夫曼（Huffman）編碼。霍夫曼編碼的基本方法是先對圖像數據掃描一遍，計算出各種像素出現的概率，按概率的大小指定不同長度的唯一碼字，由此得到一張該圖像的霍夫曼碼錶。編碼後的圖像數據記錄的是每個像素的碼字，而碼字與實際像素值的對應關係記錄在碼錶中。

赫夫曼編碼是可變字長編碼(VLC)的一種。 Huffman於1952年提出一種編碼方法，該方法完全依據字符出現概率來構造異字頭的平均長 度最短的碼字，有時稱之為最佳編碼，一般就稱Huffman編碼。下面引證一個定理，該定理保證了按字符出現概率分配碼長，可使平均碼長最短。

原理

設某信源產生有五種符號u1、u2、u3、u4和u5，對應概率P1=0.4，P2=0.1，P3=P4=0.2，P5=0.1。首先，將符號按照概率由大到小排隊，如圖1所示。編碼時，從最小概率的兩個符號開始，可選其中一個支路為0，另一支路為1。這裡，我們選上支路為0，下支路為1。再將已編碼的兩支路的概率合併，並重新排隊。多次重複使用上述方法直至合併概率歸一時為止。從圖1中（a）和（b）可以看出，兩者雖平均碼長相等，但同一符號可以有不同的碼長，即編碼方法並不唯一，其原因是兩支路概率合併後重新排隊時，可能出現幾個支路概率相等，造成排隊方法不唯一。一般，若將新合併後的支路排到等概率的最上支路，將有利於縮短碼長方差，且編出的碼更接近於等長碼。這裡圖1中（a）的編碼比（b）好。

赫夫曼碼的碼字（各符號的代碼）是異前置碼字，即任一碼字不會是另一碼字的前面部分，這使各碼字可以連在一起傳送，中間不需另加隔離符號，只要傳送時不出錯，收端仍可分離各個碼字，不致混淆。

實際應用中，除採用定時清洗以消除誤差擴散和採用緩衝存儲以解決速率匹配以外，主要問題是解決小符號集合的統計匹配，例如黑（1）、白（0）傳真信源的統計匹配，採用0和1不同長度遊程組成擴大的符號集合信源。遊程，指相同碼元的長度（如二進碼中連續的一串0或一串1的長度或個數）。按照CCITT標準，需要統計2×1728種遊程（長度），這樣，實現時的存儲量太大。事實上長遊程的概率很小，故CCITT還規定：若l表示遊程長度，則l=64q+r。其中q稱主碼，r為基碼。編碼時，不小於64的遊程長度由主碼和基碼組成。而當l為64的整數倍時，只用主碼的代碼，已不存在基碼的代碼。

長遊程的主碼和基碼均用赫夫曼規則進行編碼，這稱為修正赫夫曼碼，其結果有表可查。該方法已廣泛應用於文件傳真機中。