Lempel-Ziv-Welch

Lempel-Ziv-Welch (LZW) is a lossless compression algorithm that builds a dictionary of input substrings during encoding and replaces repeated patterns with dictionary indices. Developed by Terry Welch in 1984 as an improvement to the LZ78 algorithm, LZW requires no prior knowledge of source statistics and adapts its dictionary to the specific data being compressed.

LZW achieved widespread adoption as the compression method for the GIF image format and the Unix compress utility. Its simplicity — the dictionary is initialized with all possible single-character strings and grows dynamically — made it computationally efficient for the hardware of the 1980s. However, its patented status until 2003 limited its use in open-source software, contributing to the dominance of the DEFLATE algorithm in later formats.

The algorithm's fixed-width code words impose a maximum dictionary size, after which the dictionary must be frozen or reset, creating a tradeoff between adaptation and compression efficiency.