Contents

1 Motivation

• The original LZ77 algorithm generates a raw (un-encoded) code $k$ in each code-word $ijk$. This is a loss of compression performance!
• In [1] J.A. Storer y T.G. Szymanski (SS) proposed to minimize this problem adding an extra prefix-bit to each LZ77 code-word. Therefore, the code-word $$0_{{log}_2\left(I\right)}{0}_{log\left(J\right)}{k}_8$$

  is replaced by

  $$0_1{k}_8$$

  and the code-word

  $$i_{{log}_2\left(I\right)}{j}_{log\left(J\right)}{k}_8$$

  is replaced by

  $$1_1{i}_{{log}_2\left(I\right)}{j}_{log\left(J\right)}{k}_8.$$

Let’s go to the lab!

1. Download http://www.ace.ual.es/~vruiz/doctorado/text-compression.tar.gz and make lzss.
2. Encode each image of The Test Image Corpus using the LZSS codec. Continue filling the table:
       Codec | lena boats pepers zelda Average  
   ----------+--------------------------------  
           : |    :     :      :     :       :  
        lzss | ....  ....   ....  ....    ....

3. Try to modify the source code of lzss.c to increase the compression ratios for these data.
4. Finally, verify that the LZSS codec is lossless!

References