文档章节

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

暗之幻影
 暗之幻影
发布于 2015/01/04 15:29
字数 1290
阅读 19
收藏 0

      哈夫曼(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”:

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比特:

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值

 

解码小值区得到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”内的数据去检查。

 

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

本文转载自:http://lfp001.iteye.com/blog/737850

暗之幻影
粉丝 20
博文 377
码字总数 71245
作品 0
南京
高级程序员
私信 提问
AAC 文件解析及解码流程(音频术语aac he lc等及其功能性的描述)

OUTLINE: * AAC概述 * AAC规格简述 * AAC特点 * AAC音频文件解析 ——ADIF&ADTS格式 ——ADIF&ADTS头信息 ——ADIF&ADTS数据信息 ——AAC文件处理流程 * AAC解码流程 ——技术解析 ...

张旭0512
2014/11/05
1K
0
数据结构与算法之9(哈夫曼编解码与广度优先搜索)

》哈夫曼编码 在二叉树最后的例子里的最后提到了哈夫曼树,个人感觉不是很好理解,为大家找到了一个篇讲的比较简洁明了的http://blog.csdn.net/jinixin/article/details/52142352,就不再造轮...

kkae8643150
2017/11/27
0
0
Android 中图片压缩分析(上)

作者: shawnzhao,QQ音乐技术团队 一员 一、前言 在 Android 中进行图片压缩是非常常见的开发场景,主要的压缩方法有两种:其一是质量压缩,其二是下采样压缩。 前者是在不改变图片尺寸的情...

腾讯云社区
2017/11/13
0
0
JPG文件编解码详解——详细介绍编码和解码JPG

http://blog.csdn.net/zhengzhoudaxue2/article/details/7693258 JPEG文件编/解码详解 cat_ng 猫猫 JPEG(Joint Photographic Experts Group)是联合图像专家小组的英文缩写。它由国际电话与...

stn_lcd
2017/11/24
0
0
gzip压缩文件损坏的修复方法

修复一个损坏的gzip文件的关键环节在于找到下一个正常压缩包的起始点。根据结构图中的信息可知,每个压缩包的开始结构中有是否到达尾部标志、使用的哈夫曼树类型、以及3个哈夫曼树的树元素个...

宋国建
2018/05/31
0
0

没有更多内容

加载失败,请刷新页面

加载更多

移动开发中的 Web:WebView、WebKit、JSCore、Web 优化、热修复、跨平台、Native、Hybrid……

移动开发领域近年来已经逐渐告别了野蛮生长的时期,进入了相对成熟的时代。而一直以来 Native 和 Web 的争论从未停止,通过开发者孜孜不倦的努力,Web 的效率和 Native 的体验也一直在寻求着...

编辑部的故事
11分钟前
8
0
MySQL8.0.17 - Multi-Valued Indexes 简述

本文主要简单介绍下8.0.17新引入的功能multi-valued index, 顾名思义,索引上对于同一个Primary key, 可以建立多个二级索引项,实际上已经对array类型的基础功能做了支持 (感觉官方未来一定...

阿里云官方博客
57分钟前
9
0
make4.1降级 make-3.81、2错误

在编译 make-3.82 的时候出现如下错误提示 glob/glob.c:xxx: undefined reference to `__alloca'` 修改 /glob/glob.c // #if !defined __alloca && !defined __GNU_LIBRARY__ # ifdef __GNUC......

Domineering
58分钟前
13
0
Rainbond集群的安装和运维的原理

本文将解读Rainbond集群的安装和运维的原理,使用户基本了解Rainbond的安装机制和运维重点,便于用户搭建大型Rainbond集群。 1.Rainbond集群节点概述 1.1 节点分类 属性 类型 说明 manage 管...

好雨云帮
今天
10
0
好程序员大数据学习路线分享UDF函数

1.为什么需要UDF? 1)、因为内部函数没法满足需求。 2)、hive它本身就是一个灵活框架,允许用自定义模块功能,如可以自定义UDF、serde、输入输出等。 2.UDF是什么? UDF:user difine fun...

好程序员官方
今天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部