ABC Tools

Compression, Explained

After reading this you can predict, within a few bytes, how much RLE, LZ77 and Huffman coding will shrink or grow a given piece of text, and explain why random noise defeats all three.

Compression works by spending fewer bits on the parts of your data that are predictable. Every scheme in this playground is a bet: it wagers that your text has structure of some particular kind, and it pays a small overhead to exploit that structure. When the bet pays off, the output is smaller. When there is no structure to find, the overhead makes the output larger.

Here is the hook. Type the 40-character string aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa. Run-length encoding records it as one run: the character a, repeated 40 times. At 16 bits per run that is 2 bytes of output for 40 bytes of input, a ratio of 20 to 1. Now type 40 characters of random letters. RLE finds no repeats, writes 40 runs of length 1, and produces 80 bytes: twice the original. Same algorithm, opposite result. The data decided the outcome.

What the three algorithms actually do

Each algorithm attacks a different kind of redundancy. Knowing which is which tells you in advance which will win on your text.

Run-length encoding (RLE)
Replaces a run of identical adjacent characters with the character and a count. It only sees redundancy that sits in consecutive positions. AAAB becomes (A,3)(B,1).
LZ77
Scans left to right and replaces any phrase it has already seen with a back-reference: a pair (distance, length) pointing at the earlier copy. This catches repeated phrases anywhere behind the current position, not just adjacent ones. It is the dictionary stage inside ZIP, gzip and PNG.
Huffman coding
Ignores position entirely and looks at how often each character appears. Frequent characters get short bit codes, rare ones get long codes. It attacks uneven symbol odds, not repetition.

Because they target different structure, they combine well. The DEFLATE format used by ZIP and PNG runs LZ77 first to remove repeated phrases, then Huffman-codes whatever symbols remain.

When each one helps, and when it hurts

RLE wins on long identical runs: solid regions in bitmap images, padding, or a chorus of one letter. It is almost useless on ordinary prose, where runs longer than two are rare. In the simplified cost model here, RLE pays 16 bits (2 bytes) per run. A run must be at least 3 characters long before it saves anything, since 3 raw characters cost 3 bytes and one run costs 2.

LZ77 wins whenever whole phrases recur: repeated words, repeated lines, HTML tags, the second verse of a song. Its weakness is short or unique text. A single literal character costs 9 bits here, more than the 8 bits it would take raw, so a string with no repeats grows by one eighth.

Huffman wins when the character frequencies are lopsided, for example DNA using only four letters, or English where e and space dominate. It pays for a code table up front. On very short inputs that table can cost more than the coding saves.

No lossless scheme can beat the entropy of the source. This is Shannon's source-coding theorem, and it is a hard floor, not a target you approach with cleverness. Uniformly random data has maximal entropy, so every algorithm here leaves random noise the same size or larger. If a product claims to compress arbitrary random data, it is wrong.

The formula behind the floor

Huffman coding aims at the Shannon entropy of the source. For a text where character i appears with probability p_i, the entropy in bits per character is:

H = -\sum_{i} p_i \log_2 p_i

Here p_i is the fraction of characters equal to symbol i, and the sum runs over every distinct symbol. The term -\log_2 p_i is the ideal code length in bits for that symbol: common symbols (large p_i) get short codes, rare ones get long codes. Multiply H by the number of characters to get the theoretical minimum size in bits.

Two special cases pin down the range. If all n symbols are equally likely, then p_i = 1/n and H = \log_2 n, the maximum. If one symbol has probability 1, then H = 0: nothing to encode. Huffman gets close to H but usually not exactly, because code lengths must be whole numbers of bits.

For a two-symbol source with probabilities p and 1-p, entropy is H = -p\log_2 p - (1-p)\log_2(1-p). At p=0.5 entropy is 1 bit per symbol (no compression possible). At p=0.9 it drops to 0.469 bits. At p=0.99 it is 0.0808 bits, so a 99 percent skew is compressible to about one twelfth of its raw bit count.

A worked example with the sample text

Compressing a repetitive chorus

Take a 24-character string with obvious structure: abcabcabcabcabcabcabcabc, which is abc repeated 8 times. Work each algorithm by hand using the playground's cost model.

  1. Raw size. 24 characters at 8 bits each is 192 bits, or 24 bytes.
  2. RLE. No character repeats adjacently: the sequence is a, b, c, a, b, c and so on. That is 24 runs of length 1. At 16 bits per run the output is 24 × 16 = 384 bits, or 48 bytes. RLE doubled the size.
  3. LZ77. The first 3 characters abc are literals at 9 bits each: 27 bits. From position 4 onward, everything is a copy of earlier text. One back-reference of distance 3 and length 21 covers the entire tail. At 18 bits per reference that is 18 bits. Total 27 + 18 = 45 bits, under 6 bytes. LZ77 found the phrase and won big.
  4. Huffman. The three characters appear equally, 8 times each, so p_i = 1/3 and H = \log_2 3 \approx 1.585 bits per character. Huffman must use whole-bit codes, so it assigns lengths 1, 2, 2 bits: total 8(1) + 8(2) + 8(2) = 40 bits of codes, plus a small table. Roughly 5 to 7 bytes.

