LZW

LZW

Juan Francisco Rodríguez Herrera
Vicente González Ruiz

July 10, 2017

Contents

1 Fundamentals
2 Encoder
3 Decoder

1 Fundamentals

In 1984 Terry A. Welch proposes the LZW algorithm [3], which is an improved version of the LZ89 algorithm that does not writes raw symbols ( $k$ ) to the code-stream.
LZW was selected as encoding engine for the GIF (Graphics Interchange Format) [1] and for the compressor compress [2].
The dictionary is initially ﬁlled with the $2^{k}$ possible symbols (roots), that are stored in entries $0 \dots 255$ .

2 Encoder

$w \leftarrow$ next input symbol.
While the input is not exhausted:
1. $k \leftarrow$ next input symbol.
2. If wk is found in the dictionary, then:
  1. $w \leftarrow$ address of $w k$ in the dictionary.
3. Else:
  1. Output $\leftarrow w$ .
  2. Insert $w k$ in the dictionary.
  3. $w \leftarrow k$ .

Example

Input	$w$	$k$	Output	Comment

ab	97	b	97	$D [257] \leftarrow ab$
a	98	a	98	$D [258] \leftarrow ba$
b	97	b		$w = 257$
c	257	c	257	$D [259] \leftarrow abc$
b	99	b	99	$D [260] \leftarrow cb$
a	98	a		$w = 258$
b	258	b	258	$D [261] \leftarrow bab$
a	98	a		$w = 258$
b	258	b		$w = 261$
a	261	a	261	$D [262] \leftarrow baba$
a	97	a	97	$D [263] \leftarrow aa$
a	97	a		$w = 263$
a	263	a	263	$D [264] \leftarrow aaa$
a	97	a		$w = 263$

$w \leftarrow$ next input symbol.
While the input is not exhausted:
1. $k \leftarrow$ next input symbol.
2. If wk is found in the dictionary, then:
  1. $w \leftarrow$ address of $w k$ in the dictionary.
3. Else:
  1. Output $\leftarrow w$ .
  2. Insert $w k$ in the dictionary.
  3. $w \leftarrow k$ .

Address	String	$w$	$k$

0		0	NULL
$⋮$		$⋮$	$⋮$
97		0	a
98		0	b
99		0	c
$⋮$		$⋮$	$⋮$
256	reserved for the ESC code
257	ab	97	b
258	ba	98	a
259	abc	257	c
260	cb	99	b
261	bab	258	b
262	baba	261	a
263	aa	97	a
264	aaa	263	a

In a typical implementation, the 256-th entry in the dictionary (and it’s code-word, 256) is used as an escape code that precedes to one of the following command codes:
1. ONE_BIT_MORE: when the number of bits of $w$ becomes to small to represent all the entries in the dictionary, $w$ must be incremented by in both, the encoder and the decoder.
2. CLEAN_THE_DICTIONARY : if the compression-rate falls below of a expected value, the dictionary could be polluted. In this case, both, the encoder and the decoder should reset it.
3. END_OF_CODESTREAM: there are not more symbols to encode (and decode).

3 Decoder

$c o d e \leftarrow$ ﬁrst input code-word.
Output $c o d e$ .
$o l d_c o d e \leftarrow c o d e$ .
While the input is not exhausted:
1. $c o d e \leftarrow$ next input code-word.
2. $w \leftarrow o l d_c o d e$ .
3. If code is found in the dictionary, then:
  1. Output string $(c o d e)$ .
4. Else:
  1. Output string $(w)$ .
  2. Output $k$ .
5. $k \leftarrow$ ﬁrst symbol of the last output.
6. Insert $w k$ in the dictionary.
7. $o l d_c o d e \leftarrow c o d e$ .

Example

Input	$c o d e$	$w$	$k$	Output	Comment

97	97			a	Initialization
98	98	97	b	b	$c o d e < 257$ , $D [257] \leftarrow ab$
257	257	98	a	ab	$c o d e < 258$ , $D [258] \leftarrow ba$
99	99	257	c	c	$c o d e < 259$ , $D [259] \leftarrow abc$
258	258	99	b	ba	$c o d e < 260$ , $D [260] \leftarrow cb$
261	261	258	b	bab	$c o d e = 261$ , $D [261] \leftarrow bab$
97	97	261	a	a	$c o d e < 262$ , $D [262] \leftarrow baba$
263	263	97	a	aa	$c o d e = 263$ , $D [263] \leftarrow aa$

$c o d e \leftarrow$ ﬁrst input code-word.
Output $c o d e$ .
$o l d_c o d e \leftarrow c o d e$ .
While the input is not exhausted:
1. $c o d e \leftarrow$ next input code-word.
2. $w \leftarrow o l d_c o d e$ .
3. If code is found in the dictionary, then:
  1. Output string $(c o d e)$ .
4. Else:
  1. Output string $(w)$ .
  2. Output $k$ .
5. $k \leftarrow$ ﬁrst symbol of the last output.
6. Insert $w k$ in the dictionary.
7. $o l d_c o d e \leftarrow c o d e$ .

Let’s go to the lab!

Download http://www.ace.ual.es/~vruiz/doctorado/text-compression.tar.gz and make lzw15v.
Encode each image of The Test Image Corpus using the LZW codec. Continue ﬁlling the table:
    Codec | lena boats pepers zelda Average
----------+--------------------------------
        : |    :     :      :     :       :
   lzw15v | ....  ....   ....  ....    ....
Again, check the reversibility of the LZW codec!

References

[1] Compuserve Incorporated. Graphics Interchange Format (GIF) Speciﬁcation, June 1987.

[2] D. Hamaker. Compress and Compact Discussed Further. Commun. ACM, 31:1139–1140, 1988.

[3] T.A. Welch. A Technique for High-Performance Data Compression. IEEE Computer, pages 8–19, 1984.