Data Compression — Lossy, Lossless & RLE

Syllabus & Goals 3 min

Cambridge 1.3 · Data storage and file compression Paper 1 · Computer Systems

By the end of this lesson you can:

1. Explain the purpose of and need for data compression.
2. Explain how lossy (MP3, MP4, JPEG) and lossless compression reduce file size, and choose between them.
3. Carry out run-length encoding (RLE) on text and images, including the flag method, and work out the saving.

Textbook: Chapter 1, §1.3.3–1.3.4 (pp. 34–37)

Recap / Warm-Up 5 min

Last lesson you found that a 45-second stereo clip is over 8 MiB. Files that size are slow to send — so we shrink them first.

Quick starter

How could you write WWWWWWWW (eight W's) more briefly, without losing any information?

Key Concept 14 min

1 · Why compress?

Compression reduces the size of a file. It is needed:

• to save storage space on devices such as an HDD or SSD;
• to reduce the time taken to stream a music or video file;
• to reduce the time taken to upload, download or transfer a file across a network;
• to use less bandwidth — fewer bits to send means a faster transfer;
• to reduce costs — cloud storage is charged by size, and some internet providers charge by data downloaded.

2 · Lossy compression

A lossy algorithm permanently removes data it judges unnecessary. The original file cannot be rebuilt. For example, it may reduce an image's resolution or colour depth, or a sound's sampling rate or resolution. Lossy files are much smaller than lossless ones.

3 · Lossless compression

A lossless algorithm lets all the original data be rebuilt exactly. It is essential where losing any data would be a disaster — a spreadsheet, a text document or a program download.

4 · Run-length encoding (RLE)

• RLE is a lossless, reversible method.
• It shrinks runs of adjacent, identical data (such as repeated colours in an image).
• Each run becomes two values: the number of identical items, then the item's code (e.g. its ASCII code).
• It only helps where there are long runs. With no runs, it can make a file bigger.

The flag method. A string such as cdcdcd has runs of 1, so plain RLE doubles it. So a special flag value (such as 255) is placed before each coded run. Any value without a flag is a single character taken at face value.

Worked Example 12 min

Worked example 1 · RLE on text

Question: compress kkkkkkkmmmmmmmmmmppppqqqqqq using RLE with ASCII codes. Each value needs 1 byte.

1. Count each run of identical characters, left to right.RLE only works on items that are next to each other.
2. Write each run as count, code: 07 107 10 109 04 112 06 113.
3. Original: 27 characters = 27 bytes. Coded: 4 runs × 2 = 8 bytes.
4. Saving = (27 − 8) ÷ 27 × 100 ≈ 70% smaller, with nothing lost.

Worked example 2 · the flag method

Question: compress aaaaaaaaaxyxyxybbbbbbbb. Compare plain RLE with RLE using the flag 255.

1. Runs: 9×a, 1×x, 1×y, 1×x, 1×y, 1×x, 1×y, 8×b — 8 runs in all.
2. Plain RLE: every run is a pair, so 8 × 2 = 16 values.each single letter now costs two bytes instead of one, so short runs waste space.
3. With the flag: runs get 255, count, code; singles are written as they are: 255 09 97 120 121 120 121 120 121 255 08 98 = 12 values.
4. Original 23 bytes → plain RLE 16 bytes → flagged 12 bytes (about 48% smaller than the original).

Worked example 3 · RLE on a black-and-white image

Question: the letter T below is stored as an 8 × 8 grid, 1 byte per pixel (white = 1, black = 0). Compress it with RLE, reading left to right, top row first.

1. Flatten the grid into one long row of 64 pixels, top row first.
2. Count each run: 9W 6B 4W 2B 6W 2B 6W 2B 6W 2B 6W 2B 11W.
3. Using W = 1 and B = 0, the stored values are 9 1, 6 0, 4 1, 2 0, 6 1, 2 0, 6 1, 2 0, 6 1, 2 0, 6 1, 2 0, 11 1.
4. 13 runs × 2 = 26 bytes instead of 64 — about 59% smaller.a real file also has a header, so the true saving is a little less.

Colour images work the same way, but each colour is 3 values (red, green, blue). A row of 8 pixels — 3 red then 5 blue — is 8 × 3 = 24 bytes. RLE stores 3 255 0 0 5 0 0 255: 8 bytes.

RLE as an algorithm

// Run-length encode a string
DECLARE Text : STRING
DECLARE Index, RunLength : INTEGER
DECLARE Current : CHAR
Text ← "kkkkkkkmmmmmmmmmmppppqqqqqq"
Index ← 1
WHILE Index <= LENGTH(Text)
  Current ← MID(Text, Index, 1)
  RunLength ← 0
  WHILE Index <= LENGTH(Text) AND MID(Text, Index, 1) = Current
    RunLength ← RunLength + 1
    Index ← Index + 1
  ENDWHILE
  OUTPUT RunLength, " ", Current
ENDWHILE

text = "kkkkkkkmmmmmmmmmmppppqqqqqq"
i = 0
while i < len(text):
    current = text[i]
    count = 0
    while i < len(text) and text[i] == current:
        count = count + 1
        i = i + 1
    print(count, current)

7 k
10 m
4 p
6 q

Try It Yourself 12 min

📝 Exam Practice 10 min

Recap & Key Terms 3 min

Files are compressed to save storage, speed up streaming and transfer, use less bandwidth and cut costs. Lossy (MP3, MP4, JPEG) removes data for good to make the smallest files. Lossless (RLE) keeps every bit. RLE stores each run as a count and a code; a flag stops single items from doubling in size. That completes Unit 1 — Data representation.

Compression

Reduction of the size of a file by removing repeated or redundant pieces of data; it can be lossy or lossless.

Lossy (file compression)

A method in which parts of the original file cannot be recovered during decompression, e.g. JPEG, MP3.

Lossless (file compression)

A method that allows the original file to be fully restored during decompression, e.g. RLE.

Run-length encoding (RLE)

A lossless technique that stores each run of identical data as the number of items and the item's code.

Perceptual music shaping

Removing sounds the human ear cannot hear, e.g. a softer sound played at the same time as a louder one.

Bandwidth

The maximum rate of transfer of data across a network, in bits per second.

Homework 1 min

Task (≤ 15 min): (a) Compress aaaabbbbbbcc with RLE using ASCII codes (a = 97, b = 98, c = 99). (b) Work out the percentage saving. (c) State whether RLE is lossy or lossless. [4]