范式哈夫曼编码的快速解码技术

1 引言

对前缀编码进行解码时，最重要的问题是如何快速的确定码字的长度。范式哈夫曼编码具有数字序列属性，因而能通过如下算法确定码字的长度：

int len = 1;
 int code = bs.ReadBit();
 while(code >= first[len])
 {
   code <<= 1;
   code |= (bs.ReadBit()); // append next input bit to code
   len++;
 }
 len--;

另一方面，上述算法逐位进行操作，因而效率不高。快速解码算法的开发便是针对上述两个速度瓶颈而进行的。

1 一个小的改进^[1]

首先看一个定理：
对于任意的两个规范哈夫曼码字w1, w2, 其码长分别为l1, l2.如果l1

I(w1 1^(lmax-l1)) < I(w2 0^(lmax-l2)).

其中lmax为码字的最大长度，1^(lmax-l1)表示lmax-l1个1, w1 1^(lmax-l1)表示w1的二进制序列后面跟lmax-l1个1.w2 0^(lmax-l2)类似. I(w1 1^(lmax-l1))表示二进制序列w1 1^(lmax-l1)的整数值(无符号)。

证明：定义minword[i]为码长为i的码字的最小值，maxword[i]为码长为i的码字的最大值。那么有：
minword[1] = 0
maxword[i] = minword[i]+count[i]-1; // 数字序列属性
minword[i] = 2*(maxword[i-1]+1) = 2*(minword[i-1]+count[i-1])
<==> 
minword[i+1] = (maxword[i]+1)<<1
<==>
minword[i+1] 0^(lmax-(i+1)) = (maxword[i]+1)<<1 0^(lmax-(i+1)) = (maxword[i]+1) 0^(lmax-i)
= (maxword[i] 1^(lmax-i)) +1
<==> minword[i+1] 0^(lmax-(i+1)) > maxword[i] 1^(lmax-i) > minword[i] 1^(lmax-i) > 
minword[i] 0^(lmax-i) > maxword[i-1] 1^(lmax-(i-1)) ......
再有 minword[l1] <= w1 <= maxword[l2]，所以得证。
根据上述定理，我们对first[len]进行扩展，把它们都变为固定的lmax位长，代码如下：

