The answersDownload the PDF
Worksheet

F8.9 Compression

Data representation · GCSE · OCR J277 1.2.5, AQA 8525 3.3.8, Edexcel 1CP2 2.3.2 · about 20 min

BugBotLab
NameClassDate

What this lesson is about

Lossy and lossless; run length encoding and Huffman coding.

Questions 5 marks in all

  1. [1 mark]Which kind of compression must be used for a program file?

    1. ALossless, because every character must be kept exactly
    2. BLossy, because it is smaller
    3. CEither
    4. DNeither

  2. [1 mark]What does lossy compression do?

    1. APermanently removes detail people are unlikely to notice
    2. BKeeps every bit of the original
    3. CMakes a file larger
    4. DEncrypts the file

  3. [1 mark]Run length encode WWWWBBW in the form count then character.

  4. [1 mark]On which data does RLE work worst?

    1. AData where the value changes every character
    2. BData with long runs
    3. CBlack and white images
    4. DBlank rows

  5. [1 mark]In Huffman coding, which characters get the shortest codes?

    1. AThe most frequent ones
    2. BThe least frequent ones
    3. CCapital letters
    4. DThe first characters in the message

The task: compress a row

Write rle_encode(text) and rle_decode(code) yourself. Encode the row ........######....######........ and print it as encoded: <code>, then print original: <n> characters, encoded: <m> characters, and finally decoded matches: True, using your decode function.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

row = "........######....######........"

Plan your program here, then type it in and press Run.

QR code
Do it on the robot
www.bugbotlab.com/learn/f8-9-compression/
The simulator checks it and tells you when it passes. Nothing to install, no account.

Challenges

  1. Find a row of 20 characters where RLE makes the result longer. What is the worst case?
  2. Decode a Huffman-coded message: turn codes round into a dictionary from code to character, and read bits until they match a code.
  3. Why would lossy compression be a bad idea for the robot's program files?