Chapter 1.3: Compression

AS Level Computer Science (9618)

📚 Learning Objectives

Show understanding of the need for and examples of the use of compression
Show understanding of lossy and lossless compression and justify the use of a method in a given situation
Show understanding of how a text file, bitmap image, vector graphic and sound file can be compressed, including the use of run-length encoding (RLE)

1. The Need for Compression

📖 Definition

Compression is the process of reducing the size of a file so that it takes up less space on secondary storage.

Why Do We Need Compression?

Maximise storage: Store more data on devices with limited capacity (phones, tablets)
Minimise transfer time: Reduce time for uploading, downloading, or streaming data
Save bandwidth: Conserve network resources and reduce data transmission costs
Improve performance: Enable faster loading times for websites and applications
Efficient backup: Store more backups in the same storage space

⚠️ Key Point

Larger files require larger storage capacity
Larger files result in lower transmission/download rates
Compression reduces file size while maintaining quality as much as possible

2. Lossy vs Lossless Compression

2.1 Lossy Compression

📖 Definition

Lossy compression is a compression method where data is permanently removed to reduce file size. The process is irreversible.

Data is permanently lost during compression
Original file can never be fully recovered
Achieves high compression ratios (up to 90% reduction)
Quality is reduced but often acceptable for human perception
Best for multimedia files where small quality loss is acceptable

Example: Lossy Compression in Photographs

Similar colours are grouped together
Total number of colours is reduced
Human eye often cannot perceive subtle colour changes
Result: Smaller file with acceptable visual quality

2.2 Lossless Compression

📖 Definition

Lossless compression is a compression method where data is encoded to reduce file size, but no information is lost. The process is reversible.

No data is lost during compression
Original file can be perfectly reconstructed
Lower compression ratios (typically 50-80% reduction)
Original quality is completely maintained
Essential for files where data integrity is critical

2. Lossy vs Lossless (Continued)

Feature	Lossy Compression	Lossless Compression
Data Loss	Some data permanently removed	No data lost
Reversibility	Irreversible	Fully reversible
Compression Ratio	High (up to 90% reduction)	Lower (typically 50-80%)
Quality	Reduced quality	Original quality maintained
Best For	Multimedia (images, audio, video)	Text, documents, executables
Examples	JPEG, MP3, MP4	PNG, ZIP, RLE, Huffman

💡 Exam Tip: When to Use Which Method?

Use lossy when: Small quality loss is acceptable (photos, music, videos)
Use lossless when: Any data loss would be disastrous (text files, programs, documents)
Always justify your choice based on the file type and requirements

🧠 Memory Trick

Lossy = You LOSE data permanently
Lossless = You LOSE LESS (actually nothing!)

3. Run-Length Encoding (RLE)

📖 Definition

Run-Length Encoding (RLE) is a form of lossless data compression that condenses identical consecutive elements into a single value with a count.

How RLE Works

Repeating string is encoded as two values
First value: Number of identical data items in the run (count)
Second value: Code of the data item (e.g., ASCII code or colour value)

RLE = Count + Value

⚠️ Important Limitation

RLE is only effective where there are long runs of repeated units/bits
If data has few repeated sequences, RLE may actually increase file size
Works best for images with large blocks of the same colour
Works poorly for photographs with many different colours

3.1 RLE with Text Data

📝 Example: Compressing Text

Original string: 'aaaaabbbbccddddd'

Original size: 16 characters = 16 bytes
RLE encodes as: 5a4b2c5d (or using ASCII: 5,97,4,98,2,99,5,100)
Compressed size: 8 bytes (4 counts + 4 ASCII values)
Compression ratio: 50% reduction

4. RLE with Images

4.1 Black and White Images

📝 Example: Letter F in 8×8 Grid

White square = value 1
Black square = value 0
Original storage: 64 bytes (8 × 8 pixels × 1 byte)
RLE encodes runs of consecutive same colours
Compressed storage: 30 bytes
Compression ratio: 53% reduction

4.2 Multi-Colour Images

For images with multiple colours, RLE stores RGB values along with the count:

Colour	Red	Green	Blue
Black	0	0	0
White	255	255	255
Red	255	0	0
Green	0	255	0

RLE Encoding Example:

10 0 0 0 = Ten black pixels (count=10, R=0, G=0, B=0)
5 255 0 0 = Five red pixels (count=5, R=255, G=0, B=0)
3 0 255 0 = Three green pixels (count=3, R=0, G=255, B=0)

❌ Common Mistake

