Data Compression

Abstract

Most photos, songs, videos and web pages reach their users compressed. Data compression, removing redundancy so that information takes less space, became a science with Claude Shannon’s 1948 information theory, which set a hard limit on how far lossless compression can go. In 1951 the MIT student David Huffman found an optimal code as a term-paper alternative to a final exam. Abraham Lempel and Jacob Ziv made compression adaptive to any data in 1977 and 1978, and their methods, through Phil Katz’s ZIP, gzip and PNG, became the most widely used compressors. Lossy formats that discard what people cannot see or hear, JPEG for images (1992) and MP3 for audio, made digital media practical over slow connections. Patents shaped the field almost as much as mathematics: Unisys’s claims on LZW led to PNG, patents kept arithmetic coding out of use for decades, and royalty disputes over video codecs produced the royalty-free AV1. In 2023 researchers showed that large language models are themselves powerful general-purpose compressors.

The Limit: Shannon and Entropy

Compression is older than computers. Morse code gave the common letter E a single dot and the rare Q a long sequence, and telegraph companies sold codebooks that replaced whole phrases with single words to save on charges. It became a mathematical subject in 1948, when Claude Shannon published “A Mathematical Theory of Communication” (see Claude Shannon and Information Theory). Shannon defined the entropy of a source of messages: the average number of bits per symbol that its unpredictability requires. His source coding theorem proved that no lossless code can use fewer bits on average than the entropy, and that codes can come arbitrarily close to it.

That divided the field. Lossless compression removes only redundancy, and the original is recovered bit for bit; it is required for text, programs and most data. Lossy compression also discards information the recipient will not miss, and can therefore go far below the entropy of the raw signal, because what is reconstructed is a different, slightly worse signal. Photographs, music and video use lossy methods.

Huffman’s Exam Trick

A Huffman code tree for a short text. Frequent symbols sit near the root and get short codes, rare ones get long codes. Image: Meteficha, public domain, via Wikimedia Commons.

In 1951 David Huffman was a graduate student at MIT in an information theory course taught by Robert Fano. Fano offered the class a choice: take the final exam, or write a term paper solving a problem he set. The problem was to find the most efficient way to assign variable-length binary codes to symbols with known frequencies. Shannon and Fano had a good method, now called Shannon–Fano coding, which built the code by splitting the symbols top-down into groups of nearly equal probability, but it was not always optimal.

Huffman was about to give up and study for the exam when he found the answer: build the code tree from the bottom up, repeatedly merging the two least frequent symbols or groups into one node. He published “A Method for the Construction of Minimum-Redundancy Codes” in 1952. Huffman coding is optimal among codes that assign a whole number of bits to each symbol, and because no code word is the prefix of another, a stream of them can be decoded without separators. Seventy years later it is still the final stage of JPEG, MP3 and the DEFLATE format behind ZIP and PNG.

Fax and Run Lengths

The first mass-market use of compression was the fax machine (see The Fax Machine). A scanned page is mostly white, with runs of black where there is text. The CCITT’s Group 3 standard of 1980 encoded the lengths of runs of white and black pixels with fixed Huffman tables, so that a page could cross a telephone line in about a minute instead of six. Run-length coding, Huffman tables and the idea that a standard can fix a code in advance for a known kind of data were all in place before personal computers spread.

Lempel and Ziv

Abraham Lempel at the Technion, where he and Jacob Ziv developed the LZ77 and LZ78 algorithms. Image: Staelin, CC BY 3.0, via Wikimedia Commons.

Huffman coding needs to know the symbol frequencies in advance, and it treats each symbol separately. The method that made compression work on any data, without prior knowledge, came from Abraham Lempel and Jacob Ziv at the Technion in Haifa. Their 1977 paper, “A Universal Algorithm for Sequential Data Compression”, described what is now called LZ77: as the compressor moves through the data it looks back over a window of recent text, and when the next few bytes repeat something it has already seen, it writes a short reference (“go back 2,000 bytes and copy 12”) instead of the bytes. LZ78 (1978) built an explicit dictionary of phrases instead of a sliding window. Both learn the structure of the data as they go, and they proved that, for long enough inputs, the methods approach the entropy of the source.

The LZ family became the basis of general-purpose compression.

LZW. In 1984 Terry Welch of Sperry published a fast variant of LZ78. It became the Unix compress utility and the compression inside CompuServe’s GIF image format (1987) and TIFF.
DEFLATE. Phil Katz combined LZ77 with Huffman coding for version 2 of his PKZIP program, released in 1993. Jean-loup Gailly and Mark Adler wrote gzip (released 31 October 1992) and the zlib library (1995) on the same method. DEFLATE became the format of .zip files, gzip, PNG images and HTTP compression, probably the most widely used compression algorithm ever.

Lempel and Ziv received the IEEE Richard W. Hamming Medal for the work, and Ziv the IEEE Medal of Honor in 2021.

