Compression stores data in fewer numbers, so it takes less space and less time to send. Run-length encoding stores how many of each colour there are in turn (3, 4, 1) instead of every pixel. It gives back exactly the same picture (lossless), and works best on data with long runs.
A fax machine sent whole pages down a phone line in the 1980s, as numbers. How do you send a page with far fewer numbers than it has dots?
Pictures, songs and videos are huge: a phone photo is tens of millions of numbers. Compression stores the same data in fewer numbers, so it fits in less space and is quicker to send.
Here the pictures are black and white, one number a pixel. Run-length encoding stores each row as the lengths of its runs (pixels of the same colour in a row), taking turns: white first, then black, then white, and so on.
Predict: Read the problem and decide what you think before you try anything. A wrong guess is fine: it shows you what to look for.
Try: Try it on the board and compare the result with your prediction.
Investigate: Work out why it happens, one step at a time.
Modify: Change the problem on purpose and see what happens.
Practise: A few on your own, to check you have it.
Make: Make your own problem using what you have learned. Expect a few tries; that is normal.
Make your prediction first. Help opens once you've locked it in.
PredictRead the problem and decide what you think before you try anything. A wrong guess is fine: it shows you what to look for.
A shorter row
TryTry it on the board and compare the result with your prediction.
Try: paint a run
Was your prediction right? Change a pixel and watch the code change.
Try it yourselfYour edits are saved in this browser.
Paint pixels 4 to 7 black to match the picture. What code does the board write for the row?
Use the board. This ticks when you get there.
InvestigateWork out why it happens, one step at a time.
Worked example: encode a picture
Worked exampleBefore each step, say what you think comes next.
0,8Row 2 starts black, so the code starts with 0 (no whites).
8Row 3 is all white: one run.
1,1,1,1,1,1,1,1Row 4 changes every pixel: 8 numbers, no saving.
3+2+1+8=14 numbers instead of 32About 44% of the size. Long runs save a lot; no runs save nothing.
Decompressing reads the codes back and gives exactly the same picture, so run-length encoding is lossless. Now decode 0, 2, 6.
Sam encodes a row that starts with black. Click the line where it first goes wrong.
ModifyChange the problem on purpose and see what happens.
Vary: one change at a time
Try it yourselfYour edits are saved in this browser.
Paint the whole row black. What is its code?
Use the board. This ticks when you get there.
Paint every second pixel black: white, black, white, black… How many numbers is the code?
Use the board. This ticks when you get there.
Change this picture so its codes use as few numbers as possible.
Use the board. This ticks when you get there.
An 8 × 8 icon (64 pixels) compresses to 16 numbers. What percentage of the original size is that?
PractiseA few on your own, to check you have it.
Codes
A row is decoded from **1, 3, 2, 2**. How many pixels long is it?
MakeMake your own problem using what you have learned. Expect a few tries; that is normal.
Draw from the codes
Then: how many numbers would the plus sign need if it were twice as big (12 × 12)?
Try it yourselfYour edits are saved in this browser.
Need a hint?
Each row's first number counts white, then they take turns.
Another hint
2, 2, 2 means 2 white, 2 black, 2 white.
Another hint
0, 6 means no white, then 6 black: a whole black row.
The codes on the right describe a 6 × 6 picture. Paint it.
Use the board. This ticks when you get there.
For teachers
Students paint black and white pixels and watch each row's run-length code, to explain why data is compressed, apply run-length encoding, calculate the saving and see when it fails (AC9TDI10K03 nodes 1 and 2). About 45 minutes.
I can encode and decode a row with run-length encoding.
I can say when run-length encoding saves space and when it doesn't.
Before class
CS Unplugged's Image representation activity (the fax-machine pixel codes) is the same model on paper; doing one page of it first works well.
The one idea: store runs instead of every value; decompressing gives back the data exactly (lossless). It saves when the data has long runs, and can make data bigger when it has none.
Simplification: real formats use a count and a value, as the lossy lesson does; the black-and-white form here (taking turns from white) is CS Unplugged's.
Running the lesson
Predict: students who chose 4 lose the position; ask them to rebuild the row from 4.
Try: ask what code a row of one black pixel at the end would get (7, 1).
Worked example: pause before row 2 and ask how to say "no white".
Vary: the checkerboard task usually surprises; ask what kind of real picture is like it.
Make: swap codes between pairs: one draws a picture, the other decodes it.
The hard part (on purpose)
Rows that start black. Insist the first number always counts white, even when it is 0.
When students get stuck
A student writes 2, 6 for a row that starts black (Sam's mistake). Ask: What colour does the first number count? Fix: White, always: start with 0.
A student thinks every picture shrinks. Ask: What is the code for a checkerboard row? Fix: Eight 1s: no saving.
Stretch and support
Stretch: Design an 8 × 8 picture that compresses to 8 numbers or fewer. Design one that makes the code longer than 64.
Support: Have students say the colours aloud while counting: white 3, black 4, white 1.
Where it leads
Next: Lossy or lossless.
Builds on: Data representation (pixels and bytes). Where it leads: file formats (PNG, GIF and ZIP use lossless methods; JPEG and MP3 lossy).
a shorter row: Committing to how to store a row in fewer numbers tests the new move before it is shown: count runs, in turn, instead of storing every pixel.
Try: paint a run: Painting pixels 4 to 7 black and reading the code settles the prediction: the row becomes 3, 4, 1.
Worked example: encode a picture: Encoding four rows, including one that starts black and one with no runs, models the new move and shows when it fails. Sam leaves out the leading 0, the misconception planted after the method; the why question covers what compression is for.
Vary: one change at a time: Each task changes one thing in the data: a whole run, then the worst case (no runs), then the best case (every row one run), then the ratio and when to use RLE.
codes: Encoding and decoding rows, a code longer than the data, run-length encoding on text, and choosing what compresses well.
draw from the codes: Drawing the picture from its codes reverses the process: students decompress by hand and check that the codes rebuild it exactly.
Now you can
Explain why data is compressed.
Encode and decode a row with run-length encoding.
Say when run-length encoding saves space and when it doesn't.