Data Compression — Mathematics Knowledge System

Overview

Data compression reduces the number of bits required to represent information. Lossless compression allows perfect reconstruction of the original data; lossy compression allows some distortion in exchange for greater compression. Shannon's source coding theorem establishes the fundamental limit for lossless compression: the average code length per symbol cannot be less than the entropy H(X) bits, and codes can achieve lengths arbitrarily close to H(X). Practical lossless methods include Huffman coding, arithmetic coding, and Lempel-Ziv algorithms. Lossy compression (JPEG, MP3, video codecs) exploits perceptual irrelevance and is governed by rate-distortion theory.

Intuition

Data compression exploits redundancy. In English text, the letter 'e' appears far more often than 'z', so encode 'e' with fewer bits than 'z'. If you know the probability distribution of your data source, the optimal code assigns a codeword of length approximately -log₂ p(x) bits to symbol x — symbols that occur rarely get long codewords, frequent ones get short. This is exactly what Huffman coding does. The source coding theorem says the average code length cannot be less than H(X), but you can get within 1 bit per symbol of that limit with Huffman codes.

Formal Definition

Definition

A source code for X is a mapping C: X → {0,1}*. A prefix-free (instantaneous) code satisfies no codeword is a prefix of another. The expected length of code C is:

L(C) = \sum_{x} p(x) \ell(x)

Expected code length

H(X) \leq L(C^*) < H(X) + 1

Source coding theorem (Huffman bound)

\ell^*(x) = \left\lceil -\log_2 p(x) \right\rceil

Optimal codeword length

\sum_x 2^{-\ell(x)} \leq 1

Kraft inequality (necessary and sufficient for prefix-free code)

Notation

Notation	Meaning
$L(C)$	Expected length of code C
$\ell(x)$	Length of codeword for symbol x
$H(X)$	Shannon entropy — the compression lower bound

Theorems

Theorem 1: Shannon's Source Coding Theorem (Noiseless Coding Theorem)

For any uniquely decodable code C for source X with entropy H(X), L(C) \geq H(X). Moreover, there exists a prefix-free code C^* with H(X) \leq L(C^*) < H(X) + 1.

Theorem 2: Kraft Inequality

A prefix-free (instantaneous) code with codeword lengths \ell_1, \ldots, \ell_n exists if and only if \sum_{i=1}^n 2^{-\ell_i} \leq 1.

Theorem 3: Asymptotic Equipartition Property (AEP)

For i.i.d. source X_1, \ldots, X_n with entropy H(X), -\frac{1}{n} \log p(X_1,\ldots,X_n) \to H(X) in probability. This implies n \cdot H(X) bits suffice to represent most n-symbol sequences.

Worked Examples

1
Optimal lengths: ℓ(a) = ⌈-log₂ 0.5⌉ = 1, ℓ(b) = 2, ℓ(c) = 3, ℓ(d) = 3.
$\ell = (1,2,3,3)$
2
Check Kraft inequality.
$2^{-1} + 2^{-2} + 2^{-3} + 2^{-3} = 0.5 + 0.25 + 0.125 + 0.125 = 1$
3
Compute expected length.
$L = 0.5(1) + 0.25(2) + 0.125(3) + 0.125(3) = 1.75 \text{ bits}$
4
Compare to entropy H(X) = 1.75 bits (computed separately).
$L = H(X) = 1.75 \Rightarrow \text{code is optimal}$

✓ Answer

The code (a→0, b→10, c→110, d→111) is optimal, achieves exactly H(X) = 1.75 bits.

Practice Problems

Easyfill in blank

A fair coin is flipped 1000 times. Approximately how many bits are needed to losslessly store the sequence?

Mediumapplication

A source emits symbols with probabilities {0.4, 0.35, 0.15, 0.1}. Compute H(X) and the efficiency of a 2-bit uniform code (which uses 2 bits per symbol regardless of probability).

Common Mistakes

Common Mistake

Thinking you can always compress data to fewer bits than its entropy.

Shannon's source coding theorem makes this impossible. No lossless code can achieve expected length below H(X).

Common Mistake

Assuming applying a compression algorithm twice doubles the compression ratio.

After the first pass, the compressed file has entropy close to 1 bit/bit (it looks random). Applying compression again gains virtually nothing.

Quiz

Historical Background

Morse code (1838) was an early example of variable-length coding exploiting symbol frequencies. Shannon's 1948 paper gave the first rigorous proof that entropy is the fundamental limit for lossless compression. Huffman's 1952 algorithm provided a practical optimal prefix-free code. Ziv and Lempel's 1977-78 algorithms (LZ77, LZ78) gave adaptive universal codes that approach entropy without prior knowledge of the source distribution, enabling formats like gzip and PNG.

1838
Morse code introduces frequency-based variable-length encoding.
Samuel Morse
1948
Shannon's source coding theorem establishes entropy as the compression limit.
Claude Shannon
1952
Huffman devises the optimal prefix-free code algorithm.
David Huffman
1977
Lempel and Ziv publish LZ77 adaptive compression algorithm (used in gzip).
Abraham Lempel, Jacob Ziv
1984
Terry Welch extends LZ to LZW (used in GIF, TIFF).
Terry Welch

Summary

Shannon's source coding theorem: the minimum expected code length for lossless compression is H(X) bits per symbol.
Optimal codeword lengths are ℓ*(x) = ⌈-log₂ p(x)⌉ bits; frequent symbols get short codes, rare symbols get long codes.
Huffman coding achieves between H(X) and H(X)+1 bits/symbol; arithmetic coding approaches H(X) arbitrarily closely.
Lossless compression is bounded by entropy; lossy compression (JPEG, MP3) trades distortion for lower bit rates, governed by rate-distortion theory.

References

PaperShannon, C.E. (1948). A Mathematical Theory of Communication. Bell System Technical Journal.
BookCover, T. and Thomas, J. (2006). Elements of Information Theory, 2nd ed. Wiley. Ch. 5.
WebsiteWikipedia — Data compression