MP3解码之哈夫曼解码快速算法

      哈夫曼(huffman)解码用查表法，数据组织采用树形结构，若采用二叉树，一次处理一位(bit)，效率是比较低的。从一些杂志上看到关于哈夫曼(huffman)解码的快速算法介绍，直接用位流索引一次处理N(4<N<=32)位，这种方法实际上是不可行的，原因是构造出的码表很长，如果一次处理8位，可以编写程序构造出码表，不过可以肯定的是码表的长度会超过我们事先的想象，以至于没有多大的实用价值。一次处理多位（一位以上）码表中冗余度很大导致码表很长。

      MP3解码处理主数据（main_data）的第一步就是对主数据进行哈夫曼解码。MP3编解码用到的哈夫曼表由ISO/IEC 11172-3 的附录B中给出，大值区用到31张码表（其中第0、4、14号码表未使用），小值区用到两张码表。从ISO/IEC 11172-3复制出两张原始的码表来分析，解码大值区的码表：

Huffman code table 7
 x  y hlen hcod
 0  0   1   1
 0  1   3   010
 0  2   6   001010
 0  3   8   00010011
 0  4   8   00010000
 0  5   9   000001010
 1  0   3   011
 1  1   4   0011
 1  2   6   000111
 1  3   7   0001010
 1  4   7   0000101
 1  5   8   00000011
 2  0   6   001011
 2  1   5   00100
 2  2   7   0001101
 2  3   8   00010001
 2  4   8   00001000
 2  5   9   000000100
 3  0   7   0001100
 3  1   7   0001011
 3  2   8   00010010
 3  3   9   000001111
 3  4   9   000001011
 3  5   9   000000010
 4  0   7   0000111
 4  1   7   0000110
 4  2   8   00001001
 4  3   9   000001110
 4  4   9   000000011
 4  5  10   0000000001
 5  0   8   00000110
 5  1   8   00000100
 5  2   9   000000101
 5  3  10   0000000011
 5  4  10   0000000010
 5  5  10   0000000000

 

解码小值区的码表：

Huffman code table 17
 x  y hlen hcod
 0  0  1   1
 0  1  4   0101
 0  2  4   0100
 0  3  5   00101
 0  4  4   0110
 0  5  6   000101
 0  6  5   00100
 0  7  6   000100
 0  8  4   0111
 0  9  5   00011
 0  10 5   00110
 0  11 6   000000
 0  12 5   00111
 0  13 6   000010
 0  14 6   000011
 0  15 6   000001

 

      所有码表中取值范围是：x=0..15，y=0..15，码长hlen=1..19。

 

      一次处理多位应该如何实现呢？首先构造出码表，如果每次处理2比特，构造码表暂存数据时用4叉树；如果一次处理3比特，则用8叉树，以此类推。编程从一个文本文件中读入如上所示的原始的哈夫曼表数据，将其插入到N叉树中相应的位置。假如一次处理2位而码字（hcod）是5位（hlen=5），那么在hcod最后分别补上0和1凑足2的整数倍位数，这就导致了构造出的哈夫曼表冗余度，即一个码字对应多个码表中元素。一次处理的位数越多，构造出的码表的冗余度越大。

 

      根据自己解码设计构造出码表比较费事，解码过程挺简单。

 

      实际编程中，可以用数组来存储N叉树，只需要将指针域的值改为元素在数组中的下标值。以大值区解码一次处理2比特为例，x和y取值范围为0..15，只需占用4比特；码长hlen取值范围为1..19，存储hlen只需5比特。存储一个码值只需要13比特，可以将一个码值存储在16位整数中，低4位是y，接下来的4位是x，再接下来的5位是hlen。高3位全为零表示该数组元素存储的是一个码值，最高位为1（表示负数）则其绝对什表示该数组元素存储的是数组的下标值。经过这样处理后解码大值区的码表“Huffman code table 7”一次处理2位，是4叉树：

static short htbv7[72] = {
  -4, -68, 256, 256,  -8, -48, -64,1041, -12, -28, -40, -44, -16, -20, -24,2069,
2645,2629,2644,2643,2357,2357,2372,2372,2341,2341,2386,2386,2129, -32,2128, -36,
2309,2309,2356,2356,2371,2371,2355,2355,2084,2114,1812,1812,1857,1857,1856,1856,
 -52, -56, -60,1554,2052,2083,2098,2051,1811,1811,1841,1841,1840,1840,1826,1826,
1313,1313,1538,1568, 769, 769, 784, 784};

 

      解码小值区的码表“Huffman code table 17”一次处理4位，是16叉树：

