Chapter 19: Data Compression

Part VII: Modern Applications

Lossless vs Lossy Compression

Shannon's source coding theorem establishes the fundamental limit: a source with entropy \(H\) bits per symbol cannot be compressed below \(H\)bits per symbol without information loss. Practical algorithms approach this limit.

Lossless

Perfect reconstruction. Limited to removing statistical redundancy. Examples: ZIP, PNG, FLAC.

Lossy

Exploits perceptual limits. Rate-distortion tradeoff. Examples: JPEG, MP3, H.265 video.

Lempel-Ziv: LZ77 & LZ78

Abraham Lempel and Jacob Ziv (1977, 1978) introduced universal compression algorithms that adapt to the source without prior statistics. The Lempel-Ziv theorem guarantees asymptotic optimality: for ergodic sources, LZ achieves the entropy rate.

LZ77: Sliding Window

Maintains a sliding window of past data. Encodes each new symbol as a (offset, length, next-char) triple referencing the best match in the window.

"abracadabra" → (0,0,a),(0,0,b),(0,0,r),(3,1,c),(5,1,d),(7,4,∅)

DEFLATE (used in ZIP and PNG) combines LZ77 with Huffman coding — first remove repetition with LZ77, then encode the resulting tokens with static Huffman codes. Used in every ZIP file and PNG image.

JPEG: DCT + Quantization

JPEG exploits the human visual system's greater sensitivity to low-frequency information. The pipeline:

Block division: 8×8 pixel blocks
DCT: Discrete Cosine Transform maps spatial to frequency domain
Quantization: Divide DCT coefficients by a quality-dependent matrix (lossy step)
Entropy coding: Zigzag scan + run-length encoding + Huffman

\( F(u,v) = \frac{2}{N}\sum_{x=0}^{N-1}\sum_{y=0}^{N-1} f(x,y) \cos\!\left[\frac{(2x+1)u\pi}{2N}\right]\cos\!\left[\frac{(2y+1)v\pi}{2N}\right] \)

MP3 & Video Codecs

MP3 uses a psychoacoustic model to identify audio components below the threshold of audibility — masking effects from nearby louder sounds — and allocates fewer bits (or none) to inaudible components. At 128 kbps, roughly 90% of the original audio data is discarded, yet most listeners perceive minimal quality loss.

Modern video codecs (H.265/HEVC, AV1, H.266/VVC) achieve 50–60× compression over raw video through:

Intra-frame: DCT/integer transforms within each frame (like JPEG)
Inter-frame: Motion compensation — encode only differences between frames
Entropy coding: CABAC (Context-Adaptive Binary Arithmetic Coding)

Python: LZ77 Implementation & Analysis

Implement LZ77 from scratch, compress different data types (English text, repetitive, random, binary), and compare compression ratios with Shannon entropy limits.

Python

script.py172 lines

import numpy as np
import matplotlib
matplotlib.use('Agg')
import matplotlib.pyplot as plt
import math

# ── Simple LZ77 implementation ────────────────────────────────────────────────
def lz77_compress(data, window_size=255, lookahead_size=15):
    """
    LZ77 compression. Returns list of (offset, length, next_char) tuples.
    offset: distance back in window, length: match length, next_char: next byte
    """
    tokens = []
    i = 0
    while i < len(data):
        best_offset = 0
        best_length = 0
        # Search window
        window_start = max(0, i - window_size)
        window = data[window_start:i]
        lookahead = data[i:i + lookahead_size]
        # Find longest match
        for length in range(min(lookahead_size, len(lookahead)), 0, -1):
            substr = lookahead[:length]
            pos = window.rfind(substr)
            if pos != -1:
                best_offset = len(window) - pos
                best_length = length
                break
        next_char = data[i + best_length] if i + best_length < len(data) else ''
        tokens.append((best_offset, best_length, next_char))
        i += best_length + 1
    return tokens

