Contents

1 Fundamentals

• In 1978, Ziv and Lempel published the LZ78 algorithm [1].
• LZ89 represents the dictionary in a recursive way with the idea of improving the search of the strings in the dictionary. Now, each entry in the dictionary is a pair $wk$, where $w$ is a pointer to the dictionary and $k$ is a symbol. In fact, each entry $wk$ represents the string that results from the concatenation of string $w$ and $k$, where $w$ can be recursively computed as we have found $wk$.
• We will denote string$\left(w\right)$ to the string that $w$ represents.
• The empty string is obtained by string$\left(0\right)$.

2 Encoder

1. $w\leftarrow 0$.
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 $wk$.
      2. Insert $wk$ in the dictionary.
      3. $w\leftarrow 0$.

Compression and dictionary examples:

3 Decoder

1. While the input is not exhausted:
   1. Input $wk$.
   2. Output $\text{string}\left(w\right)$.
   3. Output $k$.
   4. Insert $wk$ in the dictionary.

Decoding and dictionary examples:

References