How to Learn LZW Compression: Dictionaries, Variable-Width Codes, Decoding Edge Cases and Legacy Format Engineering

Wait, What?

A compressor and decompressor can build the same dictionary while transmitting only codes—not the dictionary itself.

LZW, short for Lempel–Ziv–Welch, is a classic lossless compression algorithm that replaces repeated symbol sequences with dictionary codes. Its elegance comes from synchronised dictionary growth: encoder and decoder begin with the same base vocabulary and deterministically add new phrases in the same order.

For learners, LZW is a rich lesson in streaming state, dictionaries, prefix growth, variable-width integers, edge cases and the difference between an abstract algorithm and a file-format specification. It is historically important, still encountered in formats such as GIF and some TIFF workflows, and unusually good for teaching how a seemingly simple algorithm becomes a precise binary protocol.

Quick Answer

Learn LZW in this order: repetition → dictionary codes → longest-known phrase → encoder update rule → decoder reconstruction → the KwKwK edge case → dictionary growth → variable-width codes → reset policies → GIF-specific rules → bit packing → format compatibility and testing. Do not confuse “the LZW idea” with “the exact rules used by GIF, TIFF or another container.”

1. The Problem: Repeated Phrases Waste Space

Suppose an input contains repeated sequences such as:

ABABABA...

A dictionary compressor can assign codes to longer and longer sequences such as A, B, AB, BA, ABA and so on. Instead of writing the symbols repeatedly, it emits compact references to phrases already learned.

LZW is lossless: decoding the code stream must reproduce the original symbol sequence exactly.

2. Start With a Base Alphabet

The encoder and decoder begin with the same dictionary containing every possible single input symbol. For byte-oriented data, a conceptual starting dictionary might map each byte value to one code.

The exact starting code space is format-specific. Generic LZW and GIF-LZW are related but not identical protocols, so keep the abstract algorithm separate from container rules.

3. The Encoder Tracks the Longest Phrase It Already Knows

Let w be the current known phrase and k the next input symbol. Consider the concatenation wk.

If wk is already in the dictionary, extend w to wk.
If wk is not in the dictionary, output the code for w, add wk to the dictionary, and restart w as k.

At end of input, output the code for the final w.

4. Generic Encoder Pseudocode

dictionary = all single symbols
w = empty

for each symbol k in input:
    if w + k exists in dictionary:
        w = w + k
    else:
        output code(w)
        add (w + k) to dictionary
        w = k

if w is not empty:
    output code(w)

The key learning question is not “what line comes next?” It is: when does the encoder learn a new phrase, and what phrase does it output before learning it?

5. Trace a Tiny Example

Use a toy alphabet {A,B} with initial codes A=0 and B=1. Compress a short string such as:

ABABABA

Build a trace table:

w | next symbol k | wk known? | output | new dictionary entry

The table makes two things visible: phrases become longer over time, and the encoder emits a code before adding the newly discovered longer phrase.

6. Why the Decoder Can Rebuild the Dictionary Without Receiving It

The decoder receives codes. Because it knows the same initial dictionary and follows a deterministic rule, it can reconstruct new entries in the same sequence.

A common decoding pattern is:

Read the first code and output its phrase.
For each next code, determine the phrase represented by that code.
Output that phrase.
Add previous_phrase + first_symbol(current_phrase) to the dictionary.
Set previous_phrase = current_phrase.

7. Generic Decoder Pseudocode

dictionary = all single symbols
old = read first code
w = dictionary[old]
output w

for each next code c:
    if c exists in dictionary:
        entry = dictionary[c]
    else if c is exactly the next dictionary code:
        entry = w + first_symbol(w)
    else:
        fail: invalid stream

    output entry
    add w + first_symbol(entry) to dictionary
    w = entry

That special second branch is the famous LZW decoding edge case.

8. The “KwKwK” Edge Case

Sometimes the encoder emits a code for an entry it has just created before the decoder has had a chance to create the same entry. The incoming code is therefore equal to the decoder’s next available dictionary code, even though it is not yet present in the table.

In that specific case, the missing phrase is:

previous_phrase + first_symbol(previous_phrase)

This often appears in explanations using a pattern such as KwKwK. It is not permission to accept arbitrary unknown codes. Only the precisely predicted next-code case is valid.

9. Why Encoder and Decoder Stay in Lockstep

The encoder adds a phrase w+k when it discovers that phrase is not yet known. The decoder, after seeing the next output phrase, can infer exactly the same new phrase as:

previous_phrase + first_symbol(current_phrase)

That shared recurrence is the synchronisation invariant. If either side changes dictionary-reset timing, code-width timing or special-code rules, the streams diverge.

10. Code Width Cannot Stay Fixed Forever

As the dictionary grows, more code values are needed. A format may therefore begin with small codes and increase the number of bits per code when the current width can no longer represent the next dictionary entry.

This creates a second layer of state:

dictionary contents;
next available code;
current code width;
maximum code width;
reset or clear state.

Many real-world LZW bugs live in this layer rather than in the phrase-matching logic.

11. Bit Packing Is a Separate Engineering Problem

If codes are 9, 10, 11 or 12 bits wide, they do not line up neatly with 8-bit bytes. The encoder must pack code bits into bytes according to the file format’s defined bit order, and the decoder must reverse the process exactly.

