Data Compression & Analysis

📦 Data Compression & Analysis

Part 1 of 7 — Lossless vs Lossy, Compression Techniques, and Data Analysis

Why Compress Data?

Smaller files mean:

• Faster transmission over networks
• Less storage space needed
• Lower bandwidth usage
• Faster loading for users

Lossless vs Lossy Compression

Lossless Example: Run-Length Encoding

Original:  AAABBBCCDDDDDD
Compressed: 3A3B2C6D

The original can be perfectly reconstructed from the compressed version.

Lossy Example: JPEG Compression

A photograph has millions of color values. JPEG removes subtle color differences that human eyes cannot easily detect. The file shrinks dramatically, but the removed data cannot be recovered.

🔑 Lossless = perfect reconstruction. Lossy = smaller file but permanent data loss. Choose based on whether quality loss is acceptable.

Concept Check 🎯

Data Analysis and Visualization

Extracting Patterns from Data

When working with large datasets, visualization reveals patterns that raw numbers cannot.

Filtering and Transforming Data

// Filter: Keep only rows where score > 80
// Sort: Order by date ascending
// Aggregate: Calculate average score per student

Interpreting Results

• Look for trends (increasing, decreasing, stable)
• Identify outliers (values far from the norm)
• Check for clusters (groups of similar data points)
• Be cautious of bias in data collection

Challenges with Large Datasets

• Storage: Require significant space
• Privacy: May contain sensitive personal information
• Accuracy: Errors are amplified at scale
• Bias: If collection methods are biased, conclusions will be skewed

Applied Recall ✍️

1. Compression that can perfectly restore the original data is called _______ compression.

2. MP3 audio files use _______ compression, permanently removing some frequencies.

3. A chart that shows the relationship between two variables using dots is called a _______ plot.

Classify the Compression 🔍

AP Exam Strategy: Data Compression & Analysis

• Know the difference: lossless (ZIP, PNG) vs lossy (JPEG, MP3, MP4)
• Lossless for critical data (medical, legal, code). Lossy for media where small quality loss is acceptable
• Run-length encoding is the lossless technique the AP exam expects you to understand
• Data analysis questions test your ability to interpret visualizations and identify patterns
• Correlation does not imply causation — always consider confounding variables
• Large datasets can reveal patterns but also amplify errors and privacy concerns

AP-Style Application 🎯

🗜️ Data Compression & Analysis

Part 2 of 7 — Key Processes

Compression: Same Information, Fewer Bits

Compression takes a sequence of bits and produces a shorter sequence that decodes back to the original (lossless) or to an approximation of it (lossy).

Concept Check 🎯

Why Lossless Has A Limit

There's an information-theoretic minimum (entropy) for lossless compression. A truly random file cannot be losslessly compressed below its original size.

A simple example: a 100-character string of alternating "AB" patterns can be encoded as "AB × 50" — far smaller. A 100-character string of random characters has no pattern to exploit.

Why Lossy Can Go Further

Lossy compression exploits human perception:

• Audio: humans don't hear above ~20 kHz; some bands can be discarded.
• Image: small color shifts in textures are imperceptible.
• Video: most pixels barely change between frames; encode the difference.

A Tiny Lossless Example: Run-Length Encoding

RLE wins on data with long runs and loses on data without them. Compression is data-dependent.

Applied Recall ✍️

1. Compression that perfectly preserves the original data is called _______.

2. Compression that drops some information to save space is called _______.

3. The information-theoretic minimum size for lossless compression is set by _______.

Targeted Practice 🔍

AP Exam Strategy: Compression Basics

• "Must be perfect" → lossless.
• "Need much smaller, perceptual loss OK" → lossy.
• Lossless can't shrink random data below its entropy.
• Compression effectiveness is data-dependent.

AP-Style Application 🎯

🗜️ Data Compression & Analysis

Part 3 of 7 — Patterns & Examples

Common Compression Patterns

Concept Check 🎯

Dictionary Coding: A Mini-Walkthrough

Imagine encoding "the cat sat on the mat":

• Build a dictionary as you go.
• Replace repeated phrases with references.

After processing once, "the " might be code 0; "at" might be code 1. The compressed stream uses these short codes for repeated phrases.

This is the core idea behind ZIP, GZIP, PNG, and most modern lossless coders.

Huffman Coding In One Picture

If a text uses A 50%, B 25%, C 12.5%, D 12.5%:

Average bits per symbol: 0.5(1) + 0.25(2) + 0.125(3) + 0.125(3) = 1.75. Far less than 2 bits per symbol used by naive encoding.

Lossy Frequency-Domain Coding

JPEG and MP3 use a math transform (DCT) that turns blocks of pixels (or audio samples) into frequency components. Big components matter to perception; small ones can be quantized away. Decompression rebuilds an approximation.

Compression Vs. Encryption

Applied Recall ✍️

1. Replacing repeated substrings with references to a built-up dictionary is called _______ coding.

