Compression, one decision at a time
How DEFLATE works, visually
Every PNG image, every ZIP archive, every Word document and most of the web is squeezed by the same algorithm, DEFLATE, from 1996. It does two simple things, over and over. The player on the rightbelow is decompressing a real file — a short text — right here in your browser, and every step of the way below it can show you.
1 Say it once, then point back
Text repeats itself. So do images, where a row of sky looks like the row above it. DEFLATE keeps the last 32 KB it has written, and when something comes up again it writes, instead of the bytes, two numbers: how far back the earlier copy is, and how long it is.
A copy can even overlap itself: "go back 1, copy 50" writes the last byte fifty more times. That is how long runs of the same colour shrink to almost nothing.
2 Short codes for common things
What is left — single letters, and the numbers of each copy — is written in a Huffman code: symbols that come up often get short codes, rare ones get long codes. In this text a space, and the letters e, a, o and t, cost 4 bits each; a capital S costs 8.
The codes are canonical: sorted by length, then by symbol. So a decoder needs only each symbol's code length to rebuild the whole table, and reads one bit at a time until the code it has is in the range for its length. The panel under the player shows exactly that walk.
3 Each block brings its own codes
The stream is cut into blocks. A block can be stored as it is, use a fixed code the standard defines, or — usually — bring its own, tuned to its data. That custom table is itself compressed: a small code for the code lengths, and run-lengths for the stretches of symbols that never appear.
4 What it adds up to
Put together, these two ideas are all there is. The text in the player shrinks to well under half its size.
5 Where you have met it
Inside every PNG (its IDAT chunks), every ZIP archive — which includes Word, Excel and PowerPoint files, Android apps and e-books — gzip files, and much of what your browser downloads. hexscope can play any of them.
Open a PNG or a ZIP and press Watch it decompress.
The standard is RFC 1951, nine pages long. hexscope's decoder, the one running here, is open source.