「LZW 编码」是一种无损压缩编码,通过消除图像中的像素间冗余来实现压缩。采用三个发明人姓氏首字母缩写命名。
LZW 编码是 Unix 操作系统的文件压缩标准方法,还应用于 GIF、TIFF 和 PDF 压缩文件中
字典位置 | 0 | 1 | ... | 255 | 256 | 257 | ... | 511 |
---|---|---|---|---|---|---|---|---|
字典条目 | 0 | 1 | ... | 255 | / | / | / | / |
例如要对序列 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
,压缩比为
可见,虽然每个字符所需要的码长增加了一位,但是码字个数减少了,因此最后算下来还是实现了信息压缩。