簡述霍爾曼編碼原理？

原理

赫夫曼編碼可以很有效地壓縮數據: 通常可以節(jié)省20%-90%, 具體的壓縮率依賴于數據的特性;

若將待壓縮數據看做是字符序列, 根據每個字符的出現(xiàn)頻率, 赫夫曼貪心算法構造出字符的最優(yōu)二進制表示, 即霍夫曼編碼.

二進制字符編碼(binary character code, 簡稱編碼 code ), 即每個字符用唯一 的二進制串表示, 這個二進制串也稱為碼字(codeword).

編碼可以分為定長編碼(fixed-length code)和變長編碼(variable-length code).

定長編碼采用固定長度的碼字表示字符; 變長編碼對不同字符, 采用不同長度的碼字, 其思想是通過賦予高頻字符短碼字, 賦予低頻字符長碼字, 從而達到比定長編碼更好的壓縮率.

前綴碼(prefix code)是一種典型的變長編碼, 這種編碼方式中沒有任何碼字是其他碼字的前綴.

任何二進制字符碼的編碼過程(encoding)都很簡單, 只要將表示每個字符的碼字連接起來,即可完成數據的壓縮;

前綴碼的作用是簡化解碼過程(decoding), 這是由于沒有碼字是其他碼字的前綴, 編碼數據的開始碼字是無歧義的. 只要簡單地識別出開始碼字, 將其轉換為原字符, 然后對編碼數據的剩余部分重復這種解碼過程.

為了容易截取開始碼字, 解碼過程需要以某種方便形式表示前綴碼. 這里采用二叉樹表示前綴碼, 其葉節(jié)點為給定字符. 字符的二進制碼字用從根節(jié)點到該字符葉節(jié)點的簡單路徑表示.

數據的最優(yōu)編碼(optimal code)方案總是對應著一棵滿二叉樹(full binary tree). 可以采用反證法證明: 若某個最優(yōu)編碼不是滿二叉樹, 則存在某個內部結點, 有空的左子樹或右子樹, 此時, 如果將這個內部結點的編碼直接設置為非空的右子樹或左子樹的編碼, 這樣會使經過這個內部結點的所有字符碼字長度少1, 可獲得比當前假設的最優(yōu)編碼樹, 與原假設矛盾, 所以最優(yōu)編碼總是對應著一棵二叉樹.

若 C 為字母表, 且每個字符出現(xiàn)的頻率均為正數, 則最優(yōu)前綴碼對應的滿二叉樹恰有 |C| 個葉節(jié)點, 每個葉節(jié)點對應字母表中的一個字符, 且恰有 |C| - 1個內部結點. 證明方法采用不同思路計算滿二叉樹結點總數, 從而得到葉節(jié)點和內部結點的數量關系: 首先定義結點的度的概念, 在有根樹中，一個結點的孩子結點的個數稱為該結點的度．滿二叉樹的結點總數一方面可以表示為度為0的結點數 n0 ＋度為１的結點數n1 + 度為2 的結點數 n2, 即 n0 + n1 + n2；另一方面，結點總數可以表示為度為１的結點的孩子結點數 n1 + 度為2 的結點的孩子結點數 2 * n2 + 1（不屬于任何結點的孩子的根節(jié)點），即n1 + 2 * n2 + 1 , 所以有 n0 + n1 + n2 = n1 + 2 * n2 + 1, 從而有 n0 = n2 + 1, 而度為 0 的結點也就是葉子結點, 即 n0 為葉子結點的個數, 在滿二叉樹中, 不存在度為 1 的結點, 只有度為 2 的結點, 即 n2 為滿二叉樹的內部結點的個數, 如此,就證明了對于滿二叉樹, 內部結點數比葉子結點少 1.

給定一棵對應前綴碼的樹 T ,可以很容易地計算出編碼一個數據或文件所需的二進制位數. 例如對于字母表 C 中的每個字符 c , 令屬性 c.freq 表示 c 在文件或數據中出現(xiàn)的頻率, 令 dT(c) 表示 c 的葉節(jié)點在樹中的深度(根節(jié)點的深度為 0), 同時也表示字符 c 的碼字的長度.編碼文件或數據需要的二進制位數為

B(T) 也被定義為樹 T 的代價(cost).

赫夫曼算法的偽代碼, 如下所示

上圖的偽代碼中, 假定 C 是一個 n 個字符的集合, 而其中的每個字符 c 都是一個對象, 其屬性 c.freq 為字符 c 出現(xiàn)的頻率. 算法自底向上構造出最優(yōu)編碼的二叉樹 T. 它從|C|個葉節(jié)點開始, 執(zhí)行|C|-1個"合并"操作創(chuàng)建出最終的二叉樹. 具體來說, 算法使用一個以屬性 freq 為關鍵字的最小優(yōu)先隊列Q, 以識別兩個最低頻率的對象, 然后將其合并為一個新節(jié)點,并替代它們. 當合并兩個對象時, 得到的新對象的頻率設置為原來兩個對象的頻率之和. 經過 |C|-1 次的合并后, 返回優(yōu)先隊列Q中唯一結點, 即編碼樹的根節(jié)點.