How does compression work

Cut down repetition

In the last lesson we saw how keeping data close makes reading fast. Making data smaller speeds things up too: small data takes less room to store and less time to send over a network. A computer holds all information as 0s and 1s, or bits, so if the same information can be written with fewer bits, that is a gain.
The easiest method is to cut down repetition. When the same letter runs on and on, instead of writing out every one, you note only which letter repeats and how many times. The four letters AAAA become "A four times."

Tap a repeated run. The row of letters shrinks into which letter and how many times, and the total length gets shorter.

Shrink every run, and the original, twelve cells long, becomes nine. Not a single letter was thrown away; all that changed is that you noted which letter and how many times. A run of only three letters, though, takes the same number of cells even when shortened, so there is no gain. The longer the run, the more it shrinks.
This approach is called run-length encoding, and it suits data with long runs, such as a picture with large areas of a single color. But if the same letters are not side by side and the same pieces are instead scattered here and there, this method is powerless. How do you shrink scattered repetition?

Give frequent pieces short codes

Scattered repetition can be cut too. Find long pieces that come up often, assign each one a short code, and write the code wherever that piece appears. Which code stands for which piece is noted separately in a table.
The more often a piece appears, the more replacements there are, and so the bigger the effect. The table has to be stored as well, so very short data can actually grow. Many of the compression programs in real use are built on this kind of method, which points back to pieces that have already appeared.

Tap a frequent piece to give it a short code. Every place that piece appears turns into the code, and the total length drops.

With codes given to the two pieces, eighteen cells shrank to eight. Cutting repetition and giving short codes come from the same idea in the end: where data repeats itself, write that part less.
Put the other way around, random data with no repetition at all cannot be shrunk. That is also why compressing an already compressed file again barely makes it any smaller. But when something that has been shrunk like this is expanded again, does it really come back exactly as it was?

Undo it and the original returns unchanged

With the methods we have seen so far, expanding gives back the original without a single letter wrong, because nothing was thrown away. The note "A four times" expands back into the four letters AAAA, and each short code turns back into its long piece when you look it up in the table.
Compression that loses nothing like this is called lossless compression. Data where a single wrong letter is unacceptable, such as text or programs, always uses lossless compression.

Tap the compressed tokens in turn to expand them. The shortened notes unpack into the original letters, and you can compare the result side by side with the original.

The expanded version matches the original down to every letter. Since nothing was lost in packing it small, you can compress without worry and bring it back exactly as it was when you need it.
Photos, music, and video, on the other hand, are sometimes made much smaller by deliberately throwing away details that people barely notice. This is called lossy compression, and the discarded parts can never be recovered. So should lossless compression always be done as hard as possible?

Smaller vs faster

Compression lets you choose a strength. Go gently and it finishes quickly but shrinks less; go hard and it shrinks more but takes longer to compress. The more thoroughly you hunt for repeated pieces, the smaller the result, but the more work it takes.
So the right answer depends on the situation. For a file you compress once and then keep for a long time, or one that many people will download, go hard; if you have to compress on the spot every time you send something, go gently.

Pick a compression strength and tap it. The harder you go, the smaller the size but the longer the time: the trade-off is plain to see.

Size and time move in opposite directions. You cannot have both at once: to pack something smaller you have to wait longer, and to finish faster you settle for less shrinking. With many compression methods, expanding takes about the same time whatever the strength, so it is mainly the compressing side that pays the price.
So compression is a tool you choose to fit the situation. When space is tight, go hard; when time is tight, go gently.

Summary

To sum up: compression is the craft of fitting the same information into less space. Runs of repetition shrink into which letter and how many times, and scattered pieces get short codes. The methods we have seen are lossless compression, where undoing gives back the original unchanged.
The harder you compress, the smaller the result, but it takes more time, so you choose according to the situation. Find where data repeats and write it less, yet get it back unchanged when you undo it: that is compression.

Tap the key points in order to review. (cut repetition → short codes for frequent pieces → undo gives the original unchanged → smaller vs time trade-off)

Compression is also used when computers send data to one another, because smaller data arrives sooner.
But what if the data grows so large that, however much you shrink it, it will not fit on a single computer? The next lesson, on distributed data, covers how to split data across many machines and keep copies in case of failure.