Why run-length encoding saves space

Name:

Date:

Class:

Quick Questions

Shade in the A or B circle for each question.

1. A row has 8 white pixels in a row. Which run-length code stores it with the fewest numbers?

A 8 white (one count)

B 1 white, 1 white, 1 white, 1 white, 1 white, 1 white, 1 white, 1 white

2. Which row does run-length encoding save the MOST space on?

A An all-white row of 10 pixels

B A checkerboard row of 10 pixels

3. A checkerboard row goes black, white, black, white, black, white, black, white. What does run-length encoding do here?

A It saves almost nothing, because every run is only 1 pixel long

B It saves lots of space, because there are many colours

4. Row A is coded as 1,1,1,1,1,1 and Row B is coded as 6. Which code is shorter?

A Row A, with 6 numbers

B Row B, with 1 number

5. True or false: run-length encoding always makes a picture's code shorter.

A True

B False

Match the Pairs

Draw a line connecting each item on the left to its match on the right.

Left column		Right column
10 0 0 0 0 0 0 0 → 8 white		A10 white (a whole row of 10 white pixels)
20 1 0 1 0 1 0 1 → 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1		BRow A: 8 numbers \| Row B: 2 numbers → Row B is better
3Compare two codes: a shorter code means the picture is stored using less space.		CThe runs were counted one pixel at a time. The whole row is one run, so it should be 8 white.
4Run-length encoding works best on rows with long runs of one colour.		DA checkerboard row has no long runs because the colour changes every pixel, so run-length encoding saves almost nothing.
5A checkerboard row 0 1 0 1 0 1 0 1 is the best row for run-length encoding.		EAn all-white row of 8 pixels can be stored as just 2 values, so run-length encoding saves a lot of space.
6All-white row of 8 pixels: 1 white 1 white 1 white 1 white 1 white 1 white 1 white 1 white		FA checkerboard row changes colour every pixel, so run-length encoding needs 16 numbers to store 8 pixels and saves nothing.

Definitions

run-length encoding

Fill in the Blanks

Complete each line of code by filling in the missing parts.

Row: 00000000 RLE: _,0

Row: 0000001111 RLE: 6,0,4,_

Row: 010101 RLE: _,0,1,1,1,0,1,1,1,0,1,1

pixels = 8 codes = 2 codes _ pixels

pixels = 8 codes = 16 codes _ pixels

Spot the Error

Shade in the letter of the line that contains an error.

Question 1

A row = "WWWWWWW"

B code = "8W"

C print(len(row))

D print(len(code))

Question 2

A row = "BWBWBWBW"

B code = "1B1W1B1W1B1W1B1W"

C print(len(code) < len(row))

Question 3

A row = "WWWWWWWWWW"

B code = "10W"

C print(len(row))

D print(len(row) + len(code))

Question 4

A row = "WWWWBBBB"

B code = "4B4W"

C print(len(row), len(code))

Question 5

A row = "WWWWWWWWWWWWWWWW"

B code = "16W"

C print("RLE saves nothing")

Answer Key

Why run-length encoding saves space

Section A: Quick Questions

A — 8 white (one count)

A — An all-white row of 10 pixels

A — It saves almost nothing, because every run is only 1 pixel long

B — Row B, with 1 number

B — False

Section B: Match the Pairs

0 0 0 0 0 0 0 0 → 8 white → An all-white row of 8 pixels can be stored as just 2 values, so run-length encoding saves a lot of space.

0 1 0 1 0 1 0 1 → 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 → A checkerboard row changes colour every pixel, so run-length encoding needs 16 numbers to store 8 pixels and saves nothing.

Compare two codes: a shorter code means the picture is stored using less space. → Row A: 8 numbers | Row B: 2 numbers → Row B is better

Run-length encoding works best on rows with long runs of one colour. → 10 white (a whole row of 10 white pixels)

A checkerboard row 0 1 0 1 0 1 0 1 is the best row for run-length encoding. → A checkerboard row has no long runs because the colour changes every pixel, so run-length encoding saves almost nothing.

All-white row of 8 pixels: 1 white 1 white 1 white 1 white 1 white 1 white 1 white 1 white → The runs were counted one pixel at a time. The whole row is one run, so it should be 8 white.

Section C: Definitions

run-length encoding — Counts each run of one colour instead of listing every pixel. It saves space on long runs, like an all-white row, but saves little when colours change every pixel, like a checkerboard.

Section D: Fill in the Blanks

Row: 00000000
RLE: 8,0

Row: 0000001111
RLE: 6,0,4,1

Row: 010101
RLE: 1,0,1,1,1,0,1,1,1,0,1,1

pixels = 8
codes = 2
codes < pixels

pixels = 8
codes = 16
codes > pixels

Section E: Spot the Error

A — The code 8W says there are 8 white pixels, but the row has only 7 W's. The row should be "WWWWWWWW" so the 2-character code can be compared with an 8-pixel row.

C — A checkerboard row changes colour every pixel, so the run-length code (16 characters) is longer than the row (8). The test should use > to show the code is longer.

D — The space saved is how much shorter the code is than the row, so you subtract: len(row) - len(code). Adding the lengths would not show any saving.

B — The row has 4 white pixels and then 4 black pixels, so the runs must be in that order: 4W4B. The broken line has the colours the wrong way around.

C — An all-white row is one long run. The code 16W has 3 characters instead of 16, so run-length encoding saves a lot of space.