When you send a photo on WhatsApp, you compress dozens of megabytes until they fit into just a few. When a web server serves you a page, it shrinks it with Brotli before sending it over the network. Compression is everywhere and yet we almost never see it work. Behind it there is no trick: only very concrete mathematics refined over decades.
Every file has too much information
The starting idea is almost philosophical: a file, at its core, is a sequence of bits, and most sequences contain redundancy — information that repeats or can be guessed. An email from a friend is full of common words, spaces and predictable structures. A photo of a blue sky has millions of nearly identical pixels. Compression means removing that redundancy and keeping only the essential part.
Claude Shannon formalised this in 1948 with information theory. He defined the entropy of a message: the minimum number of bits that, on average, are needed to represent each symbol. The more predictable a message, the lower its entropy and the more it can be compressed. Spanish text has an entropy of around 4 bits per character, even though each character occupies 8: there is room to halve it, and even more with models that capture context.
Two families of methods
There are two big families. Lossless compression reconstructs the original file bit by bit: it is what ZIP, PNG, executables or your disk use. Lossy compression discards information that the eye or ear does not notice: that is the world of JPEG, MP3 or video. Here we focus on the first one, the one that works its magic on data that must stay exact.
Inside lossless compression two ideas coexist and are almost always combined: encoding symbols with fewer bits and finding repetitions in blocks of data.
Statistical coding: the Huffman trick
Huffman coding (1952) is the perfect example of the first idea. If the letter “e” appears 13% of the time and “w” only 0.1%, it is a waste to give both 8 bits. Huffman assigns variable-length codes: few bits to frequent symbols and many to rare ones.
The elegant part is that those codes are prefix-free: no code is the beginning of another. That way the decoder needs no separators and can read the bit stream without ambiguity. Huffman builds the optimal set of codes with a binary tree, always joining the two least probable symbols. More powerful variants, such as arithmetic coding or the FSE (Finite State Entropy) used by Zstandard, squeeze out a bit more by representing fractions of a bit rather than whole bits.
Repetitions: the LZ77 sliding window
The second idea attacks another source of redundancy: blocks that repeat. That was the revolution of Abraham Lempel and Jacob Ziv, who published LZ77 in 1977, the basis of almost all modern file compression. Instead of looking for words, the algorithm keeps a sliding window: the part of the file already read.
Every time it finds a sequence that already appeared in that window, it replaces it with a reference of three numbers: how far to go back (distance), how many characters to copy (length) and the next new symbol. So a phrase repeated a thousand times occupies only three numbers the second time around. LZ77 gave rise to LZ78 and LZW, the algorithm behind GIF (and a famous patent war).
DEFLATE: the marriage that changed everything
The most famous combination is DEFLATE (Phil Katz, 1993): it first applies LZ77 to remove repetitions and then Huffman to encode the result in few bits. It is the algorithm behind ZIP, gzip and the PNG image format. That is why text or flat backgrounds compress so well in a PNG: DEFLATE finds both the pixel repetitions and the cheapest way to encode them.
The modern ones: zstd and Brotli
In recent years far faster compressors appeared without losing ratio. Zstandard (zstd, Facebook/Meta, 2016) uses FSE and a very long sliding window, and can work in streaming, compressing data that has not finished arriving yet. Brotli (Google, 2013, used over HTTP) goes one step further: it defines a static dictionary of words in several languages and combines LZ77 with context modelling, so a repetitive web page shrinks enormously.
That is why web servers negotiate with your browser which compressor to use through the Accept-Encoding header: if the browser understands br (Brotli), it receives less data; otherwise it falls back to gzip. Fewer bytes over the wire means pages load faster, especially on mobile.
The limit nobody can bypass
Compression has a ceiling. You cannot compress what is already random: if a file has no redundancy left, its entropy is maximal and any attempt will leave it the same size or larger. Compressing an already compressed ZIP usually achieves nothing, and compressing encrypted data (which looks like noise) is outright counterproductive. That limit is not a flaw of the algorithms: it is a mathematical property of information.
Next time a file “shrinks”, remember that what you are watching is redundancy disappearing under sliding windows and Huffman trees. No magic: just mathematics that have been optimising themselves for eighty years.
