Same information, fewer bits, nothing lost. It sounds like cheating. It is arithmetic.
No Runestone reading. The book doesn't cover compression — everything you need is on this page.
Still in Bits, and finally paying a debt. In 1.5 you computed that a photo needs 36 MB and then found one on your phone taking 3 MB. That gap has been sitting there for three lessons. Today you get the word for it — and today's half of the answer is the half where nothing is lost.
But before you relax — watch this claim carefully, because it is the kind that should make you suspicious. Somebody is telling you that a thing can be made twelve times smaller and stay the same. Both of those cannot be fully true at once, and by the end of this page you'll be able to say exactly which part gives, and prove that no amount of cleverness avoids it.
Data compression is reducing the number of bits needed to store or send something. It splits into two families, and telling them apart is the actual testable skill:
| Family | Promise | Can you get the original back? |
|---|---|---|
| Lossless | Fewer bits, zero information lost | Yes — bit for bit, perfectly, always |
| Lossy | Far fewer bits, some information discarded | No — what was thrown away is gone |
Today is lossless only. The rule to hold onto: lossless compression is reversible. Compress, then decompress, and you have the identical original — not "close enough," identical. That's what ZIP does to your files, and it's why a compressed essay isn't missing any words when it comes back.
So where do the savings come from, if nothing is lost? From repetition. Real data repeats itself constantly, and repetition means you are storing the same thing over and over. Say it once, then say how many times.
Take a row of black-and-white pixels. Instead of writing every pixel, write how long each run of identical pixels is:
original — 24 pixels, 1 bit each = 24 bits 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 run-length encoded — 4 runs 8 white, 4 black, 12 white → 8, 4, 12 colours alternate, so you only store the lengths.
Three numbers instead of twenty-four pixels, and you can rebuild the original exactly from those three numbers. Nothing was approximated. That is lossless compression, complete.
Text doesn't have long runs — aaaaa is rare in English. But phrases
repeat constantly. So instead of runs, build a dictionary: find the repeated
chunks, give each a short code, and store the dictionary once alongside the coded text.
original banana banana banana orange banana orange dictionary coded text ~0 = banana ~0 ~0 ~0 ~1 ~0 ~1 ~1 = orange
Same trick, same guarantee: the dictionary lets you put every original character back exactly. This is roughly what ZIP, PNG, and GIF do — far more cleverly, but the idea is this one.
Lossless compression works by exploiting repetition, so how well it does depends entirely on how repetitive the data is. Pixel art with big flat areas compresses enormously. A photograph does not — real photos are full of tiny sensor noise and gradual shading, so almost no two neighbouring pixels are exactly equal. Lossless formats rarely manage much better than about 2:1 on a photograph.
Which means lossless cannot explain the hook. 36 MB down to 3 MB is twelve to one, and no reversible method gets there on a photo. So the honest answer is: your phone did not use a lossless method. It threw something away, deliberately, and bet you wouldn't notice.
That's 1.9, and now you know exactly what question you're walking in with: what did it throw away, and who decides whether that's acceptable?
Grid paper, 8×8. Draw a simple shape by filling squares. Now run-length encode it by hand: read left to right, top to bottom, and write down the run lengths, starting with white.
Hand only the list of numbers to a partner. They redraw it on a blank grid. Compare to your original. If it is not identical, one of you made an arithmetic mistake — because the method itself cannot lose anything. That is the whole point of the word "lossless."
Now do it at speed. Click squares to draw. The encoding, the bit count, and the ratio update as you go.
Press "checkerboard." Then look at the ratio. The compressed version is many times larger than the original, because every single run is one pixel long and each one costs a whole byte to say so. Nothing went wrong. That result is not a bug in the method, and in a moment you'll see it's not avoidable either.
Type anything. Repeated words of four or more letters get a short code. Then watch it decompress back to exactly what you typed.
Try a sentence with no repeated words at all. The dictionary comes out empty, nothing is saved, and you have just discovered the limit of the method by pushing on it — which is the right way to learn where a tool stops working.
You just used both of these. Now they get names.
Five questions in AP format. Pick an answer to see feedback immediately.
Every so often a company announces a breakthrough: a lossless compressor that shrinks any file dramatically — any file at all, run it again and again, squeeze a movie onto a floppy disk. Investors have put real money into this more than once.
It is impossible, and you already have the mathematics to prove it. From 1.1: there are exactly 2n different files that are n bits long. Now count every file shorter than n bits — all the 1-bit files, 2-bit files, and so on:
20 + 21 + … + 2n−1 = 2n − 1
One fewer slot than there are files to put in them. So if a method shrank every n-bit file, at least two different files would have to compress to the same thing — and then decompressing is a guess, not a reconstruction. That breaks the one promise lossless makes. Therefore every lossless method must make some inputs bigger. Your checkerboard was not bad luck; it was this theorem arriving on schedule.
Real compression is honest about this. It bets on the data people actually have — text, photos, and audio, which repeat — and accepts losing on data that doesn't. "Works well on typical inputs" is a real engineering claim. "Works on everything" is a claim you can now refute with counting, which is a good demonstration that the boring arithmetic at the start of this unit was never just arithmetic.