A correct dictionary algorithm can still produce an invalid file if code bits are packed in the wrong order or width changes happen one code too early or too late.

12. Dictionary Growth Needs a Policy

An unbounded dictionary is impossible in a finite format. Systems therefore choose policies such as:

stop adding entries when the table is full;
reset the dictionary;
emit a special clear code;
monitor compression effectiveness and reset adaptively.

Those policies are not interchangeable. The decoder must follow the same protocol.

13. GIF Uses a Specific LZW Variant

GIF image data uses LZW on palette indices and defines format-specific control rules. The GIF89a specification defines:

a Clear code equal to 2^{initial code size};
an End of Information code equal to Clear+1;
the first available dictionary code as Clear+2;
variable code lengths beginning at initial code size+1;
a maximum code width of 12 bits.

GIF therefore teaches an important distinction: understanding generic LZW is necessary but not sufficient to implement a compliant GIF encoder or decoder.

14. GIF Compression Is Lossless, but GIF Conversion May Not Be

LZW itself is lossless. However, GIF represents each image frame using a palette with at most 256 colour entries. Converting a full-colour photograph to a GIF may require colour quantisation or dithering before LZW is applied.

So a GIF workflow may lose colour information because of palette reduction even though the LZW compression stage preserves the palette-index stream exactly.

15. LZW Is Historically Important, Not a Universal Modern Default

LZW became widely used in Unix compress, GIF, TIFF and other systems. Later formats and compressors often favour methods with better compression ratios or different performance characteristics, such as DEFLATE and newer entropy/compression schemes.

The right professional lesson is not “LZW is obsolete.” It is: legacy algorithms remain operationally important because file formats and archives live for decades.

16. Patent History Is Part of the Engineering History

LZW became unusually well known outside computer science because patents covering LZW-related implementations affected software distribution and GIF tooling in the 1990s and early 2000s. Those patents have expired, but the episode is a useful reminder that deployable technology sits inside legal and standards ecosystems as well as algorithmic ones.

17. Test the Decoder More Aggressively Than the Encoder

A decoder receives potentially malformed external input. Robust implementations should test:

invalid codes that are not the next-code edge case;
unexpected end of stream;
dictionary overflow;
illegal code-width transitions;
clear/reset codes in awkward positions;
truncated byte blocks;
resource exhaustion attacks using hostile streams.

Correctness includes rejecting bad data safely, not merely decoding valid samples.

18. Round-Trip Tests Are Necessary but Not Sufficient

If your encoder and decoder share the same bug, compress-then-decompress may still succeed. Add cross-implementation tests: decode files produced by trusted tools and have trusted tools decode your output.

For formats such as GIF, verify conformance at the container level as well as the phrase-dictionary level.

19. Common Failure States

Adding the wrong phrase to the dictionary.
Outputting after adding when the algorithm requires output before adding.
Rejecting the valid next-code decoder edge case.
Accepting arbitrary missing codes as if they were the edge case.
Changing code width at the wrong boundary.
Letting encoder and decoder reset dictionaries at different times.
Confusing generic LZW with GIF-LZW.
Calling GIF colour reduction “LZW loss.”
Testing only round trips with the same implementation.

20. Practice Ladder: Beginner to Professional

Beginner: build a tiny phrase dictionary for an A/B string and replace repeated phrases with codes.
Foundation: trace the generic encoder with columns for w, k, output and new entry.
Intermediate: write the decoder and explain why it can recreate the dictionary without receiving it.
Advanced: construct and solve the next-code/KwKwK edge case by hand.
Professional: implement variable-width code packing, dictionary reset semantics, malformed-stream checks and cross-tool compatibility tests.
Transfer: compare dictionary coding with entropy coding and explain what kind of redundancy each targets.

21. A Better Way to Study LZW

Use two learners—or two columns on paper—as encoder and decoder. Let neither side see the other side’s dictionary. Pass only the emitted codes and verify that both dictionaries grow identically. This makes the synchronisation invariant visible. Then introduce one controlled complication at a time: next-code edge case, code-width growth, clear code, bit packing. Worked examples and active code tracing are especially useful here because the algorithm’s difficulty lies in state transitions rather than syntax.

Learning Hall Boundary

This article owns LZW as an adaptive dictionary compression algorithm and its transition from abstract phrase coding to format-level implementation concerns. It does not replace broader compression theory, entropy-coding material, the existing Asymmetric Numeral Systems article, image-format instruction, MindOS learning-process jobs, Bolt measurement work or Student/Studying Interface workflow content.

Evidence Boundary

Terry A. Welch described the practical LZW method in “A Technique for High-Performance Data Compression,” Computer 17(6), 1984, pp. 8–19, DOI 10.1109/MC.1984.1659158. The Library of Congress format description characterises LZW as lossless dictionary-based encoding used in GIF and TIFF: Library of Congress — LZW. The GIF89a specification documents Clear codes, End of Information, variable code widths and the 12-bit maximum: GIF89a specification copy. The teaching sequence also draws on programming-education research on code tracing, worked examples and algorithm visualisation.

Professional rule: you understand LZW when you can explain how encoder and decoder build the same dictionary without transmitting it, handle the next-code edge case correctly, and distinguish the abstract algorithm from the exact binary protocol of the file format you are implementing.

Small Group Tutorials