范式哈夫曼编码(Canonical Huffman Code)

1 概念介绍

哈夫曼编码是一种最优的前缀编码技术，然而其存在的不足却制约了它的直接应用。首先，其解码时间为O(lavg), 其中lavg为码字的平均长度；其次，更为最重要的是，解码器需要知道哈夫曼编码树的结构，因而编码器必须为解码器保存或传输哈夫曼编码树。对于小量数据的压缩而言，这是很大的开销。因而，应用哈夫曼编码的关键是如何降低哈夫曼编码树的存储空间。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开始。通过上述约定，解码器能根据每个码字的长度恢复出整棵哈夫曼编码树的结构。

2 码字构造

假设有如下的码长序列：
 符号：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

3 解码算法

范式哈夫曼编码有一个很重要的特性：长度为i的码字的前j位的数值大于长度为j的码字的数值，其中i > j。如上例中的最小五位码10100，它的前四位1010大于任何的四位码。由这个特性，很容易构造出范式哈夫曼编码的解码算法：
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。

4 其他特性

对于长度为i的码字而言，count[i] <= (2^i)-first[i]。其中等号仅对最大长度的码字成立。
如果对于码字的最大长度imax，count[imax] < (2^imax)-first[imax]，那么称输入的码字长度序列为不完全集。

参考文献

[1] Faller, N. 1973. An Adaptive System for Data Compression. Record of the 7th Asilomar Conf. on Circuits, Systems and Computers (Pacific Grove, Ca., Nov.), 593-597.