SLIDE 1
CSZone.co.uk
Click to advance · Arrow keys also work
CAIE 9618 · Paper 3 · Topic 3.1.4

Data
Compression

Lossless vs Lossy · RLE · Huffman Coding · JPEG · MP3 · Benefits

CSZone Cambridge International AS & A Level Computer Science 9618
Why Compress Data?

Reducing File Size

Compression reduces the number of bits needed to represent data. Benefits: faster transmission over networks, less storage space required, lower bandwidth costs.
Lossless
ORIGINAL DATA FULLY RECOVERABLE
Compressed data can be decompressed to get the exact original. No data is lost or altered. Required when every bit matters.
Examples: RLE, Huffman coding, ZIP, PNG, FLAC
Used for: text files, executables, medical images, spreadsheets
Lossy
SOME DATA PERMANENTLY DISCARDED
Compression removes data the human eye or ear typically cannot perceive. Cannot recover original once compressed. Achieves much higher compression ratios.
Examples: JPEG, MP3, AAC, H.264 video
Used for: photos, music, video streaming
Run-Length Encoding (RLE)

Count Consecutive Repeated Values

RLE replaces a run of identical values with a (count, value) pair. Highly effective for data with long repeated sequences — e.g. bitmap images with large areas of the same colour.
Original pixel row (W=White, B=Black):
W
W
W
W
W
B
B
B
W
W
→
5W
3B
2W
10 values → 6 values (3 pairs) — 40% reduction
BEST FOR
Simple graphics with large blocks of colour (logos, icons, fax documents). Performs poorly on photographs (few repeating runs).
CAUTION
Can actually INCREASE file size if few repeating sequences exist — each pair takes 2 values instead of 1.
Huffman Coding

Frequent Characters Get Shorter Codes

Huffman coding assigns variable-length binary codes to characters — more frequent characters get shorter codes. A frequency tree is built bottom-up, then codes read from root to leaf.
EXAMPLE: encode "AABABCA"
CharFreqCodeBits
A401 bit
B2102 bits
C1112 bits
Fixed 2-bit encoding: 7×2 = 14 bits
Huffman: 4×1 + 2×2 + 1×2 = 10 bits → 28% saving
PROPERTIES
Lossless — perfect reconstruction possible
Codes are prefix-free (no code is a prefix of another)
The code tree must be transmitted with the data
Used in DEFLATE (ZIP), PNG, PDF compression
LIMITATION
Tree must accompany compressed data — small overhead. Less effective when all characters have similar frequency.
Lossy Compression Examples

JPEG (Images) & MP3 (Audio)

JPEG — IMAGES
Divides image into 8×8 pixel blocks
Applies Discrete Cosine Transform (DCT) to convert spatial to frequency domain
High-frequency components (fine detail) discarded — human eye less sensitive to them
Quality setting controls how much is discarded
Not suitable for medical/legal images requiring exact accuracy
MP3 — AUDIO
Based on perceptual coding — human ear model
Removes sounds outside human hearing range (below 20Hz / above 20kHz)
Masking effect: quiet sounds immediately after a loud sound are inaudible and removed
Typical compression 10:1 ratio with little perceptible quality loss
Bit rate (128/256/320 kbps) controls quality vs size
Exam Practice

Cambridge-style questions

Question 1
A user wants to compress a photograph to upload to a website, and separately wants to compress a text document to email. For each file, state whether lossless or lossy compression is more appropriate, and give a reason. [4]
1+1
Photograph → Lossy (e.g. JPEG). A photograph can tolerate slight loss of detail imperceptible to the human eye — a much higher compression ratio is achievable, making the file faster to upload.
1+1
Text document → Lossless (e.g. ZIP). Every character in a text document is meaningful — even a single character changed would corrupt the document. Lossless compression guarantees perfect recovery of the original file.
Common Mistakes

Don't lose easy marks

1
Saying "MP3 just removes silence" — MP3 uses perceptual coding (psychoacoustic model) to remove inaudible sounds including masking effects. "Just removes silence" is too simplistic and won't score marks.
2
Claiming "RLE always reduces file size" — RLE can INCREASE file size when the data has no long runs of repeated values (e.g. a photograph). A mark-scheme question about disadvantages of RLE expects this answer.
3
Confusing the code tree and the compressed data in Huffman — the compressed bit stream alone is useless without the code tree. In an exam: always mention that the tree/dictionary must be stored or transmitted alongside the compressed data.
Topic Summary — 3.1.4

What You Need to Know

LOSSLESS
Exact original recoverable. RLE: (count, value) pairs — good for repeated runs. Huffman: frequent chars get shorter codes — tree must be stored with data.
LOSSY
Discards imperceptible data permanently. JPEG: DCT + discard high-frequency components. MP3: perceptual coding removes inaudible sounds, masking effect.
WHEN TO USE WHICH
Lossless: text, executables, medical images, spreadsheets — where every bit matters.
Lossy: photos, music, video — where human perception limits what's needed.
Benefits of compression: reduced file size, faster upload/download, lower storage cost, lower bandwidth usage.
CSZone

Next Video

3.2.1
Communication Protocols
TCP/IP · OSI Model · HTTP/S · FTP · SMTP
Head to CSZone.co.uk for the complete worksheet, quiz, and interactive tools