基本介紹
- 中文名：範式哈夫曼
- 釋義：最優的前綴編碼技術
- 不足：解碼時間為O
- 關鍵：降低哈夫曼編碼樹的存儲空間
概念介紹,碼字構造,解碼算法,其他特性,
概念介紹
Faller[1973]提出的自適應哈夫曼編碼技術使哈夫曼編碼樹的存儲空間降為零，即在使用某種約定的情況下，解碼器能動態地重構出和編碼器同步的哈夫曼編碼樹，而不需要任何附加數據。這樣做的代價便是時間開銷的增大。另一種技術是編碼器和解碼器使用事先約定的編碼樹，這種方法只能針對特定數據使用，不具備通用性。另外一種，也是最為常用的方法，便是範式哈夫曼編碼。現在流行的很多壓縮方法都使用了範式哈夫曼編碼技術，如GZIB、ZLIB、PNG、JPEG、MPEG等。
範式哈夫曼編碼最早由Schwartz[1964]提出，它是哈夫曼編碼的一個子集。其中心思想是：使用某些強制的約定，僅通過很少的數據便能重構出哈夫曼編碼樹的結構。其中一種很重要的約定是數字序列屬性(numerical sequence property)，它要求相同長度的碼字是連續整數的二進制描述。例如，假設碼字長度為4的最小值為0010，那么其它長度為4的碼字必為0011, 0100, 0101, ...；另一個約定：為了儘可能的利用編碼空間，長度為i第一個碼字f(i)能從長度為i-1的最後一個碼字得出, 即：f(i) = 2(f(i-1)+1)。假定長度為4的最後一個碼字為1001，那么長度為5的第一個碼字便為10100。最後一個約定：碼字長度最小的第一個編碼從0開始。通過上述約定，解碼器能根據每個碼字的長度恢復出整棵哈夫曼編碼樹的結構。
碼字構造
假設有如下的碼長序列：
符號：a b c d e f g h i j k ... u
碼長：3 4 4 4 4 4 4 4 4 5 5 ... 5
使用count[i]表示長度為i的碼字的數目，first[i]表示長度為i的第一個碼字的整數值。根據約定3，即first[3] = 0可得到符號a的範式哈夫曼編碼為000。再根據約定2，可得到first[4] = 2*(first[3]+1) = 2，進一步可知b的編碼為0010。由約定1可構造出符號c的編碼為0011，由此類推可構造出整個碼字空間如下：
a=000(0); f=0110(6); k=10101(21);
b=0010(2); g=0111(7); ...
c=0011(3); h=1000(8); u=11111(31);
d=0100(4); i=1001(9);
e=0101(5); j=10100(20);
其中first[3] = 0, first[4] = 0010b = 2, first[5] = 10100b = 20
解碼算法
extern KBitInputStream bs;
int len = 1;
int code = bs.ReadBit();
while(code >= first[len])
{
code <<= 1;
code |= (bs.ReadBit()); // append next input bit to code
len++;
}
len--;
// 至此,識別出了一個前綴碼,下面將code解碼為其對應的符號sym
int index = index[len]+(code-first[len]);
int sym = table[index];
其中while循環用於確定碼長，這也是解碼算法中至關重要的一步，確定碼長的算法效率影響著整個解碼算法的效率。比如說我們要解碼100110100序列，當循環至len=4的時候，code等於1001，大於len[4]，因而循環繼續，繼續讀取下一位，code=10011, len=5，小於len[5]=10100,所以循環結束，執行下面的len--代碼，得到了正確的碼字長度4。算法實現需要注意幾點：一定要使用code >= first[len]，而不是code > first[len]；另外，len--不能少。
代碼中index[len]表示長度為len的第一個碼字的索引，index[3] = 0, index[4] = 1, index[5] = 9。不難發現，index[i] = count[i-1]+count[i-2]+...+count[1]+count[0]，其中count[0] = 0。
其他特性
對於長度為i的碼字而言，count[i] <= (2^i)-first[i]。其中等號僅對最大長度的碼字成立。如果對於碼字的最大長度imax，count[imax] < (2^imax)-first[imax]，那么稱輸入的碼字長度序列為不完全集。
