How Does Data Compression Work? Removing What You Can Predict
By the BrainSnail editorial team. How these articles are written and checked, and how to tell us when one is wrong.
Compression works because real data is predictable. Text repeats words, photographs have areas of similar colour, audio changes smoothly, and anything predictable can be described more briefly than it can be listed. The two families of technique differ in one decision: whether the original must be recovered exactly, or whether it is enough to recover something a person cannot tell apart.
Lossless compression
Lossless methods reconstruct the original bit for bit, which is required for text, code, spreadsheets and archives where a single altered character matters. Two ideas do most of the work. Entropy coding assigns shorter codes to more frequent symbols and longer codes to rare ones, which is what Huffman coding does and what Morse code did by hand, giving E a single dot because it is common. Dictionary coding replaces repeated sequences with references to earlier occurrences, so a document that has already used a phrase can refer back to it rather than repeating it, which is the basis of the family of algorithms behind most general-purpose compressors. Modern compressors combine both, along with modelling that predicts each symbol from its context and encodes only the surprise. Formats built this way include the common archive formats, the lossless image format used for graphics with sharp edges, and the compression built into web servers and file systems.
Why it cannot always work
There is a hard limit and it is worth stating precisely. Claude Shannon's information theory defines entropy as the average amount of information per symbol given a statistical model of the source, and no lossless method can compress below that on average. A simple counting argument shows something stronger: since compression must be reversible, the mapping from inputs to outputs is one to one, so if some files get shorter then others must get longer, and no algorithm can compress every possible input. Random data is therefore incompressible, which is why an already compressed file barely shrinks when compressed again and why claims of universal compression are always wrong. What makes compression useful is not that data is generally compressible but that the data people actually store is highly structured, so the inputs that occur in practice are a tiny and very predictable subset of all possible inputs.
Lossy compression
Lossy methods discard information permanently, choosing what to discard based on models of human perception, and achieve compression ratios an order of magnitude beyond lossless:
- •Image compression transforms blocks of pixels into frequency components, keeping the low frequencies that carry overall shape and discarding fine high-frequency detail the eye is less sensitive to, which is what produces the blocky artefacts visible in heavily compressed photographs
- •Colour subsampling exploits the eye's much lower resolution for colour than for brightness, storing colour information at reduced resolution
- •Audio compression uses psychoacoustic masking, since a loud sound hides quieter sounds at nearby frequencies and immediately after it, so those masked components can be removed without being noticed
- •Video compression adds the largest saving of all by encoding differences between frames rather than whole frames, since consecutive frames are mostly identical, and by describing motion so a moving object is reused rather than re-encoded
- •Quality settings control how aggressively information is discarded, trading file size against visible or audible degradation
- •Generation loss accumulates, since repeatedly decoding and re-encoding a lossy file degrades it further each time, which is why archives should be kept in lossless form
Why it matters more than it seems
Compression is the reason streaming media exists, since uncompressed video would require bandwidth far beyond what networks deliver, and the advances in codec efficiency over three decades have repeatedly made new services viable rather than merely cheaper. It shapes what is stored, since the decision about what to discard is a decision about what is considered inessential, made by engineers and encoded in standards used billions of times a day. It has legal and commercial weight, since codec patents have been the subject of prolonged licensing disputes and the push for royalty-free alternatives is a significant industry battle. It has a strange theoretical connection to intelligence, since compressing data well requires predicting it well, and the argument that prediction and understanding are closely related underlies both a long-running compression prize for text and a substantial part of how modern language models are described. And it fails visibly in ways that matter, since heavy compression of faces has produced legible artefacts that have caused problems in evidential imagery.
The takeaway
Compression exploits predictability, using shorter codes for frequent symbols and references for repeated sequences. No lossless method can compress every input, since reversibility means shortening some files lengthens others, and Shannon's entropy sets the floor. Lossy methods discard information based on models of perception, removing fine detail the eye ignores, sounds masked by louder ones and the parts of a video frame identical to the last, which is why streaming is possible at all.