範式霍夫曼編碼

範式霍夫曼編碼(英語:Canonical Huffman Code)是一種特殊的霍夫曼編碼,最早由Schwartz(1964)所提出。

資料的編解碼運作方式中,以霍夫曼編碼來舉例,編解碼器的其中一方必須要知道霍夫曼樹的結構資訊,以便還原。所以其中一方必須儲存或傳輸霍夫曼樹。傳統的霍夫曼編碼使用樹狀模型編碼,給出現概率或頻率較高的符號(Symbol)較短的編碼,以提高壓縮率。但是這個方式造成兩個極大的缺點,第一,每一個樹的節點都要儲存有關它的父節點與子節點等等相關資訊,如果符號集合的數量包含許多不同概率的符號,記憶體的負荷量會明顯增大許多。第二,霍夫曼樹的追蹤需要耗費極大的運算量。所以基於以上兩個論點,傳統的霍夫曼編碼是一種極為消耗儲存空間且沒有效率的方式。

而範式霍夫曼編碼修正了這些缺點,藉由一些原則以達成利用較少的數據便能還原霍夫曼編碼的功能。範式霍夫曼編碼要求相同長度編碼必須是連續的,例如:長度為4的編碼0001,其他相同長度的編碼必須為0010、0011、0100...等等。為了盡可能降低儲存空間,編碼長度為的第一個符號可以從編碼長度為的最後一個符號所得知,即,例如:從長度為3的最後一個編碼100,可推知長度為4的第一個編碼為1010。最後,最小編碼長度的第一個編碼必須從0開始。範式霍夫曼編碼通過這些原則,便可以從每個編碼還原整個霍夫曼編碼樹。

演算法

假設我們有一組霍夫曼編碼與其相對應的符號:

F:000
O:001
R:100
G:101
E:01
T:11


首先我們先對符號進行排序,排序方式由

1. 編碼長度短至長排列
2. 字母在英文單字中的次序
E:01
T:11
F:000
G:101
O:001
R:100


接着,照下列方式依序給予新的編碼:

1. 第一個符號的編碼方式是依照符號的編碼長度給予相同長度的'0'值
2. 對接下來的符號的編碼+1,保證接下來的編碼大小都大於之前
3. 如果編碼較長,位元左移一位並補0
E:01  →  00                 按照1. 
T:11 → 01 依照2.
F:000 → 100 依照2.&3.
G:101 → 101 依照2.
O:001 → 110 依照2.
R:100 → 111 依照2.


依照上述演算法將霍夫曼碼變成範式霍夫曼碼。

而解碼的方式可由:

1. 範式霍夫曼碼的順序(後面編碼大小必定大於前面)
2. 編碼長度為   的第一個符號可以從編碼長度為   的最後一個符號所得知,即