def lz77_ratio(text):
    """Compute LZ77 compression ratio."""
    tokens = lz77_compress(text)
    # Each token: offset (1 byte), length (1 byte), char (1 byte) = 3 bytes
    # vs original 1 byte per char
    compressed_bytes = len(tokens) * 3
    original_bytes   = len(text)
    return original_bytes / compressed_bytes if compressed_bytes > 0 else 1.0

# ── Test data types ────────────────────────────────────────────────────────────
test_data = {
    'English text':
        "the quick brown fox jumps over the lazy dog the fox ran quickly through the forest "
        "information theory is the mathematical study of the quantification of information "
        "shannon entropy measures the average information content of a message source",
    'Repetitive data':
        "abcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabcabc"
        "xyzxyzxyzxyzxyzxyzxyzxyzxyzxyzxyzxyzxyzxyzxyzxyzxyzxyz",
    'Random-like data':
        "qzxmwpkrtnvbyfjdslahgeoiucqzxmwpkrtnvbyfjdslahgeoiucmwpkrjxq"
        "bzfytqnlmprwvdkshaogjcxeqiutnbfzylwmokrpvdsehajcqginxtbwfzymlu",
    'Binary zeros':
        "0" * 150,
    'Mixed source code':
        "def entropy(probs): return -sum(p*math.log2(p) for p in probs if p>0) "
        "import numpy as np; x = np.zeros(100); y = np.linspace(0,1,100) "
        "class Channel: def capacity(self): return self.bandwidth * math.log2(1 + self.snr)",
}

def shannon_entropy_bits(text):
    """Shannon entropy of the text in bits per character."""
    from collections import Counter
    counts = Counter(text)
    n = len(text)
    return -sum((c/n) * math.log2(c/n) for c in counts.values())

print("=== LZ77 Compression Analysis ===")
print(f"{'Data type':<20} {'Length':>6} {'LZ77 ratio':>11} {'Entropy (b/c)':>13} {'Tokens':>7}")
print("-" * 65)

lz77_ratios = []
entropies   = []
names       = []
for name, text in test_data.items():
    ratio = lz77_ratio(text)
    H = shannon_entropy_bits(text)
    tokens = lz77_compress(text)
    lz77_ratios.append(ratio)
    entropies.append(H)
    names.append(name)
    print(f"{name:<20} {len(text):>6} {ratio:>11.2f}x {H:>13.3f} {len(tokens):>7}")

print()
print("Note: LZ77 ratio > 1 means compression succeeded (output smaller than input)")

# ── LZ77 on English text: show tokens ────────────────────────────────────────
sample = "abracadabra abracadabra information"
tokens = lz77_compress(sample)
print()
print(f"LZ77 tokens for '{sample}':")
for i, (off, length, ch) in enumerate(tokens[:10]):
    print(f"  Token {i:2d}: offset={off}, length={length}, next='{ch}'")
if len(tokens) > 10:
    print(f"  ... ({len(tokens)} total tokens)")
original_size = len(sample)
compressed_size = len(tokens) * 3
print(f"  Original: {original_size} bytes, Compressed: {compressed_size} bytes, Ratio: {original_size/compressed_size:.2f}x")

# ── Theoretical: entropy vs compression ratio ─────────────────────────────────
print()
print("Shannon entropy sets the theoretical limit for lossless compression:")
for name, H in zip(names, entropies):
    theoretical_ratio = 8 / H if H > 0 else float('inf')  # bits/char to bytes
    print(f"  {name}: H = {H:.2f} bits/char, theoretical max ratio = {theoretical_ratio:.2f}x")

# ── Plotting ──────────────────────────────────────────────────────────────────
fig, axes = plt.subplots(1, 3, figsize=(15, 5))
fig.patch.set_facecolor('#0a0a1a')

