Lempel–Ziv–Welch compression builds its own dictionary from the message as it reads it, instead
of needing one handed to it in advance. It keeps a current matched string w (starting
as the first character) and repeatedly tries to extend it with the next character c: if
w+c is already a known dictionary entry, extend the match and keep reading — nothing is
emitted yet. The moment w+c is not already known, that's the signal to act: emit
the code for the longest match that was known (w), add the new, longer string
w+c to the dictionary under the next free code, and restart the match at c
alone. Every code transmitted refers to a string the decoder has necessarily seen built the exact
same way, in the exact same order — which is the whole trick: the decoder can reconstruct the
identical dictionary purely by watching the codes go by, so nothing but the codes themselves ever
needs to cross the wire.
This is the site's first entry filed under a dedicated Compression category. Huffman Coding and Burrows–Wheeler Transform are both already compression-adjacent, but neither is filed here — Huffman's own category is Greedy (its interesting property is a provably-correct greedy choice, not the compression itself) and BWT is filed under Exact Match (it's a reversible *rearrangement* that makes later compression easier, not a compressor on its own). LZW is the site's first entry whose whole subject is building and transmitting a compressed encoding, and the mechanism — an adaptive, self-describing dictionary instead of a fixed, pre-agreed table — is a genuinely different idea from Huffman's frequency-driven tree, worth a category of its own rather than being squeezed into either existing one. Run-Length Encoding, the category's second entry, is the much simpler idea this one is implicitly competing with — see that page's own Pitfalls for measured, head-to-head numbers on where each one wins.
Type a message and press Load, then Step or Run. Each step either extends the current match (a chip briefly highlighted below shows nothing new was emitted) or emits a code and adds one new dictionary entry, highlighted the moment it's created. The default message is the classic textbook example — short enough to trace by hand, but see the first Pitfall below for what its code count doesn't tell you. Try a message with longer, more frequent repeats (or just a longer message) to see where LZW actually starts winning.
dictionary (code : string)
emitted codes, in order
On the default message ABABABABA (9 characters, alphabet {A, B}, so
A starts as code 0 and B as code 1, next free code 2): the match starts at
A. AB isn't known yet, so emit code 0 (for A), add
AB as code 2, restart at B. BA isn't known, so emit code 1
(for B), add BA as code 3, restart at A. Now AB
is known (code 2 from the first round), so the match extends to AB without
emitting anything. ABA isn't known, so emit code 2 (for AB), add
ABA as code 4, restart at A. AB is known again, extend to
AB; ABA is also now known (code 4), extend further to ABA.
ABAB isn't known, so emit code 4 (for ABA), add ABAB as code 5,
restart at B. Finally BA is known, extend to BA, and the
message ends — emit the code for whatever's left, 3 (for BA). Five codes —
0, 1, 2, 4, 3 — cover all nine characters, each one naming a string the dictionary had
already built from strings seen earlier in the same message. A decoder replaying those five
codes rebuilds the identical dictionary one entry behind the encoder (see Pitfalls for exactly what
"one behind" costs), never needing a separate table the way
Huffman Coding does.
function lzwEncode(input) {
const alphabet = [...new Set(input)].sort();
const dict = new Map();
alphabet.forEach((ch, i) => dict.set(ch, i));
let nextCode = alphabet.length;
const out = [];
let w = input[0];
for (let i = 1; i < input.length; i++) {
const c = input[i];
const wc = w + c;
if (dict.has(wc)) {
w = wc;
} else {
out.push(dict.get(w));
dict.set(wc, nextCode++);
w = c;
}
}
out.push(dict.get(w));
return { codes: out, alphabet };
}
function lzwDecode(codes, alphabet) {
const dict = new Map();
alphabet.forEach((ch, i) => dict.set(i, ch));
let nextCode = alphabet.length;
let w = dict.get(codes[0]);
let out = w;
for (let i = 1; i < codes.length; i++) {
const k = codes[i];
// k === nextCode is the one code the decoder can't look up directly yet —
// see Pitfalls for why that's not a bug, and why it's not rare.
const entry = dict.has(k) ? dict.get(k) : w + w[0];
out += entry;
dict.set(nextCode++, w + entry[0]);
w = entry;
}
return out;
}
The decoder can be asked to look up a code that isn't in its dictionary yet — and that's
the normal case, not a bug. Encode aaaa (alphabet {a}, code 0):
emit 0 (for a), add aa as code 1; aa is now known so the match
extends through the third a; emit 1 (for aa), add aaa as code
2; the message ends, emit 0 (for the last a). Codes: 0, 1, 0. Now decode
them, tracking exactly what the decoder's dictionary knows at each step:
| code read | in decoder's dict yet? | entry used | output so far | new entry added |
|---|---|---|---|---|
| 0 | yes (initial) | a | a | — |
| 1 | no | w + w[0] = a+a = aa | aaa | 1 → aa |
| 0 | yes | a | aaaa | 2 → aaa |
At the second code, the decoder's dictionary only has entry 0 — it was never told entry 1 directly,
because the encoder adds wc to its own dictionary the instant it emits a code for
w, one full code ahead of when the decoder (which adds entries only after decoding a code)
catches up. The fix, used in the reference implementation above, is the one case worth naming on
purpose: whenever the code read equals the next code the decoder is about to assign, the
missing entry must be w + w[0] — the previous output extended by its own first character
— which is provably always the right answer (the encoder could only have just added
w + (w's first future character), and the only way a string can be extended into itself
again at the start is by repeating its own first character). This isn't a rare edge case: a 20,000-trial
fuzz test pairing the two functions above (random strings, alphabet sizes 1–4, lengths 1–30) found
zero round-trip failures, and the special case fired 28,842 times
across those trials — almost one and a half times per trial on average, not an exotic corner.
A short code count doesn't mean a short encoding. The "Why it works" trace above
found 5 codes for 9 characters, which sounds like obvious compression — but each code has to be wide
enough to address every dictionary entry that exists by the time it's sent, and that width only grows.
Packed at the narrowest width each code could actually use (1 bit while only 2 entries exist, 2 bits
once a third is added, and so on), those 5 codes cost 11 bits — more than the
9 bits a fixed 1-bit-per-character code over the same 2-symbol alphabet would need.
ABABABABA, a textbook favorite precisely because the match-and-extend mechanism is easy to
trace by hand, is actually a losing case for real variable-width LZW. The same measurement on
other short inputs: abracadabra — the Huffman
Coding page's own default example — barely breaks even (32 bits vs. 33 fixed-width, a 3% win);
mississippi and the quick brown fox outright expand (30 vs. 22 bits, and 96
vs. 76 bits — 36% and 26% larger than doing nothing). Same shape as Huffman's own "the table has to be
transmitted too" pitfall — a real cost that has to be earned back — just a different mechanism: growing
code width instead of a separately-shipped table. LZW's win shows up on longer input with longer, more
frequent repeats, not on short, cleanly didactic examples.
The dictionary has no size limit of its own. Nothing in the mechanism above ever stops it from growing — a long, highly repetitive input keeps adding entries for as long as it runs, and so does the code width needed to address them. Every real LZW-based format (GIF's version caps codes at 12 bits, 4,096 entries, with a reserved "clear code" that resets both sides' dictionaries back to their starting state) has to pick a cap and a reset rule, and the encoder and decoder have to agree on exactly the same one — if either side's dictionary ever diverges from the other's, every code after that point decodes to the wrong string with no error raised anywhere, since a wrong-but-valid lookup looks identical to a right one from inside the algorithm itself.
Time: O(n) for a message of length n, amortized — one
constant-size amount of work (a dictionary lookup, maybe an insert, maybe an emit) per input character,
assuming the dictionary's get/set run in O(1) average, which a hash map keyed by string
gives as long as string hashing itself is treated as free. A real high-throughput implementation
usually avoids even that hashing cost by keying the dictionary with a trie instead — one character
lookup plus a parent pointer per step, rather than re-hashing the whole growing prefix w on
every comparison — but the asymptotic shape is the same either way. Decoding is symmetric,
O(n) in the number of codes read, with the one extra constant-time branch (the Pitfall
above) per code. Space: O(n) worst case — a message with no repeats at
all adds one new dictionary entry per character and never reuses any of them, bounded in practice by
whatever cap and reset rule a real implementation enforces (see the Pitfall above).
See Choosing a Compression Approach for how this entry compares against the site's other six — short version: reach for LZW when repeats exist but aren't adjacent.