LZW

LZW (Lempel-Ziv-Welch) is a universal lossless data compression algorithm created by Abraham Lempel, Jacob Ziv, and Terry Welch. It was published by Welch in 1984 as an improved implementation of the LZ78 algorithm published by Lempel and Ziv in 1978. The algorithm is designed to be fast to implement, but not necessarily optimal since it does not perform any analysis on the data.

Description of the algorithm

The compressor algorithm builds a string translation table from the text being compressed. The string translation table maps fixed-length codes (usually 12-bit) to strings. The string table is initialized with all single-character strings (256 entries in the case of 8-bit characters). As the compressor character-serially examines the text, it stores every unique two-character string into the table as a code/character concatenation, with the code mapping to the corresponding first character. As each two-character string is stored, the first character is outputted. Whenever a previously-encountered string is read from the input, the longest such previously-encountered string is determined, and then the code for this string concatenated with the extension character (the next character in the input) is stored in the table. The code for this longest previously-encountered string is outputted and the extension character is used as the beginning of the next string.

The decompressor algorithm only requires the compressed text as an input, since it can build an identical string table from the compressed text as it is recreating the original text. However, an abnormal case shows up whenever the sequence character/string/character/string/character (with the same character for each character and string for each string) is encountered in the input and character/string is already stored in the string table. When the decompressor reads the code for character/string/character in the input, it cannot resolve it because it has not yet stored this code in its table. This special case can be dealt with because the decompressor knows that the extension character is the previously-encountered character.Welch, T. A. (June 1984). "A technique for high-performance data compression." Computer. Vol. 17, pp. 8-19.

Uses

The method became widely used in the program compress, which became a more or less standard utility in Unix systems circa 1986. (It has since disappeared from many for both legal and technical reasons.) Several other popular compression utilities also used the method, or closely related ones.

It became very widely used after it became part of the GIF image format in 1987. It may also (optionally) be used in TIFF files.

LZW compression provided a better compression ratio, in most applications, than any well-known method available up to that time. It became the first widely used universal data compression method on computers. It would typically compress large English texts to about half of their original sizes.

Today, an implementation of the algorithm is contained within the popular Adobe Acrobat software program.

Patent issues

Various patents have been issued in the USA and other countries for LZW and similar algorithms. LZ78 was covered by by Lempel, Ziv, Cohn, and Eastman, assigned to Sperry Corporation, later Unisys Corporation, filed on August 10, 1981. Two US patents were issued for the LZW algorithm: by Victor S. Miller and Mark N. Wegman and assigned to IBM, originally filed on June 1, 1983, and by Welch, assigned to Sperry Corporation, later Unisys Corporation, filed on June 20, 1983. On June 20, 2003, this patent on the LZW algorithm expired ^*.

US Patent 4,558,302 is the one that has caused the most controversy (See GIF#Unisys and LZW patent enforcement).

Lempel-Ziv-Welch vs. Ziv-Lempel-Welch

Although the LZW acronym refers to the inventors as Lempel, Ziv and Welch, some people claim the intellectual property rights go to Ziv first, so the method must be called the Ziv-Lempel-Welch algorithm, and not the Lempel-Ziv-Welch algorithm. Others who like distinguishing between the algorithm and the code prefer calling the algorithm LZ and the code written by Welch as LZW.

References

External links

"A technique for high-performance data compression" - The original paper by Welch
United States Patent 4,558,302 URL Retrieved on Saturday, June 03, 2006
"LZW Data Compression", by Mark Nelson (DDJ Article with source code)
Sad day... GIF patent dead at 20 (Short and possibly an oversimplification of the true story, a more detailed history can be found on the GIF page)
Bringing back LZW compression by Nathan Willis
List of LZW libraries, papers and other resources

Lossless compression algorithms | Lempel-Ziv-Welch-Algorithmus | Lempel-Ziv-Welch | אלגוריתם למפל זיו | LZW | Lempel Ziv Welch | LZW | LZW | LZW | LZW | LZW | LZW | LZW