Dictionary Methods

These compression methods use the property of many data types to contain repeating code sequences. Good examples of such data are text files (code words represent characters) and raster images (code words represent pixels). All the dictionary methods can be subdivided into two main groups.

The methods of the first group try to find if the character sequence currently being compressed has already occurred earlier in the input data and then, instead of repeating it, output only a po inter to the earlier occurrence. This is illustrated in the following diagram:

The dictionary here is implicit -- it is represented by the previously processed data. All the methods of this group are based on the algorithm developed and published in 1977 by Abraham Lempel and Jakob Ziv -- LZ77. A refineme nt of this algorithm which is the basis for practically all the later methods in this group is the LZSS algorithm developed in 1982 by Storer and Szymanski.

The algorithms of the second group create a dictionary of the phrases that occurr in the input data. When they encounter a phrase already present in the dictionary, they just output the index number of the phrase in t he dictionary. This is explained in the diagram below:

These methods are based on the algorithm developed and published by Lempel and Ziv in 1978 -- LZ78. The refinement which is the basis for the later methods is called LZW. It was developed by Terry Welch i n 1984 for hardware implementation in high-performance disk controllers.