Data Compression

Data compression is the set of techniques that reduce the number of bits needed to represent information. It exploits redundancy —repeating patterns, some symbols more frequent than others— to describe the same content in less space, so that a file takes up less room on disk or travels faster across a network. It is an invisible, ubiquitous technology, underpinning everything from a ZIP archive to the video you stream.

The whole discipline turns on one fundamental decision: whether recovering the data must return exactly the original, or whether a faithful-enough copy will do. That choice separates the two great territories of compression.

Lossless versus lossy

Lossless compression reconstructs the original bit for bit, with no alteration whatsoever. It is mandatory whenever every symbol matters: text, source code, spreadsheets or executable files. Its classic methods combine two complementary ideas. Huffman coding, proposed by David Huffman in 1952, assigns shorter codes to more frequent symbols; the LZ77 and LZ78 algorithms, by Abraham Lempel and Jacob Ziv, replace repeated sequences with references to earlier occurrences. The widespread DEFLATE —the heart of gzip, the ZIP format and PNG images— chains the two together. Arithmetic coding is an alternative that tends to come closer to the theoretical optimum.

Lossy compression deliberately discards the least perceptible information in exchange for far higher ratios. It is the basis of JPEG for images, MP3 and AAC for audio and modern video codecs: they exploit the limits of the human eye and ear to throw away what we would barely notice. The original never returns intact, yet the difference is meant to be invisible or inaudible.

The entropy limit

How far can we compress without losing anything? Claude Shannon answered in 1948, when he founded information theory. His source-coding theorem states that no lossless technique can drop, on average, below the entropy of the source: the measure of its uncertainty or information content, expressed in bits per symbol. Entropy is the unbreachable floor; good algorithms can only approach it. This limit belongs to information theory, which deserves an entry of its own.

Compression and AI: autoencoders and compression ≈ prediction

Machine learning speaks to compression in two directions. First, autoencoders are neural networks that learn to compress: an encoder squeezes the data into a compact representation (the «bottleneck») and a decoder rebuilds it. On this idea rests neural, or learned, compression —work such as that of Johannes Ballé and colleagues jointly optimizes size and fidelity— which already rivals traditional image and video codecs.

Second, there is a deeper equivalence: compressing well is predicting well. A model that anticipates the next symbol accurately lets you encode it with fewer bits; Shannon glimpsed this, and arithmetic coding turns any predictor into a compressor. Researchers at Google DeepMind and Meta formalized it in 2023 in «Language Modeling Is Compression», showing that large language models —trained to predict the next token— are first-rate general-purpose compressors. Compressing and modeling the world are, at bottom, the same task.