# Data Compression: Lossy vs Lossless (RLE)

- **Track:** Cambridge IGCSE™ Computer Science (0478 / 0984) (CAMBRIDGE IGCSE 0478)
- **Module:** Section 1: Data Representation
- **Estimated Duration:** 15 minutes
- **Access:** Open Theory + Free Practice

---

## Theory & Conceptual Background

As digital media resolutions, audio fidelity, and software complexities increase, file sizes expand rapidly. Uncompressed files consume excessive secondary storage and require prolonged transmission times over computer networks.
Data compression is the process of encoding data using fewer bits than the original representation.

Learning Objectives
Explain why data compression is necessary for storage and transmission.Compare and contrast Lossy and Lossless compression techniques.Evaluate scenarios to select the appropriate compression method.Trace and calculate Run-Length Encoding (RLE) for text and bitmap images.

Why Is Data Compression Needed?
Compressing files provides critical practical advantages:
Reduces Secondary Storage Consumption: More files, photos, and applications can fit on a solid-state drive, hard drive, or memory card.Accelerates Transmission and Download Speeds: Smaller files take less time to transfer across the internet or local networks.Conserves Network Bandwidth: Lower bitrates reduce network congestion and reduce mobile data consumption.Prevents Web and Streaming Latency: Video and audio streaming services can deliver smooth playback without frequent buffering delays.

Lossy vs Lossless Compression
Compression methods fall into two distinct categories:
1. Lossy Compression
How It Works: Algorithms analyze data and permanently discard information deemed redundant or imperceptible to human sensory organs:In Audio (e.g. MP3): Frequencies outside standard human hearing ($20\text{ Hz} - 20,000\text{ Hz}$) and quieter sounds masked by louder simultaneous sounds are discarded (psychoacoustics).In Images (e.g. JPEG): Subtle colour gradations that human eyes cannot differentiate are averaged together or removed.Key Characteristic: The original file cannot be reconstructed bit-for-bit. Once compressed, discarded data is lost forever.Advantages: Achieves very high compression ratios (often reducing file sizes by $80\% - 90\%$).Use Cases: Photographs (JPEG), streaming music (MP3/AAC), internet video (MP4/H.264).Restrictions: Never use lossy compression on executable programs, text documents, or databases, where losing even a single character or binary bit will cause fatal syntax errors or record corruption.
2. Lossless Compression
How It Works: Algorithms identify and exploit repeating patterns and statistical redundancies within data without discarding any information.Key Characteristic: The original file can be reconstructed exactly bit-for-bit identical to the original uncompressed data.Advantages: Zero loss of data or quality.Disadvantages: Yields lower compression ratios compared to lossy techniques.Use Cases: Computer software / executables (.exe), source code, word documents, spreadsheets, financial databases, medical imaging where diagnostic accuracy is paramount.Common Formats: PNG (graphics), ZIP / RAR (archives), FLAC (lossless audio).

Comparison Table

  
    FeatureLossy CompressionLossless Compression
    Data RetentionPermanently discards redundant data.Retains all original data; zero data lost.ReversibilityIrreversible (cannot recover original).Fully reversible (exact bit-for-bit reconstruction).Compression RatioVery high (typically $80\% - 95\%$).Moderate (typically $30\% - 60\%$).Effect on QualitySlight loss of quality / fidelity.No loss of quality.Common FormatsJPEG, MP3, MP4PNG, ZIP, FLAC, GIFSuitable ForWeb images, streaming audio/video.Executables, text files, databases, code.
  

