Lempel–Ziv–Welch
Universal lossless compression algorithm published by Welch in 1984.
Lempel–Ziv–Welch (LZW) is a universal lossless compression algorithm developed by Abraham Lempel, Jacob Ziv, and Terry Welch. Welch introduced it in 1984 as an enhancement to the LZ78 algorithm, which Lempel and Ziv had published in 1978. Its claimed advantages include simplicity of implementation and the ability to achieve high throughput when built into hardware. For a large English text file, LZW typically reduces the file size by about half.
LZW was the first universal data compression method to see widespread use on computers. It appeared around 1986 in the compress program commonly included with Unix systems, but later disappeared from many distributions due to patent infringement and because gzip, using the LZ77-based DEFLATE algorithm, offered better compression ratios. The algorithm gained broad adoption when it became part of the GIF image format in 1987, and it may optionally be used in TIFF and PDF files. Although Adobe Acrobat software supports LZW, it defaults to DEFLATE for most text and color-table-based image data in PDFs.
In Welch’s original description, the algorithm encodes sequences of 8-bit data into fixed-length 12-bit codes. Codes 0 through 255 represent single-character sequences for each 8-bit character, while codes 256 through 4095 are assigned dynamically to longer sequences encountered during encoding. At each step, input bytes are collected into a sequence until adding the next character would create a string not yet in the dictionary. The code for the current sequence (without that character) is output, and a new code for the sequence including that character is added to the dictionary.
For image compression using a color table, the natural alphabet is the set of color table indexes. In the 1980s, many images had small color tables (often around 16 colors). With such a reduced alphabet, fixed 12-bit codes produced poor compression unless the image was large, so variable-width codes were introduced. Codes typically start one bit wider than the symbols being encoded, and the width increases by one bit each time the current code size is exhausted, up to a prescribed maximum (usually 12 bits). Once the maximum code value is reached, encoding continues using the existing table without adding new entries.
Further refinements include reserving a clear code (typically the first value after the individual alphabet characters) to res
- field
- Data compression
- known_for
- LZW compression algorithm
- nationality
- Not specified in source
Lore & Background
The algorithm encodes sequences of 8-bit data as fixed-length 12-bit codes, with codes 0–255 representing single characters and codes 256–4095 created in a dictionary for encountered sequences. During compression, input bytes are gathered into a sequence until the next character would make a sequence not yet in the dictionary; the code for the sequence without that character is output, and a new code is added. For images with small color tables, variable-width codes were introduced, starting one bit wider than the symbols and increasing by 1 bit up to a maximum, typically 12 bits. Further refinements include a clear code to reinitialize the table and a stop code to indicate end of data.
Reader's Guide
LZW became the first widely used universal data compression method on computers, used in the compress program in Unix systems starting around 1986. It found wide use when it became part of the GIF image format in 1987, and may optionally be used in TIFF and PDF files. The algorithm's advantages include simplicity and potential for high throughput in hardware. However, it has disappeared from many Unix distributions because it infringed the LZW patent and because gzip produced better compression ratios using the LZ77-based DEFLATE algorithm. Although LZW is available in Adobe Acrobat software, Acrobat by default uses DEFLATE for most text and color-table-based image data. The algorithm works best on data with repeated patterns, with compression ratio improving asymptotically. Decoding rebuilds the dictionary from the encoded data, and encoder and decoder must agree on details such as alphabet size, code width, and use of clear and stop codes. Variable-width codes require careful synchronization, and early implementations sometimes caused confusion with 'early change' in code width, leading Adobe to include an explicit flag in PDF files.
Did You Know?
- A large English text file can typically be compressed via LZW to about half its original size.
- The algorithm was used in the compress program commonly included in Unix systems starting around 1986.
- LZW became part of the GIF image format in 1987.
- Some early implementations of the encoding algorithm increased the code width one code too early, a practice called 'early change'.
More in Discovery and invention controversies 1-24
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record