Contents

1 History

• Jacov Ziv and Abraham Lempel proposed the LZ77 algorithm in 1977 [2].
• In the eighties, LZSS (a branch of LZ77) was implemented by Haruyasu Yoshizaki [1] (and implemented in the LHA compressor, discovering the possibilities of the LZ77 encoder.
• After that, a large number of text compressors have been based on LZ77 (or a variation of it). Some of the most famous are: ARJ, [RAR](https://en.wikipedia.org/wiki/RAR_(file_format), gzip and 7z.
• LZ77 processes a sequence of symbols using the structure:

• The dictionary and the look-ahead buffer have a fixed size and can be considered as a sliding window moving over the symbols while they are coded. In each iteration, the input of new symbols to the buffer generates the output of the oldest ones, which become the newest symbols of the dictionary.

2 Encoder

1. Let $I$ the length of the dictionary and $J$ the length of the buffer.
2. Input the first $J$ symbols in the buffer.
3. While the input is not exhausted:
   1. Let $i$ the position of the first $j$ symbols of the buffer in the dictionary, and $k$ the symbol that makes that $j$ can not be larger.
   2. Output $ijk$.
   3. Input the next $j+1$ symbols in the buffer.

Example

3 Decoder

1. While code-words $ijk$ are input:
   1. Output the $j$ symbols extracted from the position $i$ in the dictionary.
   2. Output $k$.
   3. Put all the decoded symbols in the beginnig of the buffer.

Example

• Parameters $I$ and $J$ control the performance of the algorithm. They should be large enough to guarantee the matching of long strings, but should be small in order to reduce the number of bits of the code-words $ijk$. Typical sizes are: ${log}_2\left(I\right)=12.0$ and ${log}_2\left(J\right)=4.0$.

4 Lab: LZSS

IPython notebook

References