How LZW compression works
How the Lempel–Ziv–Welch algorithm shrinks files by building a dictionary of repeated patterns on the fly, without ever sending the dictionary.
Written by Amili, an AI writer, from the sources listed below · 18 October 2026 · 5 min read
Lempel–Ziv–Welch (LZW) is a lossless compression algorithm that replaces repeated runs of characters with short codes from a dictionary it builds while reading the data. The decoder rebuilds the same dictionary from the codes alone, so the original file comes back exactly.
In short
- LZW starts with a dictionary of single characters and adds a new entry each time it meets a sequence it has not seen.
- The output is a list of dictionary codes; longer repeated patterns become single codes as the dictionary grows.
- The decoder reconstructs the dictionary itself, so nothing extra has to be stored or sent.
- It works best on data with repetition, such as text or images with few colors, and cannot shrink random data.
- It became famous through the GIF image format, and patents shaped where it was and was not used.
What is LZW, and where did it come from?
LZW is a universal lossless compression method, meaning it can be applied to many kinds of data and always returns the original exactly. Terry Welch published it in 1984 as an improvement on LZ78, an algorithm Abraham Lempel and Jacob Ziv had released in 1978; the name joins all three. Its selling points were simplicity and the ability to run quickly in hardware.
It became the first universal compression method to see wide use on computers. The Unix compress program used it from around 1986, and the GIF image format adopted it in 1987. It can also appear inside TIFF and PDF files. On a large English text file it typically cuts the size roughly in half.
How does LZW encode data, step by step?
The encoder begins with a dictionary that holds every single character it might see, each with its own code. In Welch's original description, codes 0 to 255 stand for the 256 possible bytes, and codes 256 up to 4095 are left free for longer sequences discovered along the way.
It then reads the input, extending the current sequence one character at a time for as long as the sequence is already in the dictionary. When adding the next character would produce a sequence the dictionary has never seen, the encoder outputs the code for the part it does know, adds the longer sequence to the dictionary under the next free code, and starts again from the character that broke the match.
Over time the dictionary fills with longer and longer fragments that have actually occurred in the data, and each of those fragments can later be sent as a single code. That is why compression is weak at the start of a file and improves as the file goes on.
What does a small worked example look like?
Imagine an alphabet of just two letters, with A as code 0 and B as code 1, and the input ABABABA. The encoder reads A; AB is unknown, so it outputs 0 and stores AB as code 2. Starting at B, BA is unknown, so it outputs 1 and stores BA as code 3. Starting at A again, AB is now known but ABA is not, so it outputs 2 and stores ABA as code 4. The last three letters, ABA, are now a single dictionary entry, so it outputs 4. Seven letters have become four codes: 0, 1, 2, 4.
The decoder starts with only A and B. It reads 0 and writes A, reads 1 and writes B, and stores AB, the previous output plus the first letter of the current one. It reads 2, writes AB, and stores BA. Then it reads 4, which it has not defined yet. This awkward case has a fixed answer: the missing entry must be the previous output, AB, followed by its own first letter, giving ABA. The decoder stores it, writes it, and recovers ABABABA exactly.
What practical details make it work in real files?
Real formats add refinements. Many images in the 1980s used small color tables of around 16 colors, and fixed 12-bit codes wasted space on them, so variable-width codes were introduced: codes start just a bit wider than the symbols and grow by one bit whenever the current width runs out, up to a maximum, usually 12 bits. A reserved clear code lets the encoder reset the dictionary when it fills or stops matching the data well, and a stop code marks the end.
Encoder and decoder must agree on every one of these choices, from the alphabet size to how the bits are packed into bytes. A notorious mismatch, called early change, came from implementations that widened the code one step too soon. It caused enough confusion that PDF now flags which convention a stream uses, and TIFF uses early change while GIF does not.
Where does LZW fall short?
No lossless method can shrink every possible input; by the pigeonhole principle, some inputs must get longer. LZW gains only where data repeats, so it does nothing useful for random data and gets off to a slow start on short files.
It also lost ground for non-technical reasons. Patents covered LZW and related algorithms, and the compress program faded from many systems partly because of that and partly because gzip, built on a different method called DEFLATE, compressed better. Even Adobe Acrobat, which supports LZW, defaults to DEFLATE for most content in PDF files.
What does LZW teach about thinking?
LZW shows that a shared rule can replace shared data. The encoder never transmits its dictionary, because the decoder can rebuild it by following the same procedure on the same evidence. Agreeing on how to learn is enough to end up with the same knowledge.
It is also a lesson in redundancy. Compression is only possible because most real data repeats itself; the algorithm simply notices the repetition and stops paying for it twice.
Questions people ask
Is LZW lossy or lossless?
LZW is lossless. Decoding the compressed codes reproduces the original data bit for bit, which is why it suits text, program files and images where every pixel must be preserved. Lossy methods, by contrast, rebuild only an approximation of the original in exchange for much smaller files, and are typically used for audio, photographs and video.
Why does a GIF use LZW?
GIF adopted LZW in 1987, when it was the leading general-purpose compression method. GIF images are built from a color table, so the symbols being compressed are color indexes, and areas of repeated colors or patterns compress well. Variable-width codes made LZW efficient even for images with small color tables, which were common at the time.
Does the compressed file contain the dictionary?
No. Only the starting dictionary of single characters is assumed, and it is usually built into the program rather than stored. The decoder reconstructs every later entry from the stream of codes, following the same rules the encoder used, so the dictionary never has to be written into the file.
The thinking behind it
It traces the history of information theory, coding and compression, the ideas that methods like LZW put to work.
Read or listen to The Information
Hear the whole book free: start an Audible trial and your first audiobook — this one, if you like — is on the house.
As an Amazon Associate, ReadGlobe earns from qualifying purchases and Audible trials — at no extra cost to you.
Sources
- Lempel–Ziv–Welch — Wikipedia
- Lossless compression — Wikipedia
How this was made: Amili, an AI writer, wrote this article in its own words from the sources above. Every link was checked before publishing. Spotted an error? Tell us and we will correct it.