# Plot 1: LZ77 ratios by data type
ax1 = axes[0]
colors_bar = ['#818cf8', '#a5b4fc', '#6366f1', '#4338ca', '#3730a3']
bars = ax1.bar(range(len(names)), lz77_ratios, color=colors_bar, alpha=0.85, edgecolor='white', linewidth=0.8)
ax1.axhline(1.0, color='#f87171', linestyle='--', linewidth=1.5, label='No compression')
ax1.set_xticks(range(len(names)))
ax1.set_xticklabels([n.replace(' ', '\n') for n in names], fontsize=8, color='white')
ax1.set_ylabel('Compression ratio', color='white', fontsize=11)
ax1.set_title("LZ77 Compression Ratio\nby Data Type", color='white', fontsize=12, fontweight='bold')
ax1.legend(fontsize=9, facecolor='#1a1a2e', edgecolor='#818cf8', labelcolor='white')
ax1.set_facecolor('#0a0a1a')
ax1.tick_params(colors='white')
ax1.grid(True, alpha=0.2, color='#818cf8', axis='y')
for sp in ax1.spines.values(): sp.set_color('#818cf8')
for bar, r in zip(bars, lz77_ratios):
    ax1.text(bar.get_x() + bar.get_width()/2, bar.get_height() + 0.03,
             f'{r:.2f}x', ha='center', va='bottom', color='white', fontsize=9)

# Plot 2: Entropy vs LZ77 ratio scatter
ax2 = axes[1]
ax2.scatter(entropies, lz77_ratios, c=colors_bar[:len(names)], s=120, zorder=5, edgecolors='white', linewidths=1)
for i, name in enumerate(names):
    ax2.annotate(name, (entropies[i], lz77_ratios[i]),
                 textcoords="offset points", xytext=(5, 5), fontsize=7, color='#a5b4fc')
# Theoretical curve: ratio ~ 8/H (bytes to bits)
H_curve = np.linspace(1, 6, 100)
ax2.plot(H_curve, 8 / H_curve, '--', color='#fbbf24', linewidth=1.5, alpha=0.8, label='Theoretical max (8/H)')
ax2.set_xlabel('Shannon entropy (bits/char)', color='white', fontsize=11)
ax2.set_ylabel('Compression ratio', color='white', fontsize=11)
ax2.set_title("Entropy vs Compression Ratio\n(lower entropy = more compressible)", color='white', fontsize=12, fontweight='bold')
ax2.legend(fontsize=9, facecolor='#1a1a2e', edgecolor='#818cf8', labelcolor='white')
ax2.set_facecolor('#0a0a1a')
ax2.tick_params(colors='white')
ax2.grid(True, alpha=0.2, color='#818cf8')
for sp in ax2.spines.values(): sp.set_color('#818cf8')

# Plot 3: LZ77 match length distribution for English text
text_en = test_data['English text']
tokens_en = lz77_compress(text_en)
lengths = [t[1] for t in tokens_en]
ax3 = axes[2]
ax3.hist(lengths, bins=range(0, max(lengths)+2), color='#818cf8', alpha=0.85,
         edgecolor='white', linewidth=0.5, density=True)
ax3.set_xlabel('Match length', color='white', fontsize=11)
ax3.set_ylabel('Frequency (normalized)', color='white', fontsize=11)
ax3.set_title("LZ77 Match Length Distribution\n(English text)", color='white', fontsize=12, fontweight='bold')
mean_len = np.mean(lengths)
ax3.axvline(mean_len, color='#fbbf24', linestyle='--', linewidth=1.5, label=f'Mean = {mean_len:.1f}')
ax3.legend(fontsize=9, facecolor='#1a1a2e', edgecolor='#818cf8', labelcolor='white')
ax3.set_facecolor('#0a0a1a')
ax3.tick_params(colors='white')
ax3.grid(True, alpha=0.2, color='#818cf8')
for sp in ax3.spines.values(): sp.set_color('#818cf8')

plt.tight_layout()
plt.savefig('output.png', dpi=150, bbox_inches='tight', facecolor='#0a0a1a')
plt.show()
print("\nLZ77/LZ78 achieve entropy rate asymptotically for ergodic sources (Lempel-Ziv theorem).")

Click Run to execute the Python code

Code will be executed with Python 3 on the server

← Ch 18: Quantum Error Correction Ch 20: Information Bottleneck →