Compression: packing it smaller

Cut the repetition

Earlier we saw that information
takes up room as bits, 0s and 1s.
If we could hold it taking less room,
we'd keep the same information smaller.
The easiest skill is cutting repetition.
When the same letter runs on in a row,
instead of writing each one out,
we note only what repeats and how many times.
AAAA becomes A four times, like that.

Tap a run of repeated letters. The long run shrinks into what repeats and how many times, and the length drops.

The long run shrank short.
Not a single letter was thrown away.
We only noted what and how many times.
So expanding it gives back the original.
The more repetition, the more it shrinks.
But what if it isn't the same letter in a row,
and instead the same piece is scattered here and there?
How could we shrink that?

Make the pattern short

Scattered repeats can be cut too.
Find a long piece that shows up often
and fix a single short code for it.
Then each time the long piece appears,
write it as that short code instead.
What the code means
can be kept in a table on the side.
The more often a piece appears, the bigger the win,
since more swaps mean more shrinking.

Tap a frequent piece to assign it a short code. That piece turns into the code and the total length drops.

With the long piece swapped for a short code,
the whole shrank noticeably.
Cutting repeats and giving short codes
come from the same idea after all:
holding the same information in less room.
But once we've shrunk it like this,
we'll want the original content later,
so when we expand it, does it really come back exactly?

Undo it and the original returns

This is compression's most solid promise.
Shrink it small, then expand it again,
and the original returns without a single letter wrong.
Naturally so, since nothing was thrown away.
A four times becomes AAAA again,
and the short code becomes the long piece again.
Compression that loses nothing like this
is called lossless.
It fits things that must not be off by a letter,
like text or programs.

Tap the compressed copy to expand it. The shrunk form unpacks back to letters, and you check it matches the original side by side.

The expanded one matched the original exactly.
Even held small, nothing was lost.
So we can compress without worry
and bring it back as-is when needed.
Then should we always compress
as hard as we possibly can?
There's actually a trade hidden there.
Shall we see what's being traded for what?

Smaller versus time

Compression lets you pick a strength.
Go gentle and it's fast but shrinks less;
go hard and it shrinks more,
but compressing and unpacking take more time.
The more carefully you hunt repeats and patterns,
the smaller it gets, but the more effort it costs.
So the right answer changes with the situation.
If space is tight, go hard;
if it must be fast, go gentle.

Pick and tap a compression strength. The harder you go, the smaller the size but the longer the time, the trade in plain view.

You saw size and time pull against each other.
You can't have both.
Hold it smaller and you wait longer;
finish faster and it shrinks less.
So compression is a tool you choose how to use.
Storing it long, go hard;
opening it often, go gentle.
Now let's wrap the whole thing up.

Let's wrap up

Gathered on one line, it is this.
Compression holds the same information smaller.
Repetition shrinks into what and how many times,
and a frequent piece gets a short code.
Undo it and the original returns, so nothing is lost.
Compress harder and it's smaller,
but it costs more time, so choose by the situation.
Pack it small yet undo gives it back as-is;
that is compression.

Tap the key points in order to review. (cut repetition -> short code for frequent pieces -> undo gives the original as-is -> smaller versus time trade)

Now you've got the knack
of holding the same information smaller.
Just cutting repetition and giving short codes
lets you save space thriftily.
And since undoing gives the original as-is,
you can pack it small without worry.
This sense of handling data small yet whole
carries into the next story.
Let's keep exploring together.