Data Compression

Historical Context & Motivation

From the earliest days of telegraphy, engineers have searched for ways to encode messages using fewer symbols. Data compression — the process of reducing the number of bits needed to represent information — is not merely a modern convenience but a foundational problem in information science. As digital media expanded from kilobytes of text to gigabytes of video, the ability to shrink data without losing essential meaning became critical for storage, bandwidth, and cost. Understanding data compression requires appreciating both the mathematical theory behind it and the practical trade-offs that arise when encoding real-world data.

The central question that runs through this history is deceptively simple: How few bits do we truly need to represent a piece of information, and what happens when we discard some of the data to use even fewer? That question divides compression into two families — lossless and lossy — each with distinct guarantees and trade-offs that the AP CSP exam expects you to understand and evaluate.

Core Principles & Definitions

All compression techniques rest on a single insight: most data contains redundancy — patterns, repetitions, or information that is less important to human perception. Compression algorithms identify and exploit that redundancy, replacing it with shorter representations. Before examining specific techniques, it is essential to internalize several foundational concepts that appear repeatedly on the AP CSP exam.

Visualizing Lossless vs. Lossy Compression

Notice the fundamental trade-off: the lossy path achieves a much smaller compressed file (80 KB vs. 350 KB), but the cost is irreversibility. Once data is removed during lossy compression, no decompression algorithm can regenerate it. The lossless path guarantees a perfect round-trip — compress and decompress, and you are back where you started. This is why lossless formats are mandatory for text, code, medical images, and legal documents, while lossy formats are acceptable (and often preferred) for consumer media like photos, music, and streaming video, where tiny perceptual differences go unnoticed.

How Compression Algorithms Work

Run-Length Encoding (RLE)

One of the simplest lossless techniques is run-length encoding (RLE). Instead of storing every individual value, RLE replaces consecutive runs of the same value with a single value and a count. For example, the pixel row WWWWWBBBWW (10 characters) becomes 5W3B2W (6 characters). RLE works exceptionally well on data with long homogeneous runs, such as simple bitmap images or fax transmissions, but offers little benefit on data with high variability like photographs.

Huffman Coding

A more sophisticated lossless strategy is Huffman coding, which exploits statistical redundancy by assigning shorter bit patterns to symbols that occur more frequently and longer patterns to rare symbols. Consider English text: the letter 'E' appears far more often than 'Z,' so giving 'E' a 2-bit code and 'Z' a longer code reduces the total number of bits. Huffman coding constructs a binary tree from symbol frequencies and generates an optimal prefix-free code — no code is the start of another code, so the encoded bitstream can be decoded unambiguously.

Dictionary-Based Compression (LZW)

The Lempel-Ziv-Welch (LZW) algorithm builds a dictionary of recurring substrings as it scans the data. When a substring appears again, the algorithm outputs a short dictionary index instead of the full substring. The GIF image format and the Unix compress utility both use LZW. Its strength lies in adapting to whatever patterns the data contains without prior knowledge of the source.

Lossy Techniques — Perceptual Coding

Lossy algorithms leverage models of human perception. JPEG exploits the fact that the human eye is more sensitive to brightness changes than to color changes, so it stores color information at lower resolution. MP3 uses psychoacoustic models to discard audio frequencies that are masked by louder neighboring frequencies. In both cases, the algorithm throws away data that most people will never notice is missing, achieving compression ratios that are impossible with lossless methods alone.

Compression Techniques in Detail

To build a deeper understanding of how compression operates in practice, it helps to walk through a concrete example of Huffman coding and then visualize how the encoding tree determines the bit assignments for each symbol.

The savings come almost entirely from the most frequent symbol. By giving 'A' a 1-bit code instead of a 3-bit code, we save 2 bits across each of its 5 occurrences, for a total savings of 10 bits. The less frequent symbols (B, R, C, D) retain 3-bit codes, which is the same length as the fixed scheme, so they contribute no additional savings. This illustrates a general principle of Huffman coding: the benefit is proportional to the skewness of the frequency distribution. If all symbols occurred equally often, Huffman coding would offer no improvement over a fixed-length code.

Worked Example: Run-Length Encoding

Consider a simple black-and-white image stored as a grid of pixel values, where 'B' represents a black pixel and 'W' represents a white pixel. Suppose one row of the image is: BBBBBBBWWWWBBBBWWWWWWWWWWBB (26 characters). We will compress this row using run-length encoding and compute the compression ratio.

Lossless vs. Lossy — Strengths & Limitations

Connections to Information Theory & Beyond

Data compression is not an isolated topic — it sits at the intersection of several deep ideas in computer science, including information theory, algorithmic complexity, and network efficiency. Shannon's source coding theorem proves that no lossless compression algorithm can, on average, encode messages using fewer bits per symbol than the entropy of the source. This theoretical floor applies universally — it constrains ZIP just as it constrains any future algorithm yet to be invented.

Compression also has profound implications for the Internet of Things, cloud storage pricing, and sustainability — every byte we avoid transmitting reduces energy consumption in data centers and network infrastructure. As data generation continues to accelerate, the principles you learn in this lesson become even more relevant. Future courses in algorithms, machine learning (which increasingly uses learned compression models), and systems design will all build on these foundations.

Practice Problems

Data Compression — Summary