Problem: RLE stores colour + count
If no repeated colours, each pixel needs count=1
Example: Red-Green-Blue becomes Red-1 Green-1 Blue-1
Result: Larger file than original!

5. Huffman Coding

📖 Definition

Huffman coding is a lossless data compression algorithm that assigns variable-length codes to characters based on their frequency of occurrence.

How Huffman Coding Works

Analyses data to find most frequently used characters
Most frequent characters get the shortest codes
Least frequent characters get the longest codes
Original stream of bytes becomes a compact bit stream
No single code is a prefix of another (allows unambiguous decoding)

Example: Text with 8 Different Letters

Standard encoding: Each character needs 3 bits (for 8 values)
Huffman assigns variable-length codes:
Most frequent character → code 00 (2 bits)
Least frequent character → code 11110 (5 bits)
Result: Overall file size is reduced

Feature	Fixed-Length Code	Huffman Code
Code Length	Same for all characters	Variable based on frequency
Most Frequent Char	Same length as others	Shortest code
Compression	No compression	Efficient compression

6. File Compression Formats

6.1 MP3 (MPEG-3) - Audio Compression

Uses audio compression to reduce file size
Reduces file size by approximately 90%
Example: 80 MB CD track → 8 MB MP3 file
Uses lossy compression (data permanently lost)
Used on: MP3 players, computers, smartphones, streaming services

🌟 Perceptual Music Shaping

MP3 removes sounds humans cannot perceive:
Frequencies outside hearing range: Below 20 Hz or above 20,000 Hz
Masked sounds: Softer sounds hidden by louder ones are removed
Less noticeable details: Subtle audio details are simplified
Result: Smaller file without noticeable quality loss

6.2 MP4 (MPEG-4) - Multimedia Format

More versatile than MP3 (not just audio)
Can store: Music, videos, photos, animations, subtitles
Primary use: Streaming videos over the Internet
Uses both lossy and lossless methods
Maintains high quality without noticeable loss

7. JPEG and Image Formats

7.1 JPEG - Lossy Image Compression

Most common format for photographic images
Uses lossy compression
Reduces raw bitmap by factor of 5 to 15 times
Groups similar colours together to reduce file size
Original file cannot be reconstructed after compression

⚠️ Important JPEG Facts

Always keep backup of important originals
Each edit and re-save causes more quality loss
Compression level can be adjusted (higher = smaller = lower quality)
Not suitable for images with sharp edges (text, logos, diagrams)

7.2 PNG - Lossless Image Compression

Uses lossless compression
Preserves sharp edges and transparency
Best for: Screenshots, logos, diagrams, graphics with text
Original quality fully maintained
Larger file size than JPEG for photographs

💡 Choosing the Right Image Format

Photographs: JPEG (lossy) — smaller files, good quality
Screenshots: PNG (lossless) — preserves sharp text
Logos/Diagrams: PNG (lossless) — clean edges needed
Simple graphics: RLE effective if large colour blocks
Complex photos: RLE NOT effective (too many colours)

8. Vector Graphics Compression

8.1 What are Vector Graphics?

Store images as mathematical descriptions (shapes, lines, curves)
Not a grid of pixels like bitmaps
Can be scaled without quality loss
File size is typically smaller than bitmaps for simple graphics

8.2 SVG (Scalable Vector Graphics)

🌟 SVG Compression

SVG files are defined in text files using XML format
Being text-based allows effective compression:
Text compression algorithms: Similar to compressing any text file
gzip compression: Creates SVGZ format for web
Metadata removal: Simplifying XML structure
Limited compression potential compared to bitmaps
Already uses efficient mathematical representations

File Type	Compression Method	Effectiveness
Text Files	Lossless (Huffman, ZIP)	High — patterns detected
Bitmap Images	Lossy (JPEG) or Lossless (PNG)	Variable — depends on content
Vector Graphics	Lossless (text compression)	Limited — already efficient
Sound Files	Lossy (MP3) or Lossless (FLAC)	High — removes inaudible data
Video Files	Lossy (MP4)	Very High — temporal redundancy

9. Exam-Style Questions (1-5)

1. Photographs are compressed before they are uploaded to a web server. Customers download photographs from this web server. Explain reasons why compressing photographs will benefit customers. [4 marks]

Answer:

Customers can download photographs in less time
Photographs take less bandwidth to transfer
Photographs take less storage space on customer's device
Customers can store more images on their devices

2. An image can be compressed using RLE. Explain reasons why RLE may not reduce the file size of a bitmap image. Give one example in your answer. [3 marks]

Answer:

