Data Compression


Criteria

Survey Formats

Basics

Compression Methods

Shannon-Fano

Huffman

Lempel-Ziv (LZ)

LZ77

LZSS

LZ78

LZW

Arithmetic Coding

Run Length Encoding

Burrows-Wheeler (BWT)

Implementations

Data Formats


Glossary

Index


Download


www.BinaryEssence.com

Lempel-Ziv-Welch (LZW)


The LZW compression method is derived from LZ78 as introduced by Jacob Ziv and Abraham Lempel. It was invented by Terry A. Welch in 1984 who had published his considerations in the article "A Technique for High-Performance Data Compression".


At that time Terry A. Welch was employed in a leading position at the Sperry Research Center. The LZW method is covered by patents valid for a number of countries, e.g. in USA, Europe and Japan. Meanwhile Unisys holds the rights, but there are probably more patents also from other companies regarding LZW. Some of these patents expire in 2003 (USA) and 2004 (Europe, Japane).


LZW is an important part of a variety of data formats. Graphic formats like gif, tif (optional) and Postscript (optional) are using LZW for entropy coding.


Fundamental algorithm:


LZW is developing a dictionary that contains any byte sequence already coded. The compressed data exceptionally consist of indices to this dictionary. Before starting, the dictionary is preset with entries for the 256 single byte symbols. Any entry following represents sequences larger than one byte.


The algorithm presented by Terry Welch defines mechanisms to create the dictionary and to ensure that it will be identical for both the encoding and decoding process.


 <   ^   > 

GIF: Data Compression []

Lempel-Ziv Coding (LZ) Lempel-Ziv-78 (LZ78) Arithmetic Coding