When run-length encoding makes data bigger

Name:

Date:

Class:

Quick Questions

Shade in the A or B circle for each question.

1. Which string will run-length encoding make LONGER?

A ABCDEF (encodes to 1A1B1C1D1E1F)

B AAAAAA (encodes to 6A)

2. What does run-length encoding add for each run of characters?

A A dictionary that stores the repeated words

B A count showing how many times the character repeats

3. Which data is the BEST case for run-length encoding?

A WWWWWWWWWWWWBBBB (a few very long runs)

B WBWBWBWBWBWBWBWB (alternating letters)

4. The string ABAB is encoded with RLE as 1A1B1A1B. What happened to the size?

A It shrank from 8 characters to 4

B It grew from 4 characters to 8

5. Why can RLE make data bigger?

A A count is added to every run, even runs of length 1

B RLE deletes characters that look the same

Match the Pairs

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

Left column		Right column
1AAAAAAAA → 8A		AThe encoded string has 12 characters, which is longer than the original 6. RLE only saves space when there are long runs.
2ABCDEF → 1A1B1C1D1E1F		BAABBCC (6) → 2A2B2C (6)
3Comparing lengths shows whether RLE helped: the encoded text must be shorter than the original		CRLE counts consecutive repeats only. ABAB has no runs, so the correct encoding is 1A1B1A1B, which is twice as long.
4Choose a technique to suit the data: use RLE for data with long runs, such as a plain white image row		DBest case for RLE: one long run shrinks from 8 characters to 2
5RLE always makes data smaller, so ABCDEF → 1A1B1C1D1E1F is shorter		EWorst case for RLE: no repeats, so the encoded data doubles from 6 to 12 characters
6ABAB → 2A2B (encoded is shorter, so RLE worked)		FWWWWWWWWWWWW → 12W

Definitions

RLE expansion

Fill in the Blanks

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

ABC encodes to _A1B1C

IF encodedLen _ originalLen THEN OUTPUT "RLE made it bigger" END IF

AAAAAAAAAA -> __A (3 chars)

RLE saves space when data has long ____

Original: ABCDEF, length 6 Encoded: 1A1B1C1D1E1F Encoded length: __

Spot the Error

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

Question 1

A data ← AAAAAA

B encoded ← 1A1B1C1D1E1F

C original_length ← 6

D encoded_length ← 12

Question 2

A data ← AAAAAAAAAA

B encoded ← 10A

C original_length ← 10

D encoded_length ← 2

Question 3

A data ← ABAB

B encoded ← 1A1B1A1B

C encoded_length ← 4

D original_length ← 4

Question 4

A data ← WWWWWWWWBB

B encoded ← 8W1B

C IF encoded shorter THEN

D use RLE

Question 5

A IF runs are short THEN

B RLE saves space

C ELSE RLE may make it bigger

Answer Key

When run-length encoding makes data bigger

Section A: Quick Questions

A — ABCDEF (encodes to 1A1B1C1D1E1F)

B — A count showing how many times the character repeats

A — WWWWWWWWWWWWBBBB (a few very long runs)

B — It grew from 4 characters to 8

A — A count is added to every run, even runs of length 1

Section B: Match the Pairs

AAAAAAAA → 8A → Best case for RLE: one long run shrinks from 8 characters to 2

ABCDEF → 1A1B1C1D1E1F → Worst case for RLE: no repeats, so the encoded data doubles from 6 to 12 characters

Comparing lengths shows whether RLE helped: the encoded text must be shorter than the original → AABBCC (6) → 2A2B2C (6)

Choose a technique to suit the data: use RLE for data with long runs, such as a plain white image row → WWWWWWWWWWWW → 12W

RLE always makes data smaller, so ABCDEF → 1A1B1C1D1E1F is shorter → The encoded string has 12 characters, which is longer than the original 6. RLE only saves space when there are long runs.

ABAB → 2A2B (encoded is shorter, so RLE worked) → RLE counts consecutive repeats only. ABAB has no runs, so the correct encoding is 1A1B1A1B, which is twice as long.

Section C: Definitions

RLE expansion — When data has few repeats, run-length encoding adds a count to every character, so the result can be longer than the original. It only saves space when the data has long runs.

Section D: Fill in the Blanks

ABC encodes to 1A1B1C

IF encodedLen > originalLen THEN
  OUTPUT "RLE made it bigger"
END IF

AAAAAAAAAA -> 10A (3 chars)

RLE saves space when data has long runs

Original: ABCDEF, length 6
Encoded: 1A1B1C1D1E1F
Encoded length: 12

Section E: Spot the Error

A — The encoded text 1A1B1C1D1E1F has six different letters, so the data must be ABCDEF with no repeats. AAAAAA would encode to just 6A, so line 1 should be data ← ABCDEF.

D — The encoded text 10A is 3 characters long (1, 0 and A), not 2. Line 4 should be encoded_length ← 3. This is the best case, because one long run shrinks 10 characters to 3.

C — 1A1B1A1B has 4 runs, and each run needs 2 characters (a count and a letter), so the encoded length is 8. Line 3 should be encoded_length ← 8, which is double the original 4.

B — The data ends with two B characters, so the second run is 2B, not 1B. Line 2 should be encoded ← 8W2B.

A — RLE saves space when the runs are long. Short runs are the case where it can make data bigger, which is what the ELSE line says. Line 1 should be IF runs are long THEN.