LempelZivWelch

Lempel-Ziv-Welch (LZW) is a lossless data compression algorithm developed by Terry A. Welch in 1984. It builds on the Lempel-Ziv family of algorithms, notably the LZ78 method introduced by Abraham Lempel and Jacob Ziv in 1978, and is distinguished by its use of a dynamic dictionary. In LZW, the encoder maintains a dictionary of strings, initially containing all single-character symbols. As the input stream is processed, the longest string that currently exists in the dictionary is found, its code is output, and a new dictionary entry is created by appending the next input character to that string. The decoder performs the inverse operation, using the codes to reconstruct the strings and to update its own dictionary in lockstep with the encoder.

LZW is a one-pass, dictionary-based compression technique that typically uses fixed-length codes (commonly 12 bits) and expands the dictionary up to a maximum size before reinitialization. It is fast and simple to implement, and it works well on a variety of data, especially plain text and certain bitmap-style images, but its compression efficiency can be limited on already compressed data.

LZW gained wide adoption in the GIF image format (and in several other file formats) during the late 1980s and 1990s. The format’s use of LZW was the subject of patent licensing. With patent expirations in the 2000s, LZW entered broader, royalty-free use. LZW remains a foundational example in the study of dictionary-based, lossless compression, and many variants exist that tweak dictionary management, reset behavior, or input handling.