for(len=1; len   minvalue[len] = first[len] << (lmax-len);

然后我们可以根据下述代码确定一个有效码长：

len = 1;
 int code = bs.ReadBits(lmax);
 while(code >= minvalue[len])
   len++;
 len--;

最后,根据以下代码解出正确的符号：

int index = index[len] + ((code-minvalue[len]) >> (lmax-len));
 int sym = symbol[index];

上述算法的一个优点就是不用逐位操作，一定程度上提高了解码的效率。对于该算法，在确定码长的代码上还能有所改进，可以将minvalue做成一棵二叉树^[2] ，然后使用这颗二叉树可以更快地确定出码长。

2 基于固定位长的查表算法^[3,4]

上述改进虽然缓解了逐位操作的瓶颈，但还是需要计算码长，本节将讨论一种不需要计算码长的查表算法。

假定码字的最长长度为maxlen，那么解码算法可以每次固定读取maxlen或大于maxlen的位。所读的位串包含0或多个可判读的码字以及仍未解码的"剩余"部分，这些"剩余"位串是下一个码字的前缀。根据可判读的码字输出相应的符号，利用"剩余"部分索引下一个查找表，继续读入下一个位串。

这种方法所需要的查找表的数目等于不同的码字前缀的数目，即等于哈夫曼数的内部节点数: N-1
每一个查找表有2^k个记录, 相当于长度为k的二进制串的数目。
每个解码步骤输出的符号数在0-k之间。
空间需求O(2^k(N-1))。

int index = 0; // 初始化查找表
 while(!end)
 {
   int code = bs.ReadByte(); // 假定maxlen = 8
   output(table[index][code].symbols); // 输出可判读的符号
   index = table[index][code].rest; // 用“剩余”部分索引下一个查找表
 }

例子:
a=000;  f=0110;  k=10101;
b=0010;  g=0111;  ...
c=0011;  h=1000;  u=11111;
d=0100;  i=1001;
e=0101;  j=10100;

以每次读取8位为例,
table[0][00000000b].symbols = a, a;
table[0][00000000b].rest = index['00']; ==> 链接到以00为前缀的副表,比如说1
table[0][00000001b].symbols = a, a;
table[0][00000001b].rest = index['01']; ==> 链接到以01为前缀的副表,比如说2
......
table[0][00100011b].symbols = b, c;
table[0][00100011b].rest = 0; ==> 由于剩余部分为空,所以表格索引退回到主表0
......

下面看索引为1的附表. 由上面可知,1号副表以00b为前缀,所以table[1][00000000b]相当于解码0000000000b,即
table[1][00000000b].symbols = a, a, a;
table[1][00000000b].rest = index['0']; 链接到以0为前缀的副表
......

优点: 完全克服了上述两个瓶颈，解码速度快, 并且可用不支持位操作的高级语言实现解码器。
缺点: 空间要求大, 初始化查找表费时。

3 一种改进的查表算法

上述解码算法虽然效率较高，但当maxlen较大时，表的初始化将耗费较多时间和空间，不适用于小量数据解码和存储紧张的场合。鉴于此，[5]提出了一种改进的查表算法。该算法通过两点改进大大压缩了表格的空间.首先,每次只输出一个符号,并在表中新增一个length域表示该符号编码的长度.这样一来,可以不再需要用"剩余"部分索引的副表了,相应的解码算法如下:

while(!end)
 {
   bs.NeedBits(maxlen);
   int value = bs.Bits(maxlen);
   output(table[value].symbol);
   bs.DropBits(table[value].length);
 }

其次, 每次我们只固定的读取合适的位数b，b不一定要等于maxlen，只要把b控制在合适的范围内，那么主查找表的空间O(2^b)可以进一步得到压缩。但这样一来，每次读取b位时有2种可能：1. b位能解出一个码字; 2. b位只是某些码字的前缀，需要读取更多的位才能解码。对于第2种可能况又有两种情况：2.1. 以此b位为前缀的码字都具有相同的长度，因而能根据这b位唯一地确定码长。比如当b=4时，以1010为前缀的码字长度均为5: 'j'和'k'; 2.2. 以此b位为前缀的码字具有不同的长度，无法根据b位确定出码长。比如当b=2时，以10开头的码字有'h', 'i', 'j', 'k', ... ，无法唯一的确定码长。我们将第1种情况标记为SHORT_CODE,其解码算法同上; 对于2.1种情况,我们在symbol域保存第一个以此b位为前缀的码字的索引,length域保存还需要读取的位数,其解码算法如下:

 bs.NeedBits(b);
  int value = bs.Bits(b);
  if(table[value].flag == SAME_LENGTH)
  {
    bs.DropBits(b);
    bs.NeedBits(table[value].length);
    output(symbol[table[value].symbol+bs.Bits(table[value].length)]);
    bs.DropBits(table[value].length);
  }

对于2.2种情况,需要确定以此b位为前缀的码字的最长长度,设为c,那么我们需要构建一个空间大小为O(2^(c-b))的副表,利用此副表来进一步进行解码.此时,symbol域保存的是副表的起始索引(假定副表和主表保存在同一个大数组内),length=c-b.相应的解码算法如下:

 bs.NeedBits(b);
 int value = bs.Bits(b);
 if(table[value].flag == MEDIUM_CODE)
 {
  bs.DropBits(b);
  bs.NeedBits(table[value].length);
  index = table[value].symbol+bs.Bits(table[value].length);
  output(table[index].symbol);
  bs.DropBits(table[index].length);
 }

另外,为了防止c远大于b时,副表的空间耗费增大,我们定义第3种情况LONG_CODE,此时我们使用改进1中的算法确定码长:

 bs.NeedBits(b);
  int value = bs.Bits(b);
  if(table[value].flag == LONG_CODE)
  {
    bs.NeedBits(b+table[value].length);
    value = bs.Bits(b+table[value].length);
    int len = b+1;
    while(value >= minvalue[len])
    {
      len++;
    }
    len--;
    int index = index[len] + ((value-minvalue[len]) >> (b+table[value].length-len));
   ouput(symbol[index])
   bs.DropBits(len);
  }

当然,上述代码中也可以使用二叉树搜索len以提高速度.

4 Inflate的解码方法

inflate是GZip, PNG等广泛使用的解压算法,linux也使用inflate对内核进行解压.inflate的解压算法使用的第3种快速解压法的一个子集,它不考虑LONG_CODE,同时把SAME_LENGTH合并到MEDIUM_CODE。而对于规则的SAME_LENGTH编码，比如length和distance编码，inflate则使用额外的base和extra表示。这是因为在构造一般的查找表时，虽然对于SAME_LENGTH前缀可以不构造副表，但我们需要另外一个表格来保存符号的顺序，而这个表格的空间可能更大。但对于length和distance编码，他们的顺序是递增的，所以无需额外的表格来保存符号的顺序。

inflate使用root表示上述的b,查找表的数据结构为code.主表和副同时保存在inflate_state结构中的大数组codes[ENOUGH]中.表的构造函数位于inftrees.c文件的inflate_table中.

5 参考文献

[1] Moffat A. and Turpin A., "On the Implementation of minimum redundancy prefix codes", IEEE Transactions on Communications, vol. 45, No. 10, 1200 - 1207.
[2] Nekrich Y., "On efficient decoding of Huffman codes", Technical Report No.85190-CS, Department of Computer Science, Bonn University, April 1998.
[3] Shmuel T.Klein, "Space- and time- efficient decoding with canonical Huffman trees", 8th Annual Symposium on Combinatorial Pattern Matching, Aarhus, Denmark, 30 June-2 July 1997, Lecture Notes in Computer Science, vol. 1264, 65-75.
[4] Sieminski A., "Fast decoding of the Huffman codes", Information Processing Letters, vol.26, 1988, 237-241.
[5] Nekrich Y., "Decoding of Canonical Huffman Codes with Look-Up Tables", Data Compression Conference 2000, 28-30 March 2000, Snowbird, Utah, USA