Cambridge 9618 · International A Level Computer Science · ~18 min read
Notes
Video
Slides
Quiz
Worksheet
Lossy vs Lossless Compression
Compression reduces file size by encoding data more efficiently. The key distinction in Cambridge 9618 is whether the original data can be exactly recovered:
🗜️ Lossy
Some data is permanently removed
Original cannot be exactly recovered
Smaller files — higher compression ratio
Exploits limitations of human perception
Used for: MP3 (audio), JPEG (images), MPEG (video)
Not suitable for text, programs, or medical images
📦 Lossless
All original data is preserved
Original can be exactly restored on decompression
Smaller compression ratio than lossy
Removes redundancy, not actual data
Used for: PNG (images), ZIP/RLE (files), Huffman coding
Essential for text, programs, databases, medical data
Run-Length Encoding (RLE)
RLE is a simple lossless compression method that replaces consecutive repeated values with a (count, value) pair. It is most effective when data contains long runs of the same value — common in bitmap images with large areas of one colour.
For a black-and-white bitmap image, each pixel is 1 bit. A row of pixels might be stored as:
Pixel row (each block = 1 pixel)
W
W
W
W
W
B
B
B
W
W
B
B
B
B
↓ RLE encode
(5,White)(3,Black)(2,White)(4,Black)
14 individual pixel values → 4 pairs. Excellent for images with large uniform areas.
When does RLE work poorly?
RLE can increase file size if there are few or no consecutive repeated values — e.g. alternating ABABAB would encode as (1,A)(1,B)(1,A)... which is larger than the original. RLE works best for simple graphics like screenshots, logos, and clipart (PNG uses RLE), but poorly for photographic images with constant colour variation (JPEG uses lossy instead).
Huffman Coding
Huffman coding is a lossless compression method that assigns shorter binary codes to more frequent characters and longer codes to less frequent ones. This reduces the average number of bits needed per character.
Building a Huffman tree — Step by step
Given the text "AABBBCCCCDDDDDD" (frequency: A=2, B=3, C=4, D=6):
Step 1 — sort by frequency (ascending):
A:2 B:3 C:4 D:6
Step 2 — combine two smallest into a node (sum their frequencies):
[A+B]:5 C:4 D:6
Step 3 — re-sort, combine two smallest again:
Sort: C:4 [A+B]:5 D:6
Combine C and [A+B]: [C+A+B]:9 D:6
Step 5 — assign codes (left=0, right=1 at each branch):
D: 0 (left from root)
C: 10 (right from root, left)
B: 110 (right from root, right, left)
A: 111 (right from root, right, right)
Huffman code table
Character
Frequency
Huffman Code
Code Length
Bits used (freq × length)
D
6
0
1
6 × 1 = 6
C
4
10
2
4 × 2 = 8
B
3
110
3
3 × 3 = 9
A
2
111
3
2 × 3 = 6
Total bits (Huffman)
29 bits
Fixed 2-bit codes (4 chars)
15 × 2 = 30 bits
Bits needed — fixed 2-bit vs Huffman
Fixed: 30 bits
Huffman: 29 bits (3% saving)
Larger savings appear with skewed frequency distributions (e.g. English text where 'E' is very common)
Huffman coding properties
Variable-length codes: more frequent characters get shorter codes
Prefix-free: no code is a prefix of another (so decoding is unambiguous)
Requires frequency table: the code table must be stored with the compressed data for decompression
Always lossless: the original data can be perfectly restored
When to Use Each
Scenario
Best choice
Reason
Sending a voice recording over the internet
Lossy (MP3)
Small quality loss inaudible; file much smaller for streaming
Archiving a software executable
Lossless (ZIP)
Every bit must be preserved — corrupted programs won't run
Storing a medical X-ray
Lossless
Cannot risk any data loss — diagnosis depends on accuracy
Sending a photographic image by email
Lossy (JPEG)
Slight quality reduction acceptable; much faster to send
Logo/icon with few solid colours
Lossless (PNG/RLE)
Few colours → RLE very effective; sharp edges preserved
Cambridge 9618 exam tip: For RLE questions, show the (count, value) pairs and calculate bits before and after. For Huffman, you may be asked to use a given tree to encode/decode a string, or to calculate space saved. Know that Huffman assigns shorter codes to more frequent characters, codes are prefix-free, and the code table must be stored/transmitted with the data. Always state lossy/lossless and justify based on whether original data must be recoverable.
⚠️ Common Mistakes
Saying lossless removes "less" data than lossy — lossless removes NO data; it only removes redundancy
Forgetting that RLE can make data larger if there are few repeated sequences (e.g. random images)
Confusing Huffman with RLE — RLE replaces runs of repeated values; Huffman assigns variable-length codes based on frequency
Forgetting that Huffman requires the code table to be transmitted/stored alongside the compressed data
Claiming JPEG is lossless — it is lossy; PNG is the lossless image format
Saying compression ratio = compressed size / original size — it is original / compressed (higher is better)
✅ Notes completed!
▶
Video coming soon
Click slide or press arrow keys to navigate
Worksheet — 3.1.4 Data Compression
8 questions · Cambridge 9618 standard
Q1State two differences between lossy and lossless compression.[2]
✅ Mark scheme
Lossy permanently removes data so the original cannot be exactly recovered; lossless preserves all data so the original can be exactly restored [1]; lossy achieves a higher compression ratio (smaller files) than lossless; lossless removes only redundancy [1].
Q2Apply run-length encoding to the string "WWWWWBBBWWBBBBBBW" and show the encoded output as (count, value) pairs. How many values are in the original vs encoded?[4]
Q3State one situation where run-length encoding would NOT reduce file size, and explain why.[2]
✅ Mark scheme
Example: a photographic image with many different pixel colours — there are few or no consecutive repeated values [1]; RLE would store (1, colour) for each individual pixel, doubling the data needed rather than reducing it [1]. Accept any valid example with explanation.
Q4Given Huffman codes E=0, T=10, A=110, N=111, decode the bit string: 011010110111[3]
✅ Mark scheme
0→E; 110→A; 10→T; 110→A; 111→N [1 per correct character decoded; allow ecf for first error]; result: EATAN [3].
Q5Explain why Huffman coding is lossless and state one additional piece of information that must be sent alongside the compressed data for decompression to work.[3]
✅ Mark scheme
Huffman coding is lossless because every bit of the original data is encoded in the compressed output — no information is discarded [1]; decompression uses the code table to map each bit pattern back to the original character, perfectly recovering all data [1]; the Huffman code table (which maps each code to its character) must be transmitted with the compressed data, as without it the receiver cannot decode the compressed bit string [1].
Q6A user wants to upload a recording of a lecture to a website for students to download. Should they use lossy or lossless compression? Justify your answer.[3]
✅ Mark scheme
Lossy compression (e.g. MP3) [1]; the lecture is audio — human hearing cannot detect the small quality reduction caused by lossy compression [1]; the file will be much smaller, making it faster to upload/download and using less storage space — exact bit-perfect reproduction is not needed for a lecture recording [1].
Q7A bitmap image is 800 × 600 pixels with a colour depth of 24 bits. Calculate the uncompressed file size in megabytes (1 MB = 1,048,576 bytes). The image is then compressed using lossy compression to 1.2 MB. Calculate the compression ratio and state one visual consequence of this lossy compression.[5]
✅ Mark scheme
Number of pixels = 800 × 600 = 480,000 [1]; Total bits = 480,000 × 24 = 11,520,000 bits [1]; Total bytes = 11,520,000 ÷ 8 = 1,440,000 bytes; MB = 1,440,000 ÷ 1,048,576 ≈ 1.37 MB [1]; Compression ratio = 1.37 ÷ 1.2 ≈ 1.14:1 (accept working shown with uncompressed ÷ compressed) [1]; Visual consequence: loss of fine detail / colour banding / artefacts around high-contrast edges, as data discarded cannot be recovered [1].
Q8Explain how Run-Length Encoding (RLE) compresses data, using the example string "AAABBBCCDDDDDD". Calculate the compressed representation and state one type of image where RLE achieves high compression and one where it achieves little compression, justifying each.[5]
✅ Mark scheme
RLE replaces runs of consecutive identical values with a count and the value itself [1]; "AAABBBCCDDDDDD" → 3A 3B 2C 6D (or equivalent notation) — 14 characters reduced to 8 tokens [1]; High compression: simple clip-art or flags with large areas of flat colour — long runs of identical pixels compress to very few tokens [1]; Low compression: photographic images with continuously varying pixel values — few or no repeated adjacent pixels, so little or no reduction in data [1]; Award 1 mark for clear justification linking compression level to presence/absence of repetition [1].
Topic Quiz
Question 1 of 10
You scored
out of 10
Card 1 of 8
Click to reveal definition
🎉
All cards reviewed!
Term
Definition
🎯
Mini Test — 3.1.4 Data Compression
10 questions · 10 marks · 10 minutes
⏱ 10:00
Section A — Multiple Choice [5 marks]
Q1Which type of compression allows the original data to be exactly recovered?
Q2RLE encodes the string "BBBBBBBAA" as:
Q3In Huffman coding, which character gets the shortest code?
Q6State two file formats that use lossless compression and two that use lossy compression.
Mark schemeLossless: any two from PNG, GIF, ZIP, FLAC, BMP (uncompressed) [1]; Lossy: any two from JPEG/JPG, MP3, MP4/MPEG, AAC, WMV [1].
Q7Explain how run-length encoding works, using the example sequence WWWWWWBBB.
Mark schemeRLE replaces consecutive repeated values with a (count, value) pair [1]; WWWWWWBBB becomes (6,W)(3,B) — storing count and value instead of each individual character [1].
Q8Explain the prefix-free property of Huffman codes and why it is important for decoding.
Mark schemePrefix-free means no Huffman code is the prefix (start) of any other code [1]; this is important because when decoding a bit stream, as soon as the bits match a code exactly, the decoder knows the full character has been read — no ambiguity about whether to wait for more bits [1].
Q9A student claims that Huffman coding always produces a smaller file than the original. Give one counter-example where Huffman coding might not reduce file size.
Mark schemeIf all characters appear with equal frequency, Huffman assigns the same code length to all characters — no saving is achieved over fixed-length codes [1]; additionally, the code table must be stored alongside the compressed data, which adds overhead that could make the total larger than the original for very short texts [1].
Q10Give a reason why lossy compression would not be suitable for compressing a medical scan image.
Mark schemeLossy compression permanently removes data from the image — the decompressed image is not identical to the original [1]; for a medical scan, any loss of detail could mean a diagnosis is based on inaccurate data, potentially missing conditions or leading to incorrect treatment — data integrity is critical [1].