static short htc0[80] = {
 -16, -32, -48, -64,1026,1025,1028,1032, 256, 256, 256, 256, 256, 256, 256, 256,
1547,1547,1547,1547,1551,1551,1551,1551,1549,1549,1549,1549,1550,1550,1550,1550,
1543,1543,1543,1543,1541,1541,1541,1541,1289,1289,1289,1289,1289,1289,1289,1289,
1286,1286,1286,1286,1286,1286,1286,1286,1283,1283,1283,1283,1283,1283,1283,1283,
1290,1290,1290,1290,1290,1290,1290,1290,1292,1292,1292,1292,1292,1292,1292,1292};

 

      码表构造好了，如何解码呢？由位流索引查表，从码流中读入4字节暂存到unsigned int umask，解码大值区得到x和y：

y = ptab[umask >> 30];	// 一次处理2比特，ptab指向码表（如ptab=htbv7）
while (y < 0) {
	umask <<= 2;
	y = ptab[(umask >> 30) - y];
}
x = y >> 8;		// hlen
num -= x;			// num为umask中剩余的比特数
umask <<= x;
x = (y >> 4) & 0xf;		// 得到x值
y &= 0xf;			// 得到y值

       1--5行为查表过程，一次处理的位数越多，执行循环的次数越少。9--10行得到原始码表中的x、y值，对x、y进一步处理就解得哈夫曼码值。

 

      解码小值区得到y值的代码：

y = ptab[umask >> 28];		// 一次处理4比特
while (y < 0) {
	umask <<= 4;
	y = ptab[(umask >> 28) - y];
}
x = y >> 8;	// hlen
num -= x;
umask <<= x;

y &= 0xf;		// 得到y值

 

      每解码完一个码字，重新刷新umask和num。以上解码方法正确与否可以用“Huffman code table 7”或“Huffman code table 17”内的一行数据根据源码去检查。

      以Huffman code table 7的一行“2  2   7   0001101”为例：这一行表示的意思是x=2，y=2，码长hlen=7，码字hcod=0001101；

• umask被刷新，前7位是0001101（第8位可能是0，也可能是1）。
• ptab指向解码大值区的htbv7[]，y = ptab[umask >> 30]=ptab[0]=-4；y<0，执行while循环。
• 第一次：umask <<=2，umask的最高2位被移出，umask的前5位变为01101（第6位可能是0，也可能是1），y = ptab[(umask >> 30) - y] =ptab[1-(-4)]=ptab[5]=-48<0；
• 第二次循环：umask <<= 2，umask的最高2位被移出，umask的前3位变为101（第4位可能是0，也可能是1），y = ptab[(umask >> 30) - y] =ptab[2-(-48)]=ptab[50]=-60<0；
• 第三次循环：umask <<= 2，umask的最高2位被移出，umask的最高位变为1（第2位可能是0，也可能是1），若umask第2位为0，y = ptab[(umask >> 30) - y] =ptab[2-(-60)]=ptab[62]=1826>0，结束循环；若umask第2位为1，y = ptab[(umask >> 30) - y] =ptab[3-(-60)]=ptab[63]=1826>0，结束循环。
• y=1826用二进制表示为11100100010，执行x = y >> 8 = 7，得到hlen；执行x = (y >> 4) & 0xf，先将y右移4位后y为1110010，再取y低4位y为0010，所以x = (y >> 4) & 0xf = 2，得到x；执行y &= 0xf取低4位（0010）得y = 2，得到y。
• 测试完毕。

      一次处理N比特肯定比一次处理1比特效率高。兼顾效率和存储空间开销，解码大值区采用一次处理2位到4位，解码小值区一次处理4位，这样比较好。

 

本文的“哈夫曼解码快速算法”的JAVA代码是jmp123开源项目的一部分。

【jmp123下载地址】http://jmp123.sourceforge.net/

硬是没有看明白， 好像现在有不少的快速算法， 正在研究～

写的有点简略，新补充了一个解码过程例子，看清解码过程容易点了。
解码过程比较简单，构造码表比较复杂一点。