原创 Huffman解码

解码是编码的逆过程，即是根据码字查询Huffman码表，还原出初始值。 mp3音频帧的数据包括比例因子和经过Huffman编码的数据，有边带信息参量可以计算处单个声道内的比例因子的总长度。Huffman解码还原出576条频率线从低频到高频分为三个区域：大值区、小值区和零值区。只有大值区和小值区会出现在mp3的码流中，零值区的频率线值全为0，因此不用编码也不必出现在mp3码流中。大值区： 每个huffman码字对两个频率线x 和y 进行编码，参量big_values表示大值区Huffman码字的总个数，因此大值区可以解码得 big_values x 2 个频率线。被编码的频率线值小于等于15，如果超过15则只对15进行编码，超过部分表示成扩展值，放在Huffman码字之后。 大值区的32个Huffman码表使用前16个Huffman码表进行编码的主数据纯粹由Huffman码字组成，不包含扩展值，且表0 为零值表，表4 和表14未使用。后16个Huffman码表均包含扩展值，表明码字后面可能带有扩展值。 小值区使用两个特殊的Huffman码表，具体的码表选择信息有参量countable_seclect提供，此区域的Huffman码字对4个频率线v，w，x，y进行编码，且每个频率线只有3种可能的值，分别为-1，0，1,被编码数据非0 时，符号位单独传送。 零值区的频率线值全为0，不出现在码流中，解码时只需要对其补0，直至共得到576个解码值。 为了减少Huffman码表的存储空间，采用Huffman树存储码表，生成一个二叉树，将码表装入其中即可得Huffman树，使用二叉树搜索算法的存储空间利用率较好，且控制简单，不过相对处理速度较慢，需要逐个bit进行判断。

原帖：http://blog.sina.com.cn/s/blog_6840802c0100ir67.html