How does file compression make files smaller?

1. Sam made a picture and wants to send it to a friend. But the file is big, so it would travel slowly and fill up storage. Can the same picture be written in less space?
2. Look closely at one row of the picture. The file lists every square one by one: blue, blue, blue, blue, blue, blue. It says the same thing again and again.
3. Instead of listing every square, count each run of one color: six blue, two yellow, four blue. Twelve squares became three short notes.
4. Whole rows repeat too. When a row is just like one that came earlier, the note can simply say: same as that row. That is even shorter.
5. The short notes are sent instead of the big list. The friend's device follows them step by step and rebuilds the picture, exactly the same as before. Nothing was lost.
6. Photos have very few exact repeats. So photo files round nearly equal colors to the same color first. You can hardly see the change, but now there are repeats to squash.

Press Next to follow one picture from a long list to a short note and back.

• The original file. The picture is a grid of colored squares. The plain file lists the color of every square: 96 squares, 96 entries.
• Look for repeats. The program reads along each row and watches for a color that keeps going. A stretch of one color is called a run.
• Write the counts. For each run it writes two things: how many squares, and which color. A run of twelve squares costs the same as a run of two.
• Reuse repeated lines. If a whole row matches an earlier row, the note says which one to copy. That costs just one entry.
• Compare the sizes. Now compare. The packed file has far fewer entries than the original, so it is quicker to send and takes less room.
• Unpack. To unpack, the program reads each note and paints that many squares. The picture comes back exactly, square for square.

Press Squash, then try the other pictures or paint your own. Which pictures shrink a lot, and which do not shrink at all?

Experiment: Which picture will shrink the most when you squash it?

1. Press Squash on the stripes picture and read the two sizes.
2. Choose the confetti picture. What happened to the size?
3. Paint a few squares in the stripes picture and watch the notes change.
4. Press Unpack to check that the picture comes back the same.

What we found: The stripes shrink the most, because each long run of one color becomes a single short note. The confetti does not shrink at all: it actually gets bigger, because with no repeats every square needs its own count. Compression only works when there is something repeated to describe.

Turn on JavaScript to try it yourself.

Each picture must be squashed small enough to fit in the message. Choose how to read it, then press Squash. Three pictures!

A computer file is a very long list of numbers. In a simple picture file there is a number for the color of every single square, even when thousands of squares in a row are the same blue sky. All that repeating is wasteful, and compression is the art of saying the same thing in less space.

The simplest trick is counting. Instead of blue, blue, blue, blue, blue, blue, write 6 blue. A stretch of one color is called a run, so this trick is called run-length encoding. A second trick is to notice bigger patterns. If a whole row, a word or a phrase has appeared before, the file can just point back to it: same as before. Zip files use this trick.

To open the file again, the computer reads the short notes and follows them. It gets back exactly what was there before, with nothing missing. That is why this kind is called lossless. It is used for writing, programs and drawings, where every detail matters.

Compression cannot shrink everything. A picture where every square differs from its neighbors has no repeats to describe, so the notes come out longer than the picture. And you cannot squash a file again and again: once the repeats are gone, there is nothing left to remove. Photos and music use a different trick and throw away tiny details you would not notice, which makes them much smaller but not exactly the same.

Key words

Compression

Writing the same information using less space.

Run

A stretch of the same thing repeated in a row, such as six blue squares.

Run-length encoding

Writing how many and which color for each run, instead of listing every square.

Lossless

Compression that can be undone exactly: the unpacked file is identical to the original.

Lossy

Compression that leaves out tiny details to save a lot of space. The result is close, but not exactly the same.

Redundancy

Saying the same thing more than once. It is what compression removes.

Check your thinking

1. How could you write blue, blue, blue, blue, blue, blue, blue, blue in a shorter way?

   Show the answer

   8 blue. A count and a color describe the whole run, and nothing is lost.

2. Which picture shrinks the most with run-length encoding?

   Show the answer

   A flag with three wide stripes. Wide stripes are long runs, and each long run becomes one short note.

3. You unpack a losslessly compressed drawing. How does it compare with the original?

   Show the answer

   It is exactly the same, square for square. Lossless means nothing is lost. The notes rebuild every square.

4. Why does a confetti picture get bigger when you squash it by counting runs?

   Show the answer

   There are no repeats, so every square needs a count as well as a color. With nothing repeated, the notes say 1 red, 1 blue, 1 green, which is longer than the squares themselves.

5. Why are photos usually saved with lossy compression?

   Show the answer

   Photos have few exact repeats, so leaving out tiny details saves far more space. Nearly equal colors are rounded to equal ones, which creates runs and patterns to compress.

6. A row of 60 pixels has 5 runs. Stored as counts and values, how many numbers does it need, and what is the compression ratio?

   Show the answer

   10 numbers, so the ratio is 6 to 1. Each run needs a count and a value: 5 times 2 is 10. The ratio is 60 divided by 10, which is 6.