LZW compression

Abraham Lempel and Jakob Ziv are the creators of the LZ77 compressor, invented in 1977 (hence its name). This compressor was then used for filing (ZIP, ARJ and LHA formats use it).

In 1978 they created the LZ78 compressor specialized in image compression (or that of any type of binary file).

In 1984, Terry Welch of Unisys modified it, in order to use it in hard drive controllers; his surname initial was thus added to the LZ abbreviation yielding LZW.
LZW is a very fast algorithm both for compression and for decompression, based on the occurrence multiplicity of character sequences in the string to be encoded. Its principle consists in substituting patterns with an index code, by progressively building a dictionary.

Moreover, it works on bits and not on bytes, thus, it does not depend on the way in which the processor codes information. It is one of the most popular algorithms and is particularly used in TIFF and GIF formats. Since the LZW compression method has been patented by Unisys, it is the copyright-free LZ77 algorithm which is used in PNG images.

Construction of the dictionary

The dictionary is initialized with the 256 values of the ASCII table. The file to be compressed is split into strings of bytes (thus for monochrome images - coded on 1 bit - this compression is not very effective), each of these strings is compared with the dictionary and is added if not found there.

Compression

The algorithm goes over the stream of information, coding it; if a string is never smaller than the longest word in the dictionary then it is transmitted.

Decompression

During decompression, the algorithm rebuilds the dictionary in the opposite direction; it thus does not need to be stored.

Last update on Thursday October 16, 2008 02:43:16 PM.This document entitled « LZW Compression » from Kioskea (en.kioskea.net) is made available under the Creative Commons license. You can copy, modify copies of this page, under the conditions stipulated by the licence, as this note appears clearly.