What if we tried to stuff information into space that does not exist?
Imagine I hand you every possible message that can be written with exactly 1,000 binary digits. Then I give you a smaller box and make one unreasonable demand: put every one of those messages into fewer than 1,000 bits, lose nothing, and guarantee that I can recover each original perfectly.
It sounds like a problem for a clever programmer. Perhaps we need a better algorithm. Perhaps today’s compressors simply have not discovered the right trick.
But the difficulty is deeper. There are more possible 1,000-bit messages than there are shorter binary labels available to name them. If every original must have its own reversible compressed representation, eventually we run out of shorter labels. No amount of programming cleverness manufactures missing possibilities.
Quick Read
- Lossless compression does not magically create storage space.
- It works when data contains regularity, repetition, bias or other exploitable structure.
- A lossless compressor cannot make every possible input shorter.
- Some messages are already close to their shortest useful description.
- Random-looking data is difficult to compress because prediction and repetition are scarce.
- Entropy gives us a way to reason about the average information produced by a source.
- A good compressor therefore asks a more intelligent question than “How do I shrink this?” It asks, “What structure is present that I do not need to describe independently every time?”
The One-Sentence Answer
Compression makes information smaller only when the original contains structure that permits a shorter description; when no such exploitable structure exists, mathematics eventually refuses the bargain.
Start With a Smaller Impossible Box
We can see the problem without 1,000 bits. Take every possible three-bit message:
000 001 010 011 100 101 110 111
There are eight possibilities. Now demand that all eight be represented using at most two bits. Two-bit messages give us only four fixed-length possibilities: 00, 01, 10 and 11. Even if we also permit shorter strings, there are still not enough distinct short descriptions to give every three-bit original a unique shorter home under the usual uniquely decodable requirements.
Something must give. Some inputs may become shorter, but other inputs must stay the same length or become longer. Otherwise two different originals eventually receive the same compressed description, and the decoder cannot know which one to reconstruct.
This is the humble pigeonhole principle wearing an information-theory coat: too many pigeons, too few holes.
So Why Does Compression Work So Often?
Because real data is usually not an equally likely parade of every imaginable bit pattern.
A page of English contains spaces, repeated letters, common words, grammatical constraints and predictable sequences. A photograph contains neighbouring pixels that are often related. A recording contains patterns across time and frequency. A spreadsheet may contain repeated labels, similar values and empty regions. Software contains recurring instructions and structures.
Compression enters through those inequalities.
If one symbol occurs much more often than another, perhaps it deserves a shorter code. If a phrase repeats, perhaps we can store it once and point back to it. If the next value is usually close to the previous value, perhaps we store the difference rather than the whole value. If a block resembles something already seen, perhaps we describe the change.
The compressor is not squeezing bits physically closer together. It is replacing an unnecessarily literal description with a more economical one.
Compression Is Really About Unequal Surprise
Suppose I ask you to guess tomorrow’s sunrise direction in Singapore. “East” is not very surprising. Suppose instead I ask for the exact sequence of results from 100 fair coin tosses. Any particular sequence is difficult to predict in advance.
Information theory gives this intuition mathematical teeth. Claude Shannon’s framework connects information with uncertainty and gives us entropy: a measure of the average uncertainty of a source under a probability model.
If a source is strongly biased or predictable, an efficient code can exploit that structure. If outcomes are genuinely equiprobable and independent, there is less statistical redundancy to remove. For lossless coding over long sequences, source-coding results tell us that entropy establishes the fundamental average-rate boundary around which efficient codes operate.
This does not mean every individual message has length exactly equal to an entropy number. Entropy describes a source and its average behaviour. That distinction matters. Compression discussions become muddled when we confuse a property of a probabilistic source with a promise about every individual file.
The Strange Case of Randomness
Here is a 40-character string:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
You immediately see a shorter description: “A repeated 40 times.”
Now imagine a long sequence whose symbols behave like independent fair random choices. We may still get accidental local repetitions, but there is no dependable compact rule from which the entire particular sequence follows. The literal data may already be doing most of the descriptive work.
This leads toward another family of ideas associated with algorithmic information theory. Instead of asking only about probabilities, we can ask about descriptions: how short can a program or effective rule be that reproduces this exact object?
A highly regular string may have a tiny generating description. Many strings do not. Indeed, by counting alone, most sufficiently long strings cannot all possess substantially shorter unique descriptions. There simply are not enough short descriptions to go around.
But My Compressor Sometimes Makes a File Bigger
Exactly. That is not necessarily a failure.
A compressed file may need headers, dictionaries, block information, checksums or other metadata. If the original is tiny, already compressed, encrypted or statistically unhelpful, those additions can outweigh any redundancy the compressor removes.
Try repeatedly compressing a well-compressed archive and you eventually encounter diminishing returns. The first compressor has already harvested much of the easy structure visible to its model. The next compressor does not receive the rich original; it receives an output deliberately transformed to be closer to an efficient coded representation.
This is why “compress it again” is not an infinite staircase down to one byte.
What Encryption Teaches Us
Good encryption aims, among other things, to conceal exploitable patterns from an observer without the key. Consequently encrypted data often looks statistically unhelpful to ordinary compressors. That is why systems normally compress before encrypting when both operations are appropriate.
The lesson is broader than cybersecurity. Compressibility depends not merely on what an object “really is” but on what regularities are accessible to the compressor’s representation and model.
A pattern nobody can detect is not useful to that compressor.
There Is No Universal Miracle Compressor
Every few years some extraordinary claim appears: a method that supposedly makes any data dramatically smaller, repeatedly, with perfect reconstruction.
The counting argument is a useful first defence.
Ask: Is the claim really lossless? Does it work on every possible input? Is external information required? Is the decoder carrying a huge table or model? Is the original recoverable without contacting some remote store? Are only specially selected files being demonstrated? Does the method sometimes expand data? Has some information quietly moved outside the measured payload?
Often the miracle disappears when we account for the entire system.
A Book Can Be Smaller Than Its Meaning
Now the idea becomes interesting beyond computers.
Consider the word “photosynthesis.” Eleven letters can activate an enormous structure in the mind of a biologist: chloroplasts, pigments, electron transport, carbon fixation, energy transfer, ecological consequences and years of accumulated knowledge.
Did eleven letters contain all of that knowledge?
No. The word acted partly as an address into knowledge the receiver already possessed.
This distinction will matter throughout our deeper exploration of compression. Sometimes information becomes smaller because redundancy is removed. Sometimes it becomes smaller because the receiver owns a dictionary. Sometimes the missing material is stored elsewhere. Sometimes reconstruction consumes time. Sometimes we accept loss.
If we measure only the transmitted object, we may mistake relocated cost for vanished cost.
Compression and Human Learning
Students do something remarkably similar.
A beginner solving an algebra problem may need to write every intermediate step. An experienced student can sometimes write less because several transformations have become stable mental chunks. A novice reading “mitosis” may need a paragraph of explanation. A biology student may unfold an entire process from the single term.
But this creates a teaching danger. Experts can mistake their compressed representation for the learner’s representation.
“Just factorise it.”
Two words for the teacher. Perhaps six decisions for the student.
Good teaching knows when to decompress. It restores the intermediate distinctions that expertise has learned to hide.
Primary School: See the Repetition
For a younger learner, compression begins with a simple insight: repeated information does not always need to be written repeatedly.
Ask a child which is easier to communicate:
- red, red, red, red, red, red, red, red;
- eight reds.
Then ask what would happen if the sequence were red, blue, green, yellow, black, white, orange, purple. The convenient shortcut has disappeared. The child has discovered the central idea without needing the word entropy: structure creates opportunities for shorter descriptions.
Secondary School: Ask What the Shortcut Assumes
At Secondary level, we can add a harder question. If I write “AB × 500,” what must the receiver know?
They must understand the symbols, the multiplication-like notation and the intended reconstruction rule. The shorter message works because sender and receiver share conventions.
Now compression becomes a systems question, not merely a file-size question.
JC and Beyond: Distinguish Three Different Questions
- Statistical question: What uncertainty does the source have, and what average coding rate is achievable under the model?
- Individual-description question: Does this particular object possess a substantially shorter effective description?
- Engineering question: Given real constraints on speed, memory, compatibility and error tolerance, which representation is actually useful?
These questions overlap, but they are not identical. Keeping them separate prevents a great deal of confusion.
A Useful Test: Where Did the Information Go?
Whenever something seems astonishingly compressed, ask five questions:
- What patterns or probabilities were exploited?
- What must the decoder already know?
- Is any information stored outside the measured object?
- How much computation or time is required to reconstruct it?
- Is reconstruction exact, or has some information been discarded?
Those questions turn “compression” from a magic trick back into an accountable transformation.