RLE stores a colour and count for consecutive pixels
An image may not have many sequences of the same colour
RLE would need to store each colour with count 1, adding data
Example: Red-Green-Blue becomes Red-1 Green-1 Blue-1 (larger than original)

3. When storing music tracks in a computer, MP3 format is used. This reduces file size by about 90%. Explain how music quality is apparently retained. [4 marks]

Answer:

MP3 uses perceptual music shaping
Removes frequencies outside human hearing range (below 20 Hz or above 20,000 Hz)
Removes masked sounds (softer sounds hidden by louder ones)
Parts of music removed without affecting perceived quality

4. Explain the difference between lossy and lossless compression. Give an example of when each would be appropriate. [4 marks]

Answer:

Lossy: Data permanently removed; original cannot be recovered; high compression ratio
Lossless: No data lost; original can be perfectly reconstructed; lower compression ratio
Lossy example: Photographs (JPEG), music (MP3), video (MP4)
Lossless example: Text documents, spreadsheets, program files

5. A bitmap image contains the following pattern of pixels (W = White, B = Black):
WWWWWWWWWWWWBBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWW
Show how this would be encoded using Run-Length Encoding (RLE). [3 marks]

Answer:

RLE encoding: 12W2B12W3B20W
12 Ws, 2 Bs, 12 Ws, 3 Bs, 20 Ws
Original: 49 characters → RLE: 14 characters

9. Exam-Style Questions (6-10)

6. Describe how Run-Length Encoding (RLE) compresses data. Explain why RLE would be suitable for compressing a screenshot of a document with mostly white background. [4 marks]

Answer:

RLE stores consecutive identical values as count + value pairs
Instead of storing each pixel individually, stores how many in a row
Screenshot has large areas of white pixels (background)
These long runs compress very efficiently with RLE

7. A text file contains the string: AAAABBBCCDAA
Calculate the size of the original string and the RLE compressed version. Show your working. [4 marks]

Answer:

Original: 12 characters × 1 byte = 12 bytes
RLE encoding: 4A3B2C1D2A
RLE has 4 count values + 5 character values = 9 values
Compressed size = 9 bytes (or 8 bytes if we use: 4,3,2,1,2 and A,B,C,D,A)

8. Explain two differences between JPEG and PNG image formats. State when each format would be the better choice. [4 marks]

Answer:

JPEG uses lossy compression; PNG uses lossless compression
JPEG cannot preserve transparency; PNG supports transparency
JPEG better for: Photographs, complex images with many colours
PNG better for: Screenshots, logos, diagrams, images with text

9. A company wants to store high-quality master copies of photographs for professional printing. Should they use lossy or lossless compression? Justify your answer. [3 marks]

Answer:

Should use lossless compression
Professional printing requires highest quality with no data loss
Lossy compression would permanently remove image data
Any quality loss would be visible in professional prints

10. Explain how Huffman coding achieves compression. Why might Huffman coding be more effective than RLE for compressing a text document? [4 marks]

Answer:

Huffman assigns shorter codes to more frequent characters
Assigns longer codes to less frequent characters
RLE is only effective for consecutive repeated characters
Text documents rarely have long runs of identical characters
Huffman works well even without consecutive repetitions

10. Summary & Key Takeaways

📌 Chapter Summary

Compression reduces file size to save storage and reduce transmission time
Lossy compression — data permanently removed; irreversible; high compression ratio; for multimedia
Lossless compression — no data lost; reversible; lower compression ratio; for text/documents
RLE stores consecutive identical values as count + value pairs
RLE only effective for data with long runs of repeated values
Huffman coding assigns shorter codes to more frequent characters
MP3 uses perceptual music shaping (90% compression)
MP4 is a multimedia container for video, audio, animations
JPEG compresses photographs (lossy, 5-15x reduction)
PNG preserves quality and transparency (lossless)

🧠 Quick Reference Table

Scenario	Best Compression	Reason
Photographs	JPEG (lossy)	Similar colours grouped, small loss acceptable
Screenshots	PNG (lossless)	Sharp edges must be preserved
Music files	MP3 (lossy)	Removes inaudible frequencies
Text documents	ZIP/Huffman (lossless)	Any data loss corrupts file
Simple graphics	RLE (lossless)	Long runs of same colour

💡 Final Exam Tips

Always justify your choice of compression based on file type
RLE is only effective with long sequences of repeated data
MP3 uses perceptual music shaping (frequency range + masking)
JPEG is irreversible — always keep backup of originals
Be able to calculate RLE encoding and compression ratios