Data Compression: Lossy vs Lossless (RLE)

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:

1. Reduces Secondary Storage Consumption: More files, photos, and applications can fit on a solid-state drive, hard drive, or memory card.
2. Accelerates Transmission and Download Speeds: Smaller files take less time to transfer across the internet or local networks.
3. Conserves Network Bandwidth: Lower bitrates reduce network congestion and reduce mobile data consumption.
4. 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

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:

1. RLE on Text Strings

Consider an uncompressed 20-character string:

AAAAAABBBBBCCCCCCCCD

• A run of 6 'A's: 6A
• A run of 5 'B's: 5B
• A run of 8 'C's: 8C
• A 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.