2. Giving short bit-codes to common symbols and long codes to rare ones is _______ coding.

3. Encoding only the difference between adjacent frames in a video is _______ encoding.

Targeted Practice 🔍

AP Exam Strategy: Compression Patterns

• "PNG / ZIP / GIF / FLAC" → lossless.
• "JPEG / MP3 / MP4 / streaming video" → lossy.
• Differential encoding is the secret of video compression.
• Don't encrypt before compressing — it ruins the compression.

AP-Style Application 🎯

🗜️ Data Compression & Analysis

Part 4 of 7 — Connections & Interactions

Compression Connects To Other Topics

Concept Check 🎯

Big Files Demand Streaming Algorithms

When a file doesn't fit in memory, you need algorithms that process data in a single pass with constant or sub-linear memory:

This connects compression-era data sizes to algorithm design.

Compression And The Internet

A modern webpage may be 10× larger uncompressed.

Compression-Aware Privacy

Two warnings:

1. Compression timing/size attacks (CRIME / BREACH) leaked info from HTTPS responses; mitigation involves disabling certain compressions over TLS.
2. "Anonymized" datasets that are then compressed don't become more anonymous — compression doesn't help privacy.

Applied Recall ✍️

1. An algorithm that processes data in a single pass without loading it all is called a _______ algorithm.

2. Modern web responses commonly compress text with _______ or Brotli.

3. Modern still-image formats designed to beat JPEG include WebP and _______.

Targeted Practice 🔍

AP Exam Strategy: Cross-Topic Compression

• "File too big for memory" → streaming algorithm.
• "Why is web fast now?" → better codecs + CDNs.
• "Order of compress / encrypt" → compress, then encrypt.

AP-Style Application 🎯

🗜️ Data Compression & Analysis

Part 5 of 7 — Change Over Time

How Compression Has Evolved

Concept Check 🎯

Codec Generations Roughly Halve File Sizes

This is why streaming 4K to a phone became feasible.

Open vs. Proprietary Codecs

Many great codecs (H.264, H.265) are encumbered by patents — companies pay licensing fees. AV1 / Opus / AVIF emerged as open alternatives, accepted by major browsers and platforms.

ML-Era Compression

Modern research uses neural networks to learn compression strategies for specific domains (medical imaging, faces, speech). These can sometimes outperform hand-designed codecs but raise new questions about model bias and reproducibility.

Compression And Storage Cost

Even as storage gets cheaper, compression remains crucial because bandwidth scales differently. A user's phone might have 1 TB of storage but only a few hundred MB of monthly mobile data.

Applied Recall ✍️

1. An open, royalty-free modern video codec is _______.

2. A modern still-image format derived from AV1 is _______.

3. Compression matters most when _______ is constrained, even if storage is cheap.

Targeted Practice 🔍

AP Exam Strategy: Compression Evolution

• "Why is streaming HD over a phone feasible?" → modern lossy codecs + CDNs + adaptive bitrate.
• "Open vs. proprietary codec" → openness avoids licensing and lock-in.
• ML compression is real but raises bias / reproducibility concerns.

AP-Style Application 🎯

🗜️ Data Compression & Analysis

Part 6 of 7 — Problem-Solving Workshop

Compression Workshop

Apply compression vocabulary to estimation and design problems.

Concept Check 🎯

Worked: Image Sizing

Worked: Audio Sizing

Worked: Choosing A Format

Applied Recall ✍️

1. A 1024×1024 24-bit image as raw RGB is about _______ MB.

2. JPEG vs raw typically achieves ~_______ × compression for typical photos.

3. For uncompressed CD-quality stereo audio, 1 second is roughly _______ KB.

Targeted Practice 🔍

AP Exam Strategy: Workshop

• Memorize raw sizes: 24-bit image = W × H × 3 bytes. CD stereo = ~176 KB/s.
• Match format to use case: archive → lossless; consumer media → lossy.
• "Adaptive bitrate" is the right answer for variable-bandwidth video delivery.

AP-Style Application 🎯

🗜️ Data Compression & Analysis

Part 7 of 7 — AP Review

AP Exam Recap — Compression & Analysis

Final review.

Concept Check 🎯

Final Vocab

Common Pitfalls

• Saying "compression makes data smaller" without distinguishing lossless vs lossy.
• Encrypting before compressing.
• Treating storage as the only constraint (bandwidth often matters more).
• Using lossy formats for archival or medical records.
• Ignoring openness / licensing of codecs.

Applied Recall ✍️

1. JPEG is _______ compression.

2. PNG is _______ compression.

3. Encrypting before compressing usually makes the result _______.

Targeted Practice 🔍

Final Exam Tips

• Lossless vs lossy is the #1 distinction.
• Compress THEN encrypt.
• Different uses → different formats. Memorize: PNG/ZIP/FLAC = lossless; JPEG/MP3/MP4 = lossy.
• Adaptive bitrate is the answer to "how does streaming work for everyone".

AP-Style Application 🎯