Same 24 bytes in, three very different outputs: 48 bytes from RLE, about 6 from LZ77, about 6 from Huffman. The winner depends entirely on which kind of structure the text carries. Here the repetition is positional, so the dictionary scheme and the frequency scheme both cash in, while RLE sees nothing and pays overhead.

RLE grows the input to 48 bytes while LZ77 and Huffman shrink it to roughly 6. Structure that is invisible to one scheme can be obvious to another.

Reading the size ribbons

The two ribbons beneath the text let you attribute every output byte to a patch of input. A wide input patch sitting over a thin output patch is a win: many characters collapsed into few bits. A thin input patch over a wide output patch is a loss: the overhead exceeded the saving. Look for the transition points. In LZ77 the first appearance of a phrase is always literals (costly), and every later appearance is a back-reference (cheap), so repeated material shows a thin ribbon only from its second occurrence on.

Watch the arcs in LZ77. Each arc points from a back-reference to the earlier text it reuses. Long arcs mean the algorithm reached far back to find a match; short arcs mean the repeat was nearby. A dense fan of arcs is a highly self-similar input.

The single number to read is the compression ratio, output divided by input. Below 1 means the file shrank. Above 1 means it grew. That ratio is a direct measurement of how much exploitable structure your data holds, given the kind of structure each algorithm can see.

Ratios fall as structure rises. Random noise sits above 1 because LZ77 pays 9 bits per literal and finds nothing to reference.

Common mistakes

The first mistake is expecting compression on already-compressed or random data. A JPEG, an MP3 or a ZIP is close to random at the byte level, so running any of these schemes over it grows the file. That is not a bug in the algorithm, it is the entropy floor.

The second mistake is ignoring overhead on tiny inputs. Every scheme here pays a fixed cost: 16 bits per RLE run, 9 bits per LZ77 literal, and a Huffman code table up front. On a 4-character string with no repeats, all three lose. Compression is a game of amortizing overhead over many bytes, so short inputs are the worst case.

To see the entropy floor directly, compress the same text twice: once as typed, once after running it through one of the schemes and feeding the output back in. The second pass almost never helps and often hurts. Once the structure is gone, there is nothing left to remove.

The third mistake is treating one algorithm's failure as proof the data is incompressible. RLE failing on abcabc... tells you nothing about LZ77, which crushes it. Structure has kinds. A scheme only reports on the kind it can detect.

Related tools

Compression measures structure, and several other toys on this site generate structure you can feel in the ratios. The one-dimensional patterns in Elementary Cellular Automata range from perfectly periodic (rule 90, highly compressible) to the noise-like output of rule 30, which resists compression much as random text does. Conway's Game of Life produces sparse, structured grids that RLE-style schemes handle well, which is exactly why the community stores patterns in run-length encoded files. For the frequency side of the story, Random Walk Explorer shows how randomness accumulates, and randomness is precisely what has no structure to compress.

Frequently asked questions

Why does compressing random text make it bigger?

Random data has maximal entropy, so there is no pattern to exploit. Meanwhile each scheme pays overhead: LZ77 spends 9 bits per literal against 8 bits raw, so pure noise grows by about one eighth. This is Shannon's floor at work, not a flaw.

Which algorithm is best?

None in isolation. RLE wins on long identical runs, LZ77 on repeated phrases, Huffman on skewed character frequencies. Real formats stack them: DEFLATE runs LZ77 then Huffman, so it removes repeated phrases and uneven odds in two passes.

What compression ratio is good?

It depends entirely on the source. English prose typically compresses to around 0.5 to 0.6 of its size with LZ77. A file of one repeated character can reach 0.08 or lower. Random noise cannot go below about 1.0 and usually exceeds it. The ratio is a property of the data, not the tool.

Why does Huffman need whole-bit codes when the entropy is fractional?

Each character is encoded with an integer number of bits, but the ideal length -\log_2 p_i is usually fractional. For three equal symbols the ideal is 1.585 bits each, yet Huffman must use 1 or 2. That rounding is why Huffman output slightly exceeds the entropy bound. Arithmetic coding narrows the gap by not rounding per symbol.

Is any of this lossless?

All three are lossless: you can reconstruct the original text exactly. Lossy schemes like JPEG and MP3 achieve much higher ratios by discarding detail the eye or ear will not miss, which is a different problem from the one shown here.

Try it yourself in the tool

Related tools

3D Geometry Board

Points, lines, planes, spheres and polyhedra on an orbiting camera — slice solids with planes, unfold nets, drop the Dandelin spheres into a cone and drag everything.

Bézier Curve Playground

Drag control points and watch De Casteljau’s algorithm construct a Bézier curve step by step.

Central Limit Theorem Demo

Sample from any lopsided distribution and watch the averages pile up into a bell curve.

Conway’s Game of Life

Paint cells and watch Conway’s cellular automaton breed gliders, guns and oscillators.

Dynamic Geometry Board

Construct with points, lines, circles and transformations, then drag anything — the construction stays true, and a checker tells you which relations are theorems.

Fantasy Map Generator

Roll a seed and get a continent: coastlines, mountains, rivers, biomes and named towns, ready for your campaign.