LZW compression

Cost and properties

time	O(n) with a trie
dictionary	built on the fly, never sent
exploits	repeated phrases anywhere
used by	GIF, TIFF, old Unix compress

Reference: Sedgewick & Wayne, §5.5; Ziv–Lempel 1978, Welch 1984.

LZW compression in Python

Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.

Open in Visualizer

def compress(text, R=256, W=9):
    # Emit the code for the LONGEST prefix of the remaining input that is
    # already in the dictionary, then add that prefix plus the next
    # character. The expander can rebuild this dictionary from the codes
    # alone, so it is never transmitted.
    codes = {chr(c): c for c in range(R)}
    nxt = R + 1                           # R is reserved for end-of-file
    out, i = [], 0
    while i < len(text):
        s = text[i]
        while i + len(s) < len(text) and (s + text[i + len(s)]) in codes:
            s += text[i + len(s)]         # extend the match
        out.append(codes[s])              # emit its code
        t = i + len(s)
        if t < len(text) and nxt < (1 << W):
            codes[s + text[t]] = nxt      # LEARN one new phrase
            nxt += 1
        i = t
    return out

Why it works

Adaptive, and self-describing

The dictionary is not transmitted. The expander starts from the same 256 single-character entries and adds an entry after each code it reads, in lockstep with the compressor — so both sides always agree. That is what makes LZW practical: all the learned structure is free.

Why the matches grow

Each step learns exactly one new phrase: the match just emitted, extended by the next character. So after seeing AB the dictionary knows ABA; next time round it can match ABA and learn ABAB. On repetitive input the phrases lengthen geometrically — watch ABABABAB… and see how few codes the tail needs. On input with no repetition it never gets to use anything it learned, and the output is one code per character.

The tricky case in the expander

The compressor can emit a code the expander has not yet defined — it happens when a phrase is immediately followed by itself (input like AAAAA). The expander handles it by noticing the code equals the next code it is about to create, and reconstructing the string as previous phrase + its own first character. Missing that special case is the classic LZW bug, and it only shows up on inputs like the ones above.

Implementation and history

Finding the longest match is a trie lookup, which makes the whole compression linear in the input. Real implementations must decide what to do when the codes run out (W bits): stop learning, or throw the dictionary away and start again. LZW was the compression in GIF and Unix compress, and Unisys's patent on it (expired 2003) is the direct reason PNG exists — a rare case of an algorithm's licence shaping the web.

What to try in the animation

The dictionary starts with the 256 single characters (codes 0–255) and grows from 257. Watch the emitted phrases get longer as the text repeats.

The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.

• ABABABAB… — ABABABABABABAB
• course example — ABRACADABRABRABRA
• no repetition — abcdefghij
• repeated words — the cat the cat the cat

Open LZW compression in the player →

The rest of Data compression

• Run-length encoding Replace each run of identical symbols by the symbol and its length.
• Huffman compression Merge the two least frequent symbols, repeatedly.