Every Way We Compress Data, Visualised: RLE, Huffman, LZ77, DCT and Motion Compensation

By burt Published 2026-07-28 Class How Things Work Read 11 min

Every photo, video call, downloaded font and gzipped API response on the internet passes through a compression algorithm, and almost all of that machinery reduces to a handful of ideas that are each older than the personal computer. This piece works through five of them — run-length encoding, Huffman coding, dictionary (LZ77-style) compression, the discrete cosine transform used in JPEG, and the prediction step at the heart of modern video codecs — and animates each one operating on real, computed data rather than a diagram of the concept. The numbers in the animations, including the exact bit counts and DCT coefficients, come from actually running the algorithms, not from illustrative approximations.

Run-length encoding

The simplest useful compression technique replaces a run of identical values with a single (count, value) pair. A scanned document line that reads five white pixels, three black, seven white and two black — 17 pixels — becomes four pairs: (5,W) (3,B) (7,W) (2,B). Nothing about the data is approximated or discarded; decoding just re-expands each pair back into the run it represents, so run-length encoding (RLE) is lossless.

A scanline of black-and-white pixels collapsing into four (count, colour) pairs.

RLE’s biggest deployment was the fax machine. The ITU-T’s Group 3 standard (T.4) run-length-encodes each scanned line and then Huffman-codes the run lengths themselves — a technique called Modified Huffman. Group 4 (T.6), which followed, extended this to compare each line against the one before it rather than encoding every line from scratch, and reached compression ratios of roughly 20:1 to 60:1 on the ITU’s standard test images, because a page of text or line art is mostly long runs of white. The same idea survives today in the RLE variant of the Windows BMP format and in Apple’s PackBits scheme used in TIFF and early Mac graphics formats.

The technique’s entire value depends on runs actually existing. A scanned fax page or a screenshot of a text document is full of them. A photograph, where adjacent pixels rarely share an exact value, is not — run-length encoding a photo typically saves almost nothing, and a naive implementation can even make the file larger, because every non-repeating pixel still needs a count field.

Huffman coding

Where RLE exploits repetition within a sequence, Huffman coding exploits how often each distinct symbol appears, assigning shorter binary codes to more frequent symbols and longer codes to rarer ones. In the word ABRACADABRA, the letter A appears five times, B and R twice each, and C and D once each. A fixed code would need 3 bits per letter (to cover 5 distinct symbols) for 33 bits total. Building a Huffman tree — repeatedly merging the two least frequent nodes into a parent whose frequency is their sum, until one root remains — produces the codes A=0, C=100, D=101, B=110, R=111, for a total of 23 bits: a 30% reduction, with no information lost.

Building a Huffman tree from ABRACADABRA’s letter frequencies, then reading the codes off the root-to-leaf paths.

David Huffman worked this out in 1951 as a 25-year-old student in an MIT information theory class taught by Robert Fano. Fano had given the class a choice: sit a final exam, or solve the open problem of finding the most efficient binary code for a set of symbols. Huffman picked the paper, expecting it would be less work than the exam. He spent months on it, tried and discarded several approaches, and was about to throw out his notes and start cramming for the final when the idea of building the code tree from the bottom up — merging the least-frequent symbols first, rather than splitting from the top down — came to him. What Fano hadn’t told the class was that he had worked on the same problem with Claude Shannon and hadn’t solved it: their approach, now called Shannon-Fano coding, builds the tree top-down and can produce provably suboptimal codes in cases where Huffman’s bottom-up method does not. Huffman’s student paper outdid his professor’s published technique, as recounted in the ACM’s memorial for Huffman and in the Mathematical Association of America’s account of the discovery. The original paper, “A Method for the Construction of Minimum-Redundancy Codes,” was published in the Proceedings of the IRE in September 1952.

Huffman coding’s limitation is that it can only assign a whole number of bits to each symbol, so it can’t do better than one bit per symbol even when a symbol’s true information content is a fraction of a bit — which happens whenever one symbol dominates a distribution. Later entropy coders close that gap, at the cost of complexity (see below).

Dictionary compression: LZ77

