Contents

1 History

• In 1977, Jacov Ziv y Abraham Lempel propose the LZ77 algorithm.
• In the eighties, a branch of LZ77 known as LZSS and is implemented by Haruyasu Yoshizaki in the program LHARC, discovering the possibilities of the LZ77 encoding.
• After that, a large number of text compressors have been based on the LZ77 idea (or a variation of it). Some of the most famous are: ARJ, RAR, gzip and 7z.

2 Fundamentals of LZ77

• 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, where the input of a new symbol generates the output of the oldest one, which becomes the newest symbol of the dictionary.

3 The LZ77 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 in the dictionary of the first $j$ symbols of the buffer and $k$ the symbol that makes that $j$ can not be larger.
   2. Output $ijk$.
   3. Input the next $j+1$ in the buffer.

4 The LZ77 decoder

1. While the code-words $ijk$ are not exhausted:
   1. Output the $j$ symbols extracted from the position $i$ in the dictionary.
   2. Output $k$.
   3. Introduce all the decoded symbols into the buffer.

Encoding example

5 Decoding example

• Notice that the parameters $I$ and $J$ control the performance of the algorithm. They should be large enough to guarantee the matching of long strings, but should keep 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$.