Activity 3

You Can Say That Again! — Text Compression

Summary

Computers have only a limited amount of space to store information, so they need to represent that information as efficiently as possible. This process is called compression. By encoding data before storing it, and decoding it when it's retrieved, a computer can store more data—or transmit it more quickly across the Internet.

Curriculum Links

• English: Recognizing patterns in words and text.
• Technology: Understanding how computers work, at a technical level.

Skills

• Copying written text

Ages

9 and up

Materials

• Overhead transparency made from OHP Master: You Can Say That Again! (page 25)

Each student will need:

• Worksheet Activity: You Can Say That Again! (page 26)
• Worksheet Activity: Extras for Experts (page 27)
• Worksheet Activity: Short and Sweet (page 28)
• Worksheet Activity: Extras for Real Experts (page 29)

---

You Can Say That Again!

Introduction

Computers must store and transmit enormous amounts of data. To avoid using excessive storage space, or taking too long to send information over an Internet connection, computers compress text—shrinking it down in a systematic way.

Demonstration and Discussion

Show "The Rain" on the overhead projector (page 25). Look for patterns of letters in this poem. Can you find groups of two or more letters—or even whole words or phrases—that repeat? Replace these repeated sections with boxes, as shown in the diagram below.

---

OHP Master: You Can Say That Again!

The Rain

Pitter patter
Pitter patter
Listen to the rain
Pitter patter
Pitter patter
On the window pane

---

Worksheet Activity: You Can Say That Again!

Many of the words and letters in this poem are missing. Can you fill them in correctly? You'll find the missing pieces in the box that each arrow points to.

Now choose a simple poem or nursery rhyme and design your own version of this puzzle. Make sure your arrows always point back to an earlier part of the text. Your poem should be solvable by reading left to right and top to bottom—the same way we normally read.

Challenge: See how few of the original words you can keep while still making the puzzle solvable!

Some ideas to try: Three Blind Mice, Mary, Mary, Quite Contrary, Hickory Dickory Dock—or a Dr. Seuss book!

Hint: Avoid crowding your arrows together. Leave plenty of space around the letters and words as you write, so there's room for boxes within boxes and the arrows that point to them.

It's easier to design the puzzle if you write out the full poem first, then decide where to place the boxes.

---

Worksheet Activity: Extra for Experts

How would you solve this puzzle?

Ban---

Sometimes, the missing text points back to part of itself. This can still be decoded correctly if you copy the letters from left to right—each letter becomes available to copy just before it's needed. This trick is especially useful for computers when they encounter a long run of a repeated character or pattern.

Try drawing a few examples of your own.

On computers, the boxes and arrows are represented using numbers. For example, the word Banana can be written as Ban(2,3). The "2" means: count back two characters to find the starting point for copying.

Ban---

And the "3" means: copy three consecutive characters from that starting point:

Bana--
Banan-
Banana-

Since two numbers are needed to encode a repeated section, compression usually only pays off for groups of two or more letters. Otherwise, there's no real space savings—in fact, the file could actually get larger if two numbers are used just to represent a single letter.

Try making up your own words written the way a computer would compress them. Can your friends decode them?

---

Worksheet Activity: Short and Sweet

How many words do you really need here?

Imagine you're a computer trying to fit as much data as possible onto a limited disk. Cross out every group of two or more letters that has already appeared earlier in the text. These repeated groups are no longer necessary—they could simply be replaced by a pointer back to their first occurrence. Your goal is to cross out as many letters as you can.

*I know an old lady who swallowed a bird
How absurd! She swallowed a bird!
She swallowed the bird to catch the spider
That wriggled and jiggled
and tickled inside her
She swallowed the spider to catch the fly
I don't know why she swallowed a fly
Perhaps she'll die…*

---

Worksheet Activity: Extra for Real Experts

Ready for some serious compression practice?

A computer program analyzed the following story and found that at least 1,633 letters could be crossed out. How many can you find? Remember: only groups of two or more repeated characters can be eliminated. Good luck!

nce upon a time, long, long ago, three little pigs set out to make their fortunes. The first little pig wasn't very clever, and decided to build his house out of straw, because it was cheap. The second little pig wasn't very clever either, and decided to build his house out of sticks, for the "natural" look that was so very much in fashion, even in those days. The third little pig was much smarter than his two brothers, and bought a load of bricks in a nearby town, with which to construct a sturdy but comfortable country home.

Not long after his housewarming party, the first little pig was curled up in a chair reading a book, when there came a knock at the door. It was the big bad wolf, naturally.

"Little pig, little pig, let me come in!" cried the wolf.

"Not by the hair on my chinny-chin-chin!" squealed the first little pig.

"Then I'll huff, and I'll puff, and I'll blow your house down!" roared the wolf, and he did huff, and he did puff, and the house soon collapsed. The first little pig ran as fast as he could to the house of sticks, and was soon safe inside. But it wasn't long before the wolf came calling again.

"Little pig, little pig, let me come in!" cried the wolf.

"Not by the hair on my chinny-chin-chin!" squealed the second little pig.

"Then I'll huff, and I'll puff, and I'll blow your house down!" roared the wolf, and he did huff, and he did puff, and the house was soon so much firewood. The two terrified little pigs ran all the way to their brother's brick house, but the wolf was hot on their heels, and soon he was on the doorstep.

"Little pig, little pig, let me come in!" cried the wolf.

"Not by the hair on my chinny-chin-chin!" squealed the third little pig.

"Then I'll huff, and I'll puff, and I'll blow your house down!" roared the wolf, and he huffed, and he puffed, and he huffed some more, but of course, the house was built of brick, and the wolf was soon out of breath. Then he had an idea. The chimney! He clambered up a handy oak tree onto the roof, only to find that there was no chimney, because the third little pig, being conscious of the environment, had installed electric heating. In his frustration, the wolf slipped and fell off the roof, breaking his left leg, and severely injuring his pride. As he limped away, the pigs laughed, and remarked how much more sensible it was to live in the city, where the only wolves were in the zoo. And so that is what they did, and of course they all lived happily ever after.

O

---

What's It All About?

The storage capacity of computers is growing at an astonishing rate—over the past 25 years, the amount of storage on a typical computer has increased roughly a millionfold—yet we still find more and more to fill it with. Computers can now store entire books, entire libraries, and even music and movies, provided there's room. Large files also slow things down on the Internet, since bigger files take longer to download. At the same time, we keep trying to make computers smaller: even a cellphone or a wristwatch is now expected to hold large amounts of information.

Fortunately, there's a solution. Instead of buying more storage space or a faster Internet connection, we can compress the data so it takes up less room. This process—compressing and then decompressing data—is usually handled automatically by the computer. All we notice is that a disk holds more, or that web pages load faster; we don't see the extra processing work happening behind the scenes.

Many different compression methods have been invented. The method used in this activity—pointing back to earlier occurrences of repeated chunks of text—is often called Ziv-Lempel coding, or LZ coding, named after the two Israeli professors who invented it in the 1970s. It works for any language and can often cut the size of data in half. On personal computers, it's sometimes known as "zip" compression, and it's also used for GIF images and high-speed modems. In modems, this compression reduces the amount of data that must travel over the phone line, allowing transmission to happen much faster.

Other compression methods work differently: they assign shorter codes to letters that appear more frequently. Morse code, for instance, was built on exactly this idea.

Solutions and Hints

You Can Say That Again! (page 26)

*Pease porridge hot,
Pease porridge cold,
Pease porridge in the pot,
Nine days old.*

*Some like it hot,
Some like it cold,
Some like it in the pot,
Nine days old.*