哈夫曼編碼方法的方案選擇研究

蔡春梅

【摘要】本文首先分析了哈夫曼編碼的理論根據，介紹了哈夫曼編碼的編碼過程，通過舉例詳細分析了不同編碼方案的編碼結果，最后對不同方案的編碼方法進行了總結。

【關鍵詞】哈夫曼編碼無失真編碼編碼方案

香農編碼理論指出存在一種無失真的編碼方法，使得編碼平均碼長逼近熵值這個下限，并指出了理想編碼器的存在。但在香農理論中并未給出使用碼的結構及構造方法，即沒有給出具體的編碼方法，編碼理論為解決此問題而發展起來，如香農編碼法、費諾編碼法和哈夫曼編碼法，其中尤其以哈夫曼編碼法為最佳。哈夫曼編碼方法于1952年問世，至今仍廣泛應用于各種數據壓縮技術中，在多媒體編碼系統中常用這種方法作熵保持編碼。

一、哈夫曼編碼方法簡介

最佳編碼定理指出：在編碼過程中，對于信源符號，如果出現概率大的符號分配短字長的碼字，出現概率小的符號分配長碼字，編碼編碼結束后，得到的碼字長度嚴格按照符號概率的大小的相反順序，那么這種編碼方式得到的平均碼字長度一定小于任何其他排列方式得到的碼字長度。哈夫曼編碼法就是利用了這個原理，是一種典型的無失真的編碼方法，且是熵編碼中的最佳編碼方法。

哈夫曼編碼法的過程：首先將信源按概率遞減排列，然后將最小兩個概率相加，得到的新概率再放入原概率序列中重新排列，如此反復，不斷的縮減信源，直至信源個數只剩一個為止。最后從最后一級縮減信源開始，依編碼路徑向前返回，并分配碼字，得到哈夫曼碼。

二、哈夫曼編碼方案分析與選擇

根據哈夫曼編碼的方法可得：哈夫曼編碼法編碼結果一定不唯一。首先，縮減信源結束后，對最小概率分配“0”和“1”是任意的；其次，當將概率序列中的兩個最小概率相加時，得到的概率和可能與原序列中的概率相等，此時，概率相等的幾個符號及可以任意排列，也將導致最終的編碼不唯一。那編碼中究竟哪種方案更好呢？用以下這由此可見，編碼二的方差較小，說明其碼字的變化較小，此方案較好。

三、總結

哈夫曼編碼方法主要是依據最佳編碼定理，通過以上例子的分析，我們得出結論：在編碼的過程中，對縮減信源符號按概率由大到小得順序重新排列時，應將相加后的新概率盡可能的排在其他相同概率之前，這樣就可以使相加后的新符號概率重復編碼的次數減少，使得短碼得到充分利用。

參考文獻

[1]陳運.信息論與編碼.北京：電子工業出版社. 2009

[2]姜丹.信息論與編碼.合肥：中國科技技術大學出版社. 2001

[3]傅祖蕓.信息論與基礎.北京：電子工業出版社. 2006

[4]鐘家愷.通信原理教程.北京：科學出版社. 2003

[5]鐘玉琢.多媒體技術基礎與應用.北京：清華大學出版社，2008