Huffman coding needs to know symbol frequencies in advance and only ever looks at single symbols. Dictionary compression instead looks for repeated sequences anywhere earlier in the data and replaces a repeat with a pointer to the earlier occurrence. Abraham Lempel and Jacob Ziv published the technique, now called LZ77, in 1977, using a “sliding window” of recently seen text as an implicit dictionary — no separate dictionary needs to be transmitted, because the decoder has already seen the same preceding data.

Running LZ77 over ABRACADABRA again: the first seven characters — A, B, R, A, C, A, D — have no sufficiently long match yet and are emitted as literals. At position 7, the four characters ABRA exactly match the four characters starting at position 0, seven characters back, so the encoder emits a back-reference (distance 7, length 4) instead of four more letters. The 11-character word becomes eight output symbols: seven literals plus one match.

LZ77 replacing the second “ABRA” in ABRACADABRA with a back-reference to the first.

LZ77 and its sibling LZ78 (1978) are the ancestors of most general-purpose compression in use today. Phil Katz combined an LZ77-family matcher with Huffman coding on the back-reference and literal streams to create DEFLATE in 1993, which underpins ZIP, gzip and PNG. A related variant, LZW (Lempel-Ziv-Welch), compresses GIF images — and was, for a period, a cautionary tale about software patents: Unisys, which had acquired the LZW patent through its 1986 merger with Sperry, began enforcing licensing fees against GIF software developers in January 1995, prompting part of the free-software community to develop PNG specifically as a patent-unencumbered alternative. The US patent expired on 20 June 2003, with counterpart patents in other countries expiring a year later.

Dictionary compression’s limitation mirrors RLE’s: it needs matches to exist within the window it searches, and short or unique inputs (a single sentence, a random key) yield no matches at all, so the “compressed” output can end up no smaller than the input, or even slightly larger once framing overhead is added.

Transform coding: the DCT and JPEG

Photographs don’t have the exact repeats that RLE and LZ77 look for, but they do have redundancy of a different kind: neighbouring pixels tend to be similar, and human vision is far less sensitive to fine, high-frequency detail than to broad shapes and gradients. JPEG, standardised in 1992 as ISO/IEC 10918, exploits this with the discrete cosine transform (DCT): it splits an image into 8×8-pixel blocks and converts each block from pixel values into a weighted sum of cosine wave patterns of increasing frequency. This doesn’t compress anything by itself — it’s a lossless change of representation — but it concentrates most of a typical block’s energy into the low-frequency coefficients in the top-left corner, leaving the high-frequency, fine-detail coefficients small.

The lossy step is quantisation: each coefficient is divided by a value from a fixed table and rounded, which is coarser for high-frequency coefficients since the eye barely notices when they’re gone. Running this on a real, smoothly shaded 8×8 patch (values from 60 to 160, transformed with the DCT, then divided by the standard JPEG luminance quantisation table published in Wallace’s 1991 description of the standard) leaves only 6 of the original 64 coefficients non-zero. A “zigzag” scan then reads the coefficients out in order of increasing frequency, so the long run of zeros at the end collapses to a single “end of block” marker, and Huffman coding compresses what’s left.

A real 8×8 pixel block transformed into DCT coefficients, then quantised until only 6 of 64 survive.

The DCT itself was developed by Nasir Ahmed, first as a proposal to the US National Science Foundation in 1972 that was rejected — one reviewer’s comment was that the idea seemed “too simple” — and then, with his PhD student T. Natarajan and colleague K.R. Rao at the University of Texas at Arlington, published as a working algorithm in Ahmed, Natarajan and Rao, “Discrete Cosine Transform,” IEEE Transactions on Computers, January 1974. It went on to become, in the JPEG committee’s hands two decades later, the most widely used transform in digital media.

Because quantisation throws information away, JPEG is lossy: decoded pixels are never bit-identical to the originals, and pushing the quantisation harder for a smaller file introduces visible blocking artefacts at the 8×8 boundaries. Text, line art and screenshots — the same content RLE handles well — compress badly under JPEG and are better served by a lossless format such as PNG.

Modern codecs: better entropy coding and motion

Two developments since the 1990s have mattered more than any single new “phase” of compression: better entropy coding, and prediction across time rather than just within a single block of data.

