LZW

LZW
Name	LZW
Type	Lossless data compression
Inventor	Abraham Lempel; Jacob Ziv; Terry Welch
First published	1978; 1984
Related	LZ77; LZ78; GIF; TIFF; PNG
Usage	File compression; image formats; archive utilities

LZW

LZW is a lossless data compression algorithm developed as an adaptation of earlier work by Abraham Lempel, Jacob Ziv, and implemented in a practical form by Terry A. Welch. It produces a compact representation of input streams by building a dictionary of substrings and emitting dictionary indices instead of repeated symbol sequences. LZW gained widespread deployment through formats and tools associated with CompuServe, Unisys, Adobe Systems, UNIVAC, and many software libraries used on platforms such as IBM PC, Sun Microsystems workstations, and Apple Macintosh computers.

History

The conceptual roots trace to the theoretical papers by Abraham Lempel and Jacob Ziv in 1977 and 1978, which introduced dictionary-based schemes that inspired subsequent practical implementations. In 1984, Terry A. Welch published a concise variant that reduced computational overhead and made dictionary maintenance efficient for real-time use. Early adopters included the Graphics Interchange Format deployed by CompuServe and imaging support in file formats used by Aldus Corporation and Adobe Systems products. The algorithm’s acceptance expanded through inclusion in utility suites on UNIX systems and in compression tools used by Microsoft, Novell, and archival products for Digital Equipment Corporation servers. Patent activity by Unisys in the late 1980s and 1990s influenced adoption choices in standards such as those maintained by ISO and organizations like World Wide Web Consortium working groups concerned with image formats.

Algorithm

LZW operates by initializing a dictionary with all possible symbols from the input alphabet (for example, byte values 0–255). During encoding, it reads the longest string W present in the dictionary that matches the forthcoming input, outputs the dictionary index for W, then adds the concatenation of W and the next symbol K to the dictionary. Decoding mirrors this process: indices are read and mapped back to strings, with a special-case handling when an index refers to a not-yet-defined dictionary entry. The core loop relies on efficient string matching and dictionary lookup structures; theoretical connections appear with constructs from Shannon’s information theory and earlier methods by Claude Shannon and Noam Chomsky in modeling symbol probabilities and sequences. Bit-width growth strategies (fixed-width, variable-width) and clear/reset mechanisms govern dictionary size and affect compression ratio and statefulness across streams, concepts discussed in implementation notes by practitioners at Bell Labs and academic groups at MIT and Stanford University.

Implementation Details

Practical implementations commonly use hash tables, tries, or direct-address arrays to map strings to indices; decoder tables map indices to output strings or pairs (prefix index, appended symbol). Typical choices include starting code sizes of 9 bits and expanding up to 12 bits, with a clear code mechanism that resets the dictionary when it becomes full. Memory/time trade-offs are influenced by platform constraints observed on systems such as Intel 8086-based machines and Motorola 68000 series workstations. Endianness, streaming interfaces in POSIX environments, and integration with container formats like TIFF or GIF necessitate careful bit-packing and I/O buffering. Implementers in projects like gzip-adjacent libraries and image toolkits for GIMP and ImageMagick often include optimized routines employing CPU-specific instructions found in Intel and ARM processors to accelerate hashing and table updates.

Variants and Extensions

Multiple variants extend the basic scheme: adaptive reset policies, maximum-table-size tuning, and early-ascii or early-binary seeding for particular alphabets used in protocols by RFC authors. Modified LZW forms inspired by LZ77 hybrids appear in compression utilities developed by companies such as PKWARE and academic prototypes from UC Berkeley. Other extensions introduce arithmetic coding wrappers or entropy-coding stages influenced by work at Bell Labs and research labs at IBM Research to improve compression for skewed symbol distributions. Specialized variants accommodate streaming multimedia in standards from MPEG committees, and improvements for dictionary persistence and slide-window mechanisms reflect research from groups at University of California, San Diego and Carnegie Mellon University.

Applications

LZW and its derivatives have been embedded in image formats including Graphics Interchange Format and early variants of Tagged Image File Format employed by scanners and desktop publishing workflows involving Aldus Corporation and Adobe Systems. It appears in legacy compression utilities on MS-DOS and Windows platforms and in archival tools used in UNIX environments. Industrial use cases spanned fax codecs, printer drivers for vendors like Hewlett-Packard, and firmware compression on embedded controllers produced by Motorola and Intel divisions. Research groups at institutions such as ETH Zurich and Imperial College London have used LZW as a baseline when comparing dictionary methods to statistical coders like those based on Huffman and arithmetic coding.

Legal and Patent Issues

Patent enforcement by Unisys in the late 1980s and early 1990s created licensing concerns for implementers and standards bodies, prompting reassessments in organizations such as ISO and discussions among companies like CompuServe, Adobe Systems, and Apple Inc.. Licensing obligations affected adoption in open-source projects maintained by contributors associated with Free Software Foundation and communities around GNU Project utilities. Patent expirations and jurisdictional differences eventually reduced direct barriers, but historical disputes shaped the evolution of image format recommendations in consortia like the World Wide Web Consortium and commercial decisions by firms such as Microsoft and Novell.

Category:Data compression algorithms