Run-Length Encoding (RLE)
Run-Length Encoding (RLE) is a classic lossless data compression algorithm.
How RLE Works
RLE identifies runs—consecutive sequences of the same data value—and stores them as a pair consisting of the run count and the data value:
$$\text{Consecutive Data} \longrightarrow (\text{Count}, \text{Value})$$
1. RLE on Text Strings
Consider an uncompressed 20-character string:
AAAAAABBBBBCCCCCCCCD
A run of 6 'A's: 6AA run of 5 'B's: 5BA run of 8 'C's: 8CA single 'D': 1D
Compressed representation: 6A5B8C1D
Original length: 20 bytes (20 ASCII characters).Compressed length: 8 bytes (8 characters).Storage reduction: $\frac{20 - 8}{20} = 60\%$ compression.
2. RLE on Bitmap Graphics
Monochrome or simple graphic images with large blocks of uniform background colour compress exceptionally well with RLE.
Imagine a $10 \times 1$ pixel row of a black-and-white icon (W = White, B = Black):
WWWWBBBBWW
Using RLE: 4W4B2W (stores 3 pairs instead of 10 separate pixel values).
When Does RLE Fail?
RLE depends on consecutive repetitions. If data contains frequent variations with little or no repetition, RLE can actually increase the file size!
For example, the 6-character string:
ABCDEF
Encoded with RLE:
1A1B1C1D1E1F
The file size doubled from 6 characters to 12 characters! This demonstrates why compression algorithms must be chosen based on the characteristics of the data being stored.
Written practice and self-review
A mobile digital media service streams 4K video movies over cellular networks, but distributes its operating system security updates via downloadable installer packages.
Justify why lossy compression is suitable for the streaming movies, whereas lossless compression is required for the operating system security updates.
Write an explanation before checking the theory. Check that each claim answers the question, uses the correct concept and explains why it applies. Discuss uncertain points with a teacher. The structured exercise below checks specific facts; it does not automatically mark this explanation.

---

## Interactive Exercises & Autotest Specifications

### Exercise 1: Exam-Style Check: Run-Length Encoding (RLE) Mechanics (Multiple choice, 25 XP)

**Instructions:**
Which type of data compression MUST be used when compressing an executable computer program or medical text database, and why?

**Options:**
- **A**: Lossy compression, because it achieves the highest compression ratio regardless of data loss.
- **B**: Run-Length Encoding on lossy audio streams.
- **C**: No compression is ever permitted on files larger than 1 MiB.
- **D**: Lossless compression, because the exact original data must be reconstructed bit-for-bit without any loss of code or values.


**Autotest Expectations:**
- **Correct option selected**: `selection_match` -> Expected: `b`

### Exercise 2: Exam-Style Question: Run-Length Encoding (RLE) Tracing (Fill in blank, 35 XP)

**Instructions:**
An uncompressed monochrome image row consists of the following **16 pixels** (where **W** = White and **B** = Black):

`WWWWWWWWBBBWWWWW`

1. Write the Run-Length Encoded (RLE) string for this sequence in the format `CountValueCountValue...` (for example, `4W2B`): [blank_1]
2. If a different row of 10 pixels is encoded as `2W5B3W`, how many total **Black** pixels are in that row? [blank_2]


**Starter Code:**
```text
{"word_bank":["8W3B5W","5","8W3B4W","8W2B5W","3","6","16"],"template":"1. RLE string: [blank_1]\n2. Black pixels count: [blank_2]","prompt":"Exam-Style Question: Run-Length Encoding (RLE) Tracing","blanks":[{"id":"blank_1"},{"id":"blank_2"}]}
```

**Autotest Expectations:**
- **RLE encoded string and black pixel count**: `text_exact` -> Expected: `{"blank_1":"8W3B5W","blank_2":"5"}`

### Exercise 3: Application: Check the reasoning (Fill in blank, 30 XP)

**Instructions:**
Work out each answer before submitting. Software installer requiring exact recovery: lossy or lossless? A photograph can sacrifice some detail: lossy or lossless? RLE stores each long repeated run using a value and a what?


**Starter Code:**
```text
{"prompt":"Application: Check the reasoning","template":"1. Software installer requiring exact recovery: lossy or lossless? [blank_1]\n2. A photograph can sacrifice some detail: lossy or lossless? [blank_2]\n3. RLE stores each long repeated run using a value and a what? [blank_3]","blanks":[{"id":"blank_1"},{"id":"blank_2"},{"id":"blank_3"}],"word_bank":["lossless","lossy","count","frequency","parity","index"]}
```