The GIF Tax and PNG

Welch’s employer, which became Unisys, held a patent on LZW. For years few people noticed that GIF images used it. At the end of December 1994 CompuServe and Unisys announced that developers of software reading or writing GIF files would have to pay royalties: 1.5 percent of a program’s price or 15 cents a copy, whichever was greater. Web developers called it the “GIF tax.”

Within weeks a group of programmers on Usenet began designing a replacement, built on the patent-free DEFLATE. The Portable Network Graphics format (PNG) became a World Wide Web Consortium recommendation on 1 October 1996. The US LZW patent expired on 20 June 2003 and the last foreign counterparts in 2004, by which time PNG had become the web’s standard format for lossless images, while GIF survived mainly for short animations.

Throwing Information Away

Lossy compression rests on the limits of human perception.

JPEG, named after the Joint Photographic Experts Group approved as ITU-T recommendation T.81 in 1992 and published as ISO/IEC 10918-1 in 1994, divides an image into 8-by-8 pixel blocks, converts each into frequency components with the discrete cosine transform, quantizes away much of the fine detail the eye barely notices, and Huffman-codes the result. A tenfold reduction with no visible loss is routine. It became the most widely used image format in the world.

MP3, formally MPEG-1 Audio Layer III, did the same for sound. It was developed largely at Germany’s Fraunhofer Institute by a team including Karlheinz Brandenburg and standardized by ISO’s MPEG committee in the early 1990s. A psychoacoustic model calculates which sounds are masked by louder nearby tones or fall below the threshold of hearing, and the encoder spends no bits on them. A song shrinks about tenfold, small enough to download over the modems of the late 1990s, which made file sharing, the iPod and eventually streaming possible.

The same transform-and-prediction approach scaled up to video. MPEG-2 carried digital television and DVDs, and H.264 (2003) carried most online video of the 2000s and 2010s. Video codecs exploit redundancy between frames, since most of the picture changes little from one frame to the next, by sending motion vectors and differences instead of whole images.

Newer Lossless Methods

General-purpose compression kept improving. bzip2 (1996), by Julian Seward, used the Burrows–Wheeler transform, published by Michael Burrows and David Wheeler in 1994, which rearranges a block of text so that similar contexts sit together and become easy to compress. Google’s Brotli (2015) was designed for web content and adopted by browsers. Zstandard, written by Yann Collet at Facebook and released on 31 August 2016, combined LZ77-style matching with modern entropy coding to compress about as well as zlib or better at several times the speed, and spread into Linux kernels, databases, package managers and network protocols.

Compression and Prediction

Compression and prediction are the same problem: a model that predicts the next symbol well can encode it in few bits. In August 2006 the AI researcher Marcus Hutter offered a prize, now 500,000 euros, for compressing a fixed extract of English Wikipedia, arguing that better compression of human knowledge requires something like understanding. In September 2023 researchers at DeepMind published “Language Modeling Is Compression”, showing that a large language model used with arithmetic coding was a strong general-purpose compressor: their 70-billion-parameter Chinchilla model, trained mainly on text, compressed image patches to 43.4 percent of their size, better than PNG’s 58.5 percent, and speech samples to 16.4 percent, better than the audio format FLAC’s 30.3 percent.

Dead End

The clearest dead end in compression was legal rather than technical.

Arithmetic coding, developed from the late 1970s, encodes a whole message as a single number in an interval and can therefore spend fractional bits per symbol, coming closer to Shannon’s limit than Huffman coding, especially when one symbol is very common. It should have replaced Huffman coding in most formats. For two decades it did not, because IBM and others held a thicket of patents on it. The original JPEG standard of 1992 included an arithmetic-coding mode that gave smaller files, and almost no software implemented it because of the patent risk; Huffman coding stayed the default. Arithmetic coding came into general use only as the patents expired. Its modern successor, asymmetric numeral systems (ANS), published by Jarosław Duda in 2009 and deliberately placed in the public domain, gives similar efficiency at higher speed and is used in Zstandard, JPEG XL and other recent formats.

Video repeated the story. HEVC (H.265, 2013) compressed about twice as well as H.264, but its patents were split among several competing licensing pools with uncertain terms, and many web companies avoided it. On 1 September 2015 Amazon, Cisco, Google, Intel, Microsoft, Mozilla and Netflix announced the Alliance for Open Media to build a royalty-free codec; its AV1 was published in March 2018, with every member committing to license its essential patents free of charge. Royalty-free did not mean free of disputes: in March 2026 Dolby sued Snap in Delaware, claiming that AV1 uses patented technology that is also part of HEVC. Even image formats were not spared politics. Google removed support for the new JPEG XL format from Chrome in October 2022, citing low interest, and reversed the decision in late 2025; Chrome 145 shipped a new decoder in February 2026, at first behind a settings flag.