Logo der Uni Stuttgart
Introduction

The Lempel-Ziv (LZ) data compression techniques are lossless dictionary based techniques that utilizes adaptive dictionaries to compress information. Those techniques exploit the the redundancy in the information and the correlation between the data for more effecient encoding and data compression, unlike other static compression techniques (like Huffmann coding) which are only optimal if the probabilities of the symbols in the data are independent [1][2].

The first Lempel-Ziv algorithm was introduced in 1977 by Jacob Ziv and Abraham Lempel [3] known as the LZ77 algorithm, which uses a sliding window for encoding and decoding (Not to be demonstrated in this web-demo). Later in 1978 another "faster" compression technique was introduced by the same authors in [4] known as the LZ78 algorithm, which showed that there exists finite lossless encoders that achieve "the bound" on the data compression ratio (defined in Slide 3). One of the most famous implementations of the LZ78 in applications is the deflate algorithm designed by Phil Katz [7] which is the default compression technique in the Adobe Acrobat software.

A famous variant of the LZ78 was introduced in 1984 by Teryy Welch [5] - as an improved algorithm for the LZ77 - known as the LZW (Lempel-Ziv-Welch) algorithm. The algorithm varies primary from the LZ78 in intializing a dicitonary which contains inputs of length one before encoding (unlike the LZ78 in which the dicitonary in constructed based on the input as shown in slide 3). This is done in order to get rid of the second element $s$ in the encoded pair $\left(i,s\right)$ . The LZW algorithm offered (as was shown in [5]):

• Simple algorithm implementation

• Very high throughput in hardware implementations

It should be noted that the LZW algorithm best works with data containing redundant patterns.

The use of the LZW was later patented in 1987 [6] and utilized in the famous GIF image as the compression technique the GIF images are based upon.

The LZ78 is to be demonstrated in this web-demo in details in Beginner Mode with simple text, as well as, for compressing ASCII-encoded text files as well as images in Expert mode.