Skip to content
VirtusAcademy

Data Compression: Run-Length Encoding

FoundationHigherAQA

Master Data Compression: Run-Length Encoding for GCSE Computer Science with this free worksheet and full mark scheme — Foundation and Higher exam-style questions with worked answers for AQA GCSE Computer Science (8525). Run-length encoding (RLE) compresses data by recording repeated values as a value and a count.

Free downloads

These worksheets and mark schemes are original, written for Virtus Academy and checked against the current AQA specification. Every worksheet comes with a full mark scheme.

Foundation

WorksheetFoundation · PDFMark SchemeFoundation · PDF

Higher

WorksheetHigher · PDFMark SchemeHigher · PDF

Topic overview

Compression reduces file size, which means less storage is used, files transfer faster and less bandwidth is needed.

There are two kinds. Lossless compression reduces file size without losing any data, so the original file can be perfectly reconstructed. Lossy compression achieves greater reduction by permanently discarding some data, so the original cannot be recovered.

Run-length encoding is a lossless method. It replaces runs of identical values with the value and a count, so AAAABBB becomes 4A3B. It works well where long runs occur, such as simple graphics with blocks of one colour. It works badly where values alternate: ABABAB would become 1A1B1A1B1A1B, which is larger than the original.

Revision notes

Lossless and lossy

Lossless: no data is lost, and the original file can be perfectly reconstructed.

Lossy: some data is permanently discarded to achieve greater reduction, and the original cannot be recovered. Text and program files need lossless; photos and music often use lossy.

Run-length encoding

RLE replaces runs of identical values with the value and a count.

AAAABBB becomes 4A3B. It is lossless, because the original can be reconstructed exactly from the counts.

When RLE fails

RLE only helps where long runs of identical values occur.

ABABAB has no runs, so it becomes 1A1B1A1B1A1B — twice the original size. This is why RLE suits simple graphics with blocks of colour, but not photographs or text.

Key points

  • Compression reduces file size.
  • Lossless compression loses no data.
  • Lossy compression discards data permanently.
  • RLE replaces runs with a value and count.
  • RLE is a lossless method.
  • RLE can enlarge files with no runs.

Worked examples

Example 1

Apply run-length encoding to the sequence AAAABBBCC. [3 marks]

Working

There are four As, so 4Aencode the first run
Three Bs, so 3Bencode the second run
Two Cs, so 2C. The result is 4A3B2Cencode the final run and combine

Example 2

Explain why run-length encoding may increase the size of the sequence ABABAB. [2 marks]

Working

There are no runs of identical characters, so each is encoded as a count of onestate the problem
giving 1A1B1A1B1A1B, which uses twice as many characters as the originalexplain the result

Example 3

State the difference between lossless and lossy compression. [2 marks]

Working

Lossless compression loses no data, so the original file can be perfectly reconstructeddefine lossless
Lossy compression permanently discards some data, so the original cannot be recovereddefine lossy

Common mistakes

  • Saying RLE always reduces file size.

    It enlarges files with no runs of identical values.

  • Calling RLE lossy.

    It is lossless — the original is perfectly recoverable.

  • Forgetting the count for single characters.

    Each character needs a count, even if it is 1.

  • Saying lossy compression can be reversed.

    The discarded data is gone permanently.

Exam tips

  • State the count before each character.
  • Remember RLE is lossless.
  • Explain when RLE fails as well as when it works.
  • Match the compression type to the file type.

Key terms

Compression
Reducing the size of a file.
Lossless
Compression losing no data.
Lossy
Compression permanently discarding data.
Run-length encoding
Replacing runs of identical values with a count.

Related topics

Written and reviewed against the current AQA specification. Spotted an error? Let us know.