编码方式

「LZW 编码」是一种无损压缩编码,通过消除图像中的像素间冗余来实现压缩。采用三个发明人姓氏首字母缩写命名。

LZW 编码是 Unix 操作系统的文件压缩标准方法,还应用于 GIF、TIFF 和 PDF 压缩文件中

  1. 初始字典:字典的前 个位置分配给全部 个可能出现的灰度值。一个 8bit 的灰度图像,若采用 9bit 构造字典,初始字典前 256 位置分配给灰度值 0~255
字典位置 0 1 ... 255 256 257 ... 511
字典条目 0 1 ... 255 / / / /
  1. 字典扩充:编码器顺序扫描像素,确定字典中还没有出现的灰度值序列,给定新的字典内容
  2. 编码输出:每当有新的字典扩充,便输出当前识别序列在字典中的位置序号,作为编码器输出

特点

  • 码字长度固定
  • 无需信源符号的出现概率
  • 采用字典编码方式,编码中逐渐构成字典
  • 字典定义了符号出现的顺序

例题

例如要对序列 0,0,255,255,0,0,255,255,0,0,255,255,0,0,255,255 进行 LZW 编码。

编码过程可以表示为

第一次编码,输入 0,不进行考虑

序号 当前识别序列 下一个数字 编码输出 字典位置 字典条目 解释
1 - 0 - 开始编码
2 0 0 0 256 0-0 识别到了新的样式,写入字典的 256
3 0 255 0 257 0-255
4 255 255 255 258 255-255
5 255 0 255 259 255-0
6 0 0 - - 发现了出现过的序列 0-0,直接在下一行用 256 表示
7 0-0 255 256 260 0-0-255
8 255 255 -
9 255-255 0 258 261 255-255-0
10 0 0 -
11 0-0 255 -
12 0-0-255 255 260 262 0-0-255-255
13 255 0 -
14 255-0 0 259 263 255-0-0
15 0 255 -
16 0-255 255 257 264 0-255-255
17 255 - 255

编码输出结果为 0, 0, 255, 255, 256, 258, 260, 259, 257, 255,压缩比为

可见,虽然每个字符所需要的码长增加了一位,但是码字个数减少了,因此最后算下来还是实现了信息压缩。