语音处理:霍夫曼编码算法原理分析
前言
分类
:无损编码中常见的为熵编码,主要分为霍夫曼编码和算术编码。霍夫曼编码是无损编解码中的经典压缩算法。效果
:如果没有压缩算法,一张未经压缩的2M图片,同样内存可以放下70万字的鸿篇巨著红楼梦。特点
:霍夫曼编码虽无法达到算术编码逼近信息熵极限的压缩效率,但由于算法简单、实现优美且可以避免大量算术编码的专利封锁,应用十分广泛,如mp3、aac、jpeg等均采用了此算法。
霍夫曼编码解密
本文结合文章《JPEG算法解密(四):霍夫曼编码》进行分析解读,有兴趣的读者可相互参照,增进理解。
jinchao霍夫曼思路分析:
效果:将64个byte数据,无损压缩成10byte,压缩率达84%
- 霍夫曼核心:RLE编码 + BIT编码
- 数据分组
- 原则:0最高频,优先分组
- 若无零,则非零组成一组
- 若有零,则连续零+非零形成一组
- 若组内0个数超过16,则拆分
- 最后形成单组:
0, 0, 0, ..., val
- RLE编码过程
- 一个组形成一对
(zero_count, val)
zero_count
表示0的个数val
表示结尾的数值- 若为最后一个组且全零,则单独编EOB
- 根据值范围,设计码本
- 结构体:
val, size, bit
- 结构体:
- 对
val
编码,得到size
和bit
(zero_count, val)
组成新数据(zero_count, size, bit)
- 将zero_count和size合并成一个 byte,高四位给zc,低四位给size
- 得到
(new_val, bit)
,前者为直流数据,后者为交流数据
- 一个组形成一对
- BIT编码过程
- 对
new_val
进行霍夫曼编码 - 数组第一个是DCT变换后的直流部分,表征总体能量,用第一个霍夫曼码本表示
- 之后的分组数据为交流部分,用第二个霍夫曼码本表示
- 查表得到霍夫曼编码结果,最后将其组合
- 对
个人理解:
- 疑惑点
- 第1、2个霍夫曼码本咋来的?
- 编码后的01数据如何解码呢?
- 压缩效果对比:
- 压缩前,64个数据,需64个字节
- 压缩后,只需10个字节
扩展资料
- 恒泽aac/mp3中的霍夫曼编码,https://www.cnblogs.com/gaozehua/archive/2012/05/08/2489483.html
- jpeg图像压缩原理,DCT变换,https://www.cnblogs.com/Arvin-JIN/p/9133745.html
- 霍夫曼编码清晰易懂, https://thecodeway.com/blog/?p=522
- DCT变换中DC系数和AC系数,https://blog.csdn.net/qingkongyeyue/article/details/58130001