Huffman coding is optimal only when every symbol’s true probability happens to be a power of two — otherwise it wastes a fraction of a bit per symbol rounding up to the nearest whole bit. Arithmetic and range coding fix this by encoding an entire message as a single high-precision number, but historically that made them noticeably slower to decode than Huffman. In 2009, Jarek Duda proposed asymmetric numeral systems (ANS), an entropy coder that gets arithmetic coding’s near-optimal compression using only table lookups, shifts and additions — closer to Huffman’s decoding speed. Yann Collet’s tANS implementation, released around 2013 as FSE (“finite state entropy”), became the entropy stage of Zstandard (zstd), the general-purpose compressor Collet built at Facebook, open-sourced in August 2016 and standardised as RFC 8878 in February 2021. On the standard Silesia benchmark corpus, zstd at its default level compresses to roughly the same ratio as zlib/gzip while compressing around five times faster and decompressing around four times faster, according to the project’s own published benchmarks. Google’s Brotli, released in 2013 for web font compression and generalised for HTTP in 2015, takes a different route to a similar goal: it pairs LZ77 matching and Huffman coding with a built-in static dictionary of roughly 13,500 common words, phrases and markup fragments drawn from the web, which helps most on small files where there isn’t enough repeated content within the file itself to build a useful dictionary from scratch. Brotli at its higher compression levels typically beats zstd on ratio; zstd is typically faster — in one 2024 comparison across the top 10,000 websites, Brotli’s maximum setting produced files about 19% smaller than gzip against zstd’s roughly 14%, while zstd compressed noticeably faster at comparable settings, as measured by web performance engineer Paul Calvano.

The other major development applies to video rather than static files: most of the data in a video is unchanged from one frame to the next, so codecs since the 1990s encode most frames as a prediction from a previous frame plus a small correction, rather than as a fresh image. For each block in the current frame, the encoder searches nearby frames for a block of pixels that closely matches it, records the displacement as a motion vector, and encodes only the difference — the residual — between the predicted block and the actual one. That residual is typically small and is itself compressed with a DCT-like transform and entropy coding, reusing the same machinery JPEG uses for still images.

A block in the current frame predicted from a matching block in the previous frame; only the motion vector and residual are encoded.

AV1, the royalty-free codec released by the Alliance for Open Media in 2018, extends this considerably: it can reference up to six previous frames rather than one, model non-translational motion such as rotation and zoom through warped-motion compensation, and blend predictions from neighbouring blocks to smooth the edges between them. The Alliance’s own technical overview reports AV1 achieving more than a 30% bit-rate reduction compared with its predecessor, VP9, at equivalent decoded quality.

Compression research hasn’t stopped iterating on the general-purpose side either. In October 2025, Meta released OpenZL, which represents a compression pipeline as a graph of format-aware transformations — rearranging structured data, such as columns of a table or fields of a log line, before handing it to a general compressor — while still decoding any file with one universal decoder, because the graph describing how it was built travels with the compressed data. On one of Meta’s own benchmark datasets, OpenZL reached roughly 1.6 times the compression ratio of zstd at a comparable decompression speed. It’s a reminder that “general-purpose” and “format-specific” compression have mostly been a trade-off, not a solved problem, and the frontier is still moving.

Where each technique falls short

Run-length encoding only helps when the data actually contains long runs; photographic or otherwise noisy data can come out larger, not smaller.
Huffman coding is limited to whole-bit code lengths per symbol, so it can’t reach the theoretical entropy limit when one symbol dominates; it also needs the symbol frequencies computed or transmitted up front.
Dictionary compression needs matches within its search window; very short or high-entropy inputs (already-compressed or encrypted data, for instance) yield few or no matches and can grow slightly under the framing overhead.
DCT-based image compression is inherently lossy — decoded pixels are never identical to the source — and performs badly on sharp-edged content like text or line art, which is why screenshots are usually PNG rather than JPEG.
Motion-compensated video coding assumes redundancy between nearby frames; content with constant, unpredictable change (heavy film grain, fast strobing) yields poor predictions and forces the encoder back toward full-frame, less efficient coding.