当前位置:文档之家› 无损压缩算法的比较和分析

无损压缩算法的比较和分析

Adaptive-Huffman-Coding 自适应霍夫曼编码
压缩比:1.79
分析:
霍夫曼算法需要有关信息源的先验统计知识,而这样的信息通常很难获得,即使能够获得这些统计数字,符号表的传输仍然是一笔相当大的开销。

自适应压缩算法能够解决上述问题,统计数字是随着数据流的到达而动态地收集和更新的。

概率再不是基于先验知识而是基于到目前为止实际收到的数据。

随着接收到的符号的概率分布的改变,符号将会被赋予新的码字,这在统计数字快速变化的多媒体数据中尤为适用。

Lempel-Ziv-Welch 基于字典的编码
压缩比:1.86
分析:
LZW算法利用了一种自适应的,基于字典的压缩技术。

和变长编码方式不同,LZW使用定长的码字(本次实验使用12位定长码字)来表示通常会在一起出现的符号/字符的变长的字符串。

LZW编码器和解码器会在接受数据是动态的创建字典,编码器和解码器也会产生相同的字典。

编码器的动作有时会先于解码器发生。

因为这是一个顺序过程,所以从某种意义上说,这是可以预见的。

算术编码(arithmetic coding)
压缩比:2
分析:
算术编码是一种更现代化的编码方法,在实际中不赫夫曼编码更有效。

算术编码把整个信息看作一个单元,在实际中,输入数据通常被分割成块以免错误传播。

算术编码将整个要编码的数据映射到一个位于[0,1)的实数区间中。

并且输出一个小于1同时大于0的小数来表示全部数据。

利用这种方法算术编码可以让压缩率无限的接近数据的熵值,从而获得理论上的最高压缩率。

比较分析:
一般来说,算术编码的性能优于赫夫曼编码,因为前者将整个消息看作一个单元,而后者受到了必须为每一个符号分配整数位的限制。

但是,算术编码要求进行无限精度的实数运算,这在仅能进行有限精度运算的计算机系统是无法进行的。

随着研究的深入,有学者提出了一种基于整数运算的算术编码实现算法。

在编码和解码的过程还需要不时的调整区间大小,以免精度不足,加大了实现的难度。

在3种无损压缩算法中,LZW算法相对来说,实现最为简单,但其压缩效果要在数据源足够大的时候,才能显现出来。

相关主题