Contents

1 Basics

• In 1984, Terry A. Welch proposed the LZW algorithm [1], an improved version of the LZ78 algorithm that does not writes raw symbols ($k$ fields) to the code-stream.
• LZW was selected as the encoding engine for the GIF (Graphics Interchange Format), and for the compressor compress.
• Initially, the dictionary is filled with the $2^k$ possible symbols (roots), that are stored in the first entries (for 1-byte symbols: $0\cdots 255$).

2 Encoder

1. $w\leftarrow$ first input symbol.
2. 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 $wk$ in the dictionary.
   3. Else:
      1. Output $\leftarrow w$.
      2. Insert $wk$ in the dictionary.
      3. $w\leftarrow k$.

Example

3 Decoder

1. $c\leftarrow$ first input code-word.
2. Output $c$.
3. $c^{\prime }\leftarrow c$.
4. While the input is not exhausted:
   1. $c\leftarrow$ next input code-word.
   2. $w\leftarrow c^{\prime }$.
   3. If $c$ is found in the dictionary, then:
      1. Output string$\left(c\right)$.
   4. Else:
      1. Output string$\left(w\right)$.
      2. Output $k$.
   5. $k\leftarrow$ first symbol of the last output.
   6. Insert $wk$ in the dictionary.
   7. $c^{\prime }\leftarrow c$.

Example

4 Lab: LZW

IPython notebook

References