DEFLATE isn't a new idea — it's two of this site's own entries, stacked. First LZ77 Compression's own Pitfalls named the variant real formats actually use: LZSS, which replaces LZ77's always-emit-a-triple token with a single flag bit (literal, or match) so a plain character never pays for an offset and length field it doesn't need. DEFLATE takes that token stream — the exact same literal/match decisions LZSS already makes — and Huffman-codes it instead of packing it at a fixed width. The flag bit disappears entirely in the process: real DEFLATE gives literal bytes (0–255) and match-length codes (257–285) seats in the same alphabet, so the Huffman tree itself assigns short codes to whichever is more common and the "is this a literal or a match" question is answered by which code arrives, at no bit cost of its own. Match distances get a second, separate alphabet, for a reason measurable below. This page builds a simplified version of exactly that pipeline and measures what each layer is actually worth.
This is the Compression category's fifth entry — not a new redundancy shape like RLE, LZW, or LZ77 each bring, but the first entry that exploits two of the site's existing shapes in the same format: LZ77's bounded-window substring matching to find repeats, and Huffman's frequency-skew coding to pack whatever's left. Neither constituent page's own numbers say what the combination is worth — that's what this page measures.
Type a message and press Encode. This fixes the window at 32 characters (6-bit offsets) and the lookahead at 15 (4-bit lengths) — the same sizing LZ77's own fixed-tax measurement uses, so every number below lines up directly against that page's published bits. The LZSS tokenizer below only emits a match when it's actually cheaper than the literals it would replace (see the min match figure); everything after that — the literal/length alphabet and the separate distance alphabet — gets its own Huffman tree, built live from this exact token stream.
LZSS tokens (flag-bit format — literal, or match offset/length)
literal/length alphabet (shared — this is where the flag bit disappears)
distance alphabet (separate — only matches contribute)
Take the default message, ABABABABA (9 characters) — the same string LZ77's own worked example starts from. With a 2-symbol
alphabet (charBits = 1), LZSS's break-even point is a 6-character match (shorter than that, three
literals at 2 bits each beats one match's 11-bit flag+offset+length cost): the first two characters
(A, B) have nothing to match yet, so both go out as literals. At position 2
the window holds AB, and because the message is perfectly periodic, the longest match
runs all the way to the 7-character lookahead cap: offset 2, length 7, covering the rest of the
message. Three tokens total: lit A, lit B, match(2,7).
The literal/length alphabet this builds has exactly three symbols — the literal A, the
literal B, and the length value 7 — each appearing once. Standard Huffman
on three equally-frequent symbols gives two of them a 2-bit code and one a 1-bit code (5 bits total,
however the ties break — any valid Huffman tree on this frequency multiset costs the same 5 bits). The
distance alphabet has a single symbol, offset 2, which costs the usual one bit a
one-symbol alphabet is charged by convention (there's no choice to encode, but a real bitstream still
needs to know the stream continues). Total: 6 bits — against LZSS's own 15 bits for
the identical tokens (2 + 2 + 11, paying the full fixed offset/length field for the one match) and
LZ77's published 32 bits for the same string. Folding the flag bit into the alphabet and then
Huffman-coding what's left compounds into a real, measured win — before a single bit is spent
transmitting either tree.
Round-trip tested with a 20,000-trial fuzz test (random strings, alphabet size 1–4, length 1–30, window 20, lookahead 10, minimum match length drawn randomly from 1–5 each trial — the same harness convention LZ77's own page uses, extended to confirm decode correctness holds regardless of what match-vs-literal policy the encoder follows) — zero mismatches.
function lzssEncode(input, windowSize, lookaheadSize, minMatch) {
const tokens = [];
let pos = 0;
while (pos < input.length) {
let bestLen = 0, bestOffset = 0;
const windowStart = Math.max(0, pos - windowSize);
const maxLen = Math.min(lookaheadSize, input.length - pos);
for (let start = windowStart; start < pos; start++) {
let len = 0;
while (len < maxLen && input[start + len] === input[pos + len]) len++;
if (len > bestLen) { bestLen = len; bestOffset = pos - start; }
}
if (bestLen >= minMatch) {
tokens.push({ type: 'match', offset: bestOffset, length: bestLen });
pos += bestLen;
} else {
tokens.push({ type: 'lit', char: input[pos] });
pos += 1;
}
}
return tokens;
}
function lzssDecode(tokens) {
let out = '';
for (const t of tokens) {
if (t.type === 'lit') { out += t.char; continue; }
// Same one-character-at-a-time rule as LZ77's own decoder — a match can reach past
// its own starting point, copying characters this token is still in the middle of writing.
for (let i = 0; i < t.length; i++) out += out[out.length - t.offset];
}
return out;
}
// Standard Huffman tree over a symbol -> frequency map, returning symbol -> code length.
// (Only the lengths are needed to measure total bits — this page doesn't assign or ship
// actual bit patterns, the same scope Huffman Coding's own page stays within.)
function huffmanCodeLengths(freq) {
const symbols = Object.keys(freq);
if (symbols.length === 1) return { [symbols[0]]: 1 };
let nodes = symbols.map((s) => ({ sym: s, freq: freq[s] }));
while (nodes.length > 1) {
nodes.sort((a, b) => a.freq - b.freq);
const a = nodes.shift(), b = nodes.shift();
nodes.push({ freq: a.freq + b.freq, left: a, right: b });
}
const lengths = {};
(function walk(node, depth) {
if (node.sym !== undefined) { lengths[node.sym] = depth || 1; return; }
walk(node.left, depth + 1);
walk(node.right, depth + 1);
})(nodes[0], 0);
return lengths;
}
Folding the match/literal choice into the alphabet, instead of spending a flag bit on it, is a real and consistent win — measurable the moment the tree-transmission cost is set aside. Run the same six strings LZ77's own Pitfalls already measured through LZSS's flag-bit format, then through this page's Huffman layer on top of the identical token stream (so the comparison isolates what Huffman coding itself adds, without also re-deciding which spans get tokenized as matches):
| input | LZ77 (always-triple) | LZSS (flag bit) | DEFLATE, no tree sent |
|---|---|---|---|
ABABABABA | 32 | 15 | 6 |
abracadabra | 75 | 39 | 21 |
mississippi | 72 | 32 | 19 |
the quick brown fox | 224 | 95 | 75 |
LZSS alone roughly halves LZ77's bits on every row — the flag-bit fix LZ77's own page named but never measured. Folding that same flag bit into a shared literal/length alphabet and Huffman-coding the result cuts the cost again, by more than half on three of the four rows. Neither layer is doing something the other couldn't on its own data — they're stacking because they exploit genuinely different redundancy (LZ77's page-spanning repeats, Huffman's frequency skew in whatever's left), the same "two shapes at once" point the category entry above makes.
Two Huffman trees are two tree-transmission costs, and on a short message that tax outweighs every other format on this page combined. Huffman Coding's own page already measures one tree's overhead against one message; DEFLATE pays that cost twice (once for the literal/length alphabet, once for distances), using the same per-distinct-symbol accounting (an id wide enough to address the alphabet, plus a code-length field wide enough for the tree's own tallest code):
| input | LZ77 | LZSS | DEFLATE, no tree | DEFLATE, + both trees | fixed-width |
|---|---|---|---|---|---|
ABABABABA | 32 | 15 | 6 | 17 | 9 |
abracadabra | 75 | 39 | 21 | 53 | 33 |
mississippi | 72 | 32 | 19 | 46 | 22 |
the quick brown fox | 224 | 95 | 75 | 187 | 76 |
ab repeated 100× (200 chars) | 164 | 153 | 38 | 56 | 200 |
abcdef repeated 50× (300 chars) | 322 | 244 | 68 | 117 | 900 |
With both trees included, DEFLATE is the worst of all four real formats on every single short-message row — worse than LZ77's always-pay-the-full-triple format it's supposed to improve on, because now it's paying for two trees on top of that. The same two rows flip completely once the message is long and repetitive enough: DEFLATE with both trees beats LZ77 by roughly 3-6x and the fixed-width baseline by up to 7.7x, because the tree cost stays flat (bounded by how many distinct symbols appear, not by message length) while every other format's cost keeps growing with the message. This is the exact crossover shape Huffman's own page measured for one tree, now compounding for two — a format with more layers of cleverness has more fixed cost to earn back, not less.
The break-even match length a fixed-width LZSS field accepts isn't a constant — it moves
with the alphabet. The demo's own "min match" figure is 6 characters for the two-symbol
strings above (ABABABABA, and ab repeated), but only 3 for every
wider-alphabet string tested (abracadabra, the quick brown fox,
abcdef repeated) and 4 for mississippi. A wider alphabet makes each literal
costlier on its own (more bits per character), which lowers the match length needed to beat paying for
those same characters as literals — exactly the arithmetic the reference implementation runs once per message, not a fixed
textbook constant like LZ77's own always-match-if-found rule needs.
Time: tokenizing is the same O(n·W·L) window scan LZ77's own Complexity section already covers (a real
implementation swaps in a hash chain the same way, independent of the format built on top). Building
each Huffman tree costs O(k log k) for k distinct symbols — Huffman's own Complexity section derives the same
bound — and k is bounded by the alphabet size plus the lookahead's own range of possible
match lengths, never by the message length, so this stays small even on long input. Decoding is
O(n): look up a symbol's code, append a literal or copy a match, same as every format on
this page. Space: O(W + L) for the window and lookahead, plus
O(k) for the two small trees — the fixed-cost side of the Pitfall above, bounded by how
much the alphabet and lookahead vary, not by how long the message runs.
See Choosing a Compression Approach for how this entry compares against the site's other six.