有一个问题很想弄清楚:LZW算法的字典为什么可以丢弃?

clonne 发布于 2012/07/01 19:08
阅读 321
收藏 0

 我的网上搜索LZW,一般都会有如下介绍:”LZW压缩算法是一种新颖的压缩方法,由Lemple-Ziv-Welch 三人共同创造,用他们的名字命名。它采用了一种先进的串表压缩,将每个第一次出现的串放在一个串表中,用一个数字来表示串,压缩文件只存贮数字,则不存贮串,从而使图象文件的压缩效率得到较大的提高。奇妙的是,不管是在压缩还是在解压缩的过程中都能正确的建立这个串表,压缩或解压缩完成后,这个串表又被丢弃。“

让我感到困惑的是为什么这个串表(字典)可以丢弃?在我的认识中,就像霍夫曼算法,是必须要将字典和压缩后的数据一并输出,不然无法解压缩(没有字典对应)。但是为什么LZW可以不用输出字典?我一直无法理解,是根本理解不了,难道说LZW的串表(字典)可以无中生有?还能自动对应原数据?

加载中
0
H
HanAnthony

并不是完全不需要字典的,因为encoding/decoding时的初始字典,是约定好的。这2个过程中动态增加字典中字符的位数也是约定好的,每次不够了就+1位。由此在编码/解码过程中,产生的字典就是一致的。

因为是无损,字典又是从数据中抽象的,因此只要数据都在,字典就会还原。

0
中山野鬼
中山野鬼

字典的全部已经被基本信息以及动态的压缩信息所表示,因此可以通过解码时,恢复出全部字典。这样做的好处是提高了压缩率,缺点是,整个压缩后的串,关联性提高,由此,错一个,后面全错。

冗余和压缩量本身就是矛盾的。极至的通常都没有实际意义。关键看工程上,实际环境和应用需求,做折中处理。

返回顶部
顶部