Cairn
guides · comparison, not a new algorithm

↩ back to Guides

Choosing a Compression Approach

Six entries on this site compress the same kind of thing — a message made of repeated symbols — but each one exploits a genuinely different shape of redundancy, and none of them is simply better than the others. Run-Length Encoding, LZW Compression, LZ77 Compression, and DEFLATE are filed under this site's own Compression category; Huffman Coding is filed under Greedy instead (its own page explains why: the interesting property is a provably-correct greedy choice, not the compression itself), but it competes directly with the others on the same job. Picking between the first five is really a question of what kind of redundancy the input actually has, not a ranking; DEFLATE is the odd one out — it doesn't exploit a shape none of the other five already cover, it stacks two of their shapes in one format, measured below.

A seventh Compression-category entry, Move-to-Front, is deliberately left out of that "picking between" framing: it never shrinks a message by itself (see below), so there's no scenario where it's the answer to "which of these do I reach for" the way the other six are. It still belongs on this page, because it changes what the other entries can achieve when stacked on top of it.

Three questions, in order

Does the redundancy sit in long, uninterrupted runs of the exact same symbol, right next to each other? If so, Run-Length Encoding is the cheapest possible answer — see below for exactly how decisively it wins on that shape, and how badly it loses otherwise.

If not: is the redundancy a substring that repeats somewhere earlier in the message, even if not immediately adjacent? That's LZW Compression's whole reason to exist — it can see a repeat anywhere in the history already read, not just the character immediately to the left. LZ77 Compression exploits the identical shape of redundancy but only within a fixed-size window of recent history, not the whole message — see below for exactly what that bound costs and what it buys back.

If neither — the input just has a skewed per-symbol frequency distribution, with no exploitable adjacency or substring structure at all — the choice is between Huffman Coding and Arithmetic Coding, and that split turns on a narrower question of its own: how far the skew sits from a power of one-half, and how much implementation complexity is worth paying to get the rest of the way to the entropy floor. See below for the measured gap.

Redundancy is adjacent: Run-Length Encoding

Run-Length Encoding's own page measures six inputs head-to-head against LZW at the narrowest bit width each scheme could actually use for that input:

inputRLE bitsLZW bitsfixed-width baseline
50×a72650
aaaaabbbbbccccc152830
aabbccddeeffgghhiijj609380
mississippi323022
abracadabra443233
ABABABABA18119

The rows are ordered from RLE's best case to its worst. On one long uninterrupted run, RLE wins by very close to 4x over LZW — exactly the shape it's built for, at essentially no implementation cost: O(n) time, no dictionary to build or cap, no table to transmit, the single cheapest tool on this page when the shape actually fits. The moment adjacency disappears — mississippi's only repeats are two separated doubled letters, ABABABABA never repeats adjacently at all — RLE not only loses to LZW, it loses to doing nothing (both expand past the fixed-width baseline on the bottom two rows). RLE's own Pitfalls section names the practical answer real formats already use: run RLE as a cheap first pass specifically to catch long runs (PNG's filtering step does exactly this) before a heavier stage looks for everything else — not an either/or choice in practice, a pipeline.

Redundancy is a repeated substring, anywhere (or nearby): LZW vs. LZ77

LZW Compression builds its dictionary adaptively as it reads, so a repeat anywhere earlier in the message — not just immediately to the left — gets caught. That's exactly why it wins the middle two rows of the table above: abracadabra and mississippi both have real repeated letters with no adjacency to exploit, which RLE can't see and LZW can. The cost of that wider view is real and measured on the same page: a short code count doesn't mean a short encoding, since every code has to be wide enough to address the whole dictionary built so far — ABABABABA, the classic five-codes-for-nine-characters textbook example, actually costs 11 bits against a 9-bit fixed-width baseline, a losing case for the mechanism that looks the most impressive traced by hand. LZW's dictionary also has no size limit of its own; every real LZW-based format (GIF caps at 12-bit codes, 4,096 entries, with a reserved clear code) has to agree on a cap and reset rule in advance, baked into the format rather than carried per message.

LZ77 Compression exploits the same shape of redundancy — a repeated substring, not necessarily adjacent — but only within a fixed-size sliding window, and pays a fixed per-token cost (an offset and a length) whether or not a match was even found. Its own Pitfalls measure both ends of that tradeoff on the exact same short strings above:

inputLZ77 bitsLZW bitsfixed-width baseline
ABABABABA32119
abracadabra753233
mississippi723022
the quick brown fox2249676

LZW wins every row here, sometimes by more than 2x — on short input, LZW's lower per-code overhead beats LZ77's fixed offset+length tax every time. Running both pages' own reference implementations on the same longer, more repetitive inputs LZ77's own page measures finds the gap narrows but doesn't flip in LZ77's favor by default:

inputlengthLZ77 ratioLZW ratio
a sentence repeated 3×1340.93x0.83x
ab repeated 100×2000.56x0.57x
abcdef repeated 50×3000.26x0.33x

(ratio = encoded bits ÷ fixed-width baseline bits; lower is better.) LZW actually wins the first row and ties the second — its adaptive dictionary has no per-token tax to pay off, so it doesn't need LZ77's longer runs to break even. LZ77 only pulls ahead on the third row, where match lengths are long enough (6-character repeats, well inside its lookahead) that its per-token tax gets spread across more copied characters than LZW's per-code cost can match. Neither mechanism dominates the other on long input the way the short-input table above makes LZW look like the clear winner everywhere. The sharper, reliably measured difference between the two is memory, not bits: LZ77's window and lookahead are two fixed numbers chosen once in advance, so its memory use never grows past them no matter how long the message runs; LZW's dictionary has no cap of its own and grows with the message (the real-world cap-and-reset rule mentioned above exists specifically to bound that). LZ77 can also lose a match completely that LZW would never miss — its own page shows one character of window shrinkage turning a 7-token encoding into 12 tokens with zero compression, because the only repeat in that message sat one position past what the narrower window could reach. Reach for LZW when the repeat could be anywhere and unbounded memory is acceptable; reach for LZ77 when memory has to stay flat regardless of message length, accepting that a distant-enough repeat becomes invisible. On data that's mostly long runs, it's RLE's territory instead, per the table at the top of this guide.

Redundancy is just skewed frequency: Huffman vs. Arithmetic Coding

Neither RLE nor LZW helps once the redundancy has no spatial shape at all — just some symbols occurring more often than others, with no run and no repeated substring to point at. Huffman Coding and Arithmetic Coding both spend fewer bits on common symbols and more on rare ones, but at different granularities: Huffman can only spend a whole number of bits per symbol, because every code is a path through a binary tree; Arithmetic Coding narrows a single interval instead, so a symbol can be charged a fractional bit. Arithmetic Coding's own page measures exactly when that fractional accounting matters:

inputHuffmanArithmetic (guaranteed formula)entropy floor
abracadabra (11 chars)23 bits24 bits22.4 bits
20-char 90%/10% run20 bits11 bits9.4 bits

On abracadabra — a small, mildly skewed five-symbol alphabet — the two are a near wash; Arithmetic Coding's own safety-margin formula is actually one bit worse than Huffman's real output here (a direct search without that margin finds 22, one bit better, but that's not what a real streaming implementation can commit to without seeing the whole message first). The real, structural gap only opens on the second row: a two-symbol alphabet gives Huffman exactly two leaves and therefore exactly one bit per symbol no matter how skewed the frequencies get, so a 90%/10% split still costs the full 20 bits — Arithmetic Coding's guaranteed bound on the identical message is 11, essentially half, and within two bits of the true 9.4-bit floor. The gap is specifically a small-alphabet, far-from-power-of-one-half problem; Huffman's own measurement against real Dickens prose (616 characters, 30 distinct symbols, a flatter and far less skewed distribution than either row above) lands within 0.03 bits per symbol of its own entropy floor — nowhere near enough slack left for Arithmetic Coding's fractional-bit edge to matter in practice. Huffman Coding is the right default on ordinary text; Arithmetic Coding earns its complexity specifically on small, heavily skewed alphabets, and pays for it with a real cost Huffman has no equivalent of — a naive floating-point implementation's interval width runs out of precision and starts silently returning the wrong message, measured on that same page at 1.1% of trials failing by length 26 on a 2-bit-per-symbol source, and a full, undetectable collision by symbol 120 on a heavily skewed one.

Redundancy is both shapes at once: DEFLATE

DEFLATE doesn't answer the three questions above with a fourth shape of redundancy — it answers the first two with LZ77's own window-bounded substring search (by way of LZSS, the flag-bit variant LZ77's own page names but doesn't build), then Huffman-codes whatever that search produces instead of packing it at a fixed width. Its own page measures both layers on the same six strings LZ77's page already used:

inputLZ77LZSSDEFLATE, no tree sentDEFLATE, + both treesfixed-width
ABABABABA32156179
abracadabra7539215333
mississippi7232194622
the quick brown fox224957518776
ab repeated 100×1641533856200
abcdef repeated 50×32224468117900

Each layer is a real, compounding win on its own: LZSS's flag bit roughly halves LZ77's bits on every row, and folding that same flag bit into a shared literal/length alphabet (so Huffman coding replaces it instead of sitting alongside it) cuts the cost again. But two Huffman trees mean two tree-transmission costs — Huffman's own crossover lesson, paid twice — and on every short-message row above, that tax makes DEFLATE-with-both-trees the worst of all four real formats, not the best, even though it's built from two genuinely good ideas. The same format wins by 3-6x over LZ77 and up to 7.7x over the fixed-width baseline on the two long repetitive rows, where the tree cost (bounded by how many distinct symbols appear, not by message length) finally gets amortized. More layers of cleverness means more fixed cost to earn back first, not less — DEFLATE is both the best-case and worst-case format on this entire page, depending only on whether the message is long enough to pay for what it's carrying.

Not a fourth shape — a transform: Move-to-Front

Move-to-Front doesn't answer "does the redundancy sit in runs, repeated substrings, or frequency skew" with a new option — it emits exactly as many codes as the input has symbols, so by itself it never gets smaller. What it does is turn a shape none of the three questions above can see — a symbol recurring recently, not necessarily adjacently or often overall — into frequency skew that Huffman can then exploit. Its own page measures this directly by Huffman-coding five inputs twice, once as given and once after running them through Move-to-Front first:

inputHuffman aloneHuffman after Move-to-Front
mississippi21 bits16 bits
aabbaabbccddccdd32 bits25 bits
abcdefghijabcdefghij68 bits49 bits
abracadabra23 bits24 bits

The clearest win, aabbaabbccddccdd, has a perfectly flat letter frequency (four letters, four occurrences each) — Huffman alone can't beat the fixed-width baseline at all on that input, because a flat frequency table gives a frequency-driven code nothing to work with. Move-to-Front exposes the positional repetition Huffman is structurally blind to and hands it back as frequency skew instead, for a real 22% cut Huffman alone could never find. The one case where it backfires, abracadabra, is the same eleven-character input this guide's own table above already uses: its repeats are real but never close together, so a symbol's recency-based position isn't any smaller than its plain frequency rank already was — one bit worse, not better, for the extra transform step. Like the other six entries, it's order-sensitive — recency is position — but it needs no side information beyond the starting list both ends already agree on, the same no-side-channel property RLE, LZW, and LZ77 have.

A structural split verified directly: order matters to four of these, not the other two

The table in the first section already shows RLE and LZW swinging wildly on the exact same multiset of characters depending on their arrangement — aaaaabbbbbccccc costs RLE 15 bits, while the identical five as, five bs, and five cs scrambled into no-adjacent-repeats order would cost it far more. LZ77 is just as order-sensitive for the same structural reason LZW is — a repeat has to physically occur earlier in the message for the sliding window to find it at all, so scrambling can create or destroy matches exactly like it does for LZW's dictionary. DEFLATE inherits the identical sensitivity rather than adding a new reason for it — its own matching stage is LZSS's windowed search, the same mechanism LZ77 already uses, before any Huffman coding happens on top. Huffman Coding and Arithmetic Coding have no equivalent sensitivity, and that's checkable directly rather than just inferred from how each mechanism is described: both build their code purely from symbol frequency — a merge-by-count tree for Huffman, an interval sized by probability for Arithmetic Coding — never from where in the message a symbol occurs. Running both sites' own shipped reference implementations, unmodified, against four messages and three random scrambles of each (twelve scrambles total) confirmed every single one produces an output length identical to its unscrambled original — Huffman Coding's bit count and Arithmetic Coding's interval width never moved by even one bit when only the symbol order changed, holding the exact same frequency multiset fixed. Scrambling a message can turn a Run-Length Encoding win into a loss (per the table above) and changes what LZW's adaptive dictionary even sees, but it is provably invisible to Huffman and Arithmetic Coding — a real, structural line between the two pairs, not just a difference in how each one happens to perform on the inputs already chosen for their own pages.

What has to travel besides the code

RLE, LZW, and LZ77 are all self-describing — nothing beyond the encoded stream itself is needed to decode it (LZW's cap-and-reset rule and LZ77's window/lookahead sizes are both properties of the format, agreed once in advance, not data carried per message). Huffman and Arithmetic Coding both need outside help: a decoder can't reconstruct a frequency-driven code from the bitstream alone. Huffman's own page measures exactly how much that costs and when it pays off: a canonical code table costs 11 bits per distinct symbol on the Dickens passage above, and cumulative savings don't overtake that cost until 267 characters into the message — before that point, transmitting the table costs more than the compression saves. Arithmetic Coding's own page calls out the identical shape of cost for its own frequency table plus message length, "symmetric to Huffman coding's own need to transmit its tree" — but doesn't measure its own crossover point the way Huffman's page does, so that comparison stops at "the same kind of cost," not a second number to set against 267. DEFLATE's own page pays this cost twice over — one tree for literals and match lengths, a second for match distances — and measures the compounded crossover directly: on every short message it tries, both trees together cost more than the rest of the format combined, flipping only once the message is long and repetitive enough to amortize two tables instead of Huffman's one.

Side by side

EntryRedundancy shape exploitedOrder-sensitive?Side informationReach for it when
Run-Length Encoding long runs of the identical symbol, adjacent yes — extremely none the input is mostly long uninterrupted runs
LZW Compression repeated substrings, anywhere earlier in the message yes none per-message; a cap/reset rule agreed by the format repeats exist but aren't adjacent, memory can grow with the message
LZ77 Compression repeated substrings, within a fixed-size window yes none per-message; window/lookahead sizes agreed by the format repeats exist but aren't adjacent, memory has to stay flat
DEFLATE both at once: repeated substrings within a window, then skewed frequency in what's left yes — inherits LZSS's window search two code tables (literal/length + distance) — worse than everything short, best of all long repeats and frequency skew both matter, and the message is long enough to amortize two tables
Huffman Coding skewed symbol frequency, whole-bit granularity no — verified above code table (tree) — 267-character measured crossover on real prose default for frequency skew; simple, fast, no precision ceiling
Arithmetic Coding skewed symbol frequency, fractional-bit granularity no — verified above frequency table + length — same shape of cost, uncrossed-over here small alphabet, skew far from a power of one-half