You take a 12-megabyte photo of your dog. You text it to a friend — and the messaging app sends a 400-kilobyte version that still looks, to your eye, exactly like your dog. That's a 30× shrink. Where did 96% of the photo go?
Gone. Permanently. The app threw away detail your eye probably wouldn't notice — subtle color gradations, fine texture. Your friend can never recover the original from what you sent.
Now suppose instead you email your friend a 12-megabyte spreadsheet, zipped down to 2 megabytes. When she unzips it, she'd better get every cell back exactly — a spreadsheet with "approximately your data" is garbage.
Two compressions, two totally different promises. That difference is this whole lesson.
Data compression reduces the number of bits needed to store or transmit data. Fewer bits = less storage, faster transmission, lower cost. Since everything is bits (Lesson 3), everything can potentially be compressed.
Compression works because real data has redundancy — repeated patterns, predictable structure. "AAAAAABBBB" doesn't need 10 stored letters; "6 A's, then 4 B's" carries the same information in less space.
Lossless compression reduces bits in a way that allows complete reconstruction of the original data. Nothing is lost — the compressed version is a perfectly reversible re-encoding.
Lossy compression reduces bits by permanently discarding some information — typically detail humans barely perceive.
Choose lossless when complete reconstruction matters more than file size. Choose lossy when reducing size/transmission time matters more than perfect fidelity.
The deciding factor is always the purpose of the data's use. Same photo, different answers: archiving the master copy of a professional shoot → lossless; posting to social media → lossy is fine. Scenario questions bury the purpose in one phrase ("the analyst must recover the exact original readings") — find that phrase and the answer falls out.
Run-length encoding (RLE) replaces runs of repeated values with a count + the value. It's the exam's standard concrete example of lossless compression.
Consider one row of a black-and-white image (B = black pixel, W = white):
Original: W W W W W W W W B B B W W W W B
RLE: 8W 3B 4W 1B
The original row takes 16 symbols; the encoded version takes 4 count-value pairs. Decoding is mechanical: write 8 W's, 3 B's, 4 W's, 1 B — the exact original returns, which is what makes RLE lossless.
Computing the savings (a real exam task): Suppose each pixel takes 1 bit uncompressed (16 bits total) and each RLE pair takes 4 bits for the count + 1 bit for the color = 5 bits (20 bits total for 4 pairs). Compressed is bigger — 20 > 16! RLE only wins when runs are long:
Original: 64 white pixels = 64 bits
RLE: one pair "64 W" — but wait: a 4-bit count only reaches 15!
Need: 15W 15W 15W 15W 4W = 5 pairs × 5 bits = 25 bits ✓ (61% smaller)
Two morals the exam tests: (1) compression effectiveness depends on the data — long runs compress well, noisy data can even grow; (2) implementation details (like how many bits the count gets) matter when computing savings.
Compression changes how many bits encode the data. Sampling (Lesson 3) converts analog → digital. A question about "measuring a sound wave 44,100 times per second" is sampling; a question about "reducing the MP3's file size" is compression. Don't let the sound-context blur them.
Problem: A hospital stores MRI scans that radiologists will later examine for subtle tissue anomalies. Which compression is appropriate, and why?
Strategy: Find the purpose: "examine for subtle anomalies" → every detail may matter → perfect reconstruction required.
Solution: Lossless. Discarded detail in a lossy scheme could be exactly the anomaly a radiologist needs to see; medical use requires complete reconstruction.
Interpretation: The setting (medical/legal/financial/scientific) almost always signals lossless. The signal-word is a stakes word: diagnose, audit, evidence, exact.
Problem: A video-streaming service wants to serve movies to phones on limited data plans. Which compression, and what's the trade-off?
Solution: Lossy. Purpose = minimize transmission size for smooth playback; viewers tolerate imperceptible (or even mildly perceptible) quality loss. The trade-off: the full original quality can never be recovered from the streamed version — which is fine, because the service keeps the master and the viewer only needs to watch.
Problem: Encode this pixel row with run-length encoding, then verify decoding restores it: B B B B B B W W B B B B W W W W W W W W
Strategy: Walk left to right, counting runs.
Solution:
Runs: 6 B's → 2 W's → 4 B's → 8 W's
RLE: 6B 2W 4B 8W
Decode check: BBBBBB WW BBBB WWWWWWWW = 6+2+4+8 = 20 pixels ✓ exact original
Interpretation: Count carefully — off-by-one in a run is the whole error mode here. Verify totals: 6+2+4+8 = 20 = original length.
Problem: A student applies run-length encoding to two 24-pixel rows.
Row 1: WWWWWWWWWWWWBBBBBBBBBBBB (12 W's, 12 B's)
Row 2: WBWBWBWBWBWBWBWBWBWBWBWB (alternating)
Each RLE pair costs 6 bits; each raw pixel costs 1 bit. What happens?
Strategy: Count pairs for each row; compare to 24 bits raw.
Solution: - Row 1: 2 runs → 2 pairs × 6 bits = 12 bits vs. 24 raw → compressed to half. ✓ - Row 2: 24 runs (every pixel is a run of 1) → 24 pairs × 6 bits = 144 bits vs. 24 raw → six times larger. ✗
Interpretation: Compression exploits redundancy; data without redundancy can expand under the wrong scheme. If an exam question shows alternating or noisy data, watch for the "compressed version may be larger" answer — it's often correct.
1. (C). Complete reconstruction is the defining property. (A) describes lossy. (B) reverses the size trade-off. (D) is a fabricated restriction.
2. (B). Greater reduction by discarding information — both halves of the definition. (A) describes lossless. (C) reverses appropriateness. (D) is nonsense.
3. (C). "Quoted verbatim in court" = exactness is the purpose → lossless. (A)/(D) sacrifice recoverability that the purpose demands.
WWWWBBBWWWWWW encodes to:4. (A). Runs: 4 W's, 3 B's, then count the tail: W W W W W W = 6 W's → 4W 3B 6W. (B) miscounts the last run (off-by-one — the classic). (C) reverses pair order and miscounts. (D) swaps the first two counts.
2B 5W 1B 4W decodes to a row of how many pixels?5. (C). 2 + 5 + 1 + 4 = 12 pixels. (D) is a digit-mash; (B) drops a run; (A) counts pairs, not pixels.
6. (A). Smaller files with reduced detail = information discarded = lossy. (B) wouldn't reduce detail. (D) is a lossless technique and irrelevant to photos-with-reduced-detail.
7. (C). Alternating pixels = 60 runs of length 1 → maximal overhead, worst case (may even expand — see Example 4). (A), (B), (D) all have long runs, RLE's best case.
8. (A). The archive's purpose (future remastering) needs perfect masters → lossless; streaming's purpose (casual listening on limited bandwidth) tolerates loss → lossy. Purpose decides per use, even for the same organization. (C)/(D) apply one answer to two different purposes.
9. (B). Lossy's defining consequence: approximation out, originals unrecoverable. (A) describes lossless.
10. (A) and (B). These are the CED's two decision factors — reconstruction need vs. size/time need. (C) is universal (everything is binary); (D) is irrelevant to the algorithm choice.
15W 15W using pairs that cost 6 bits each; raw pixels cost 1 bit each. The compression achieves:11. (A). 2 pairs × 6 bits = 12 bits vs. 30 raw bits → 60% reduction. (D) forgets each pair costs 6 bits, not 7.5; (C) multiplies wrongly.
12. (B). Encoding overhead vs. redundancy — when runs are short, count-markers cost more than they save (Example 4's alternating row). (A) is false in general; (D) confuses lossless with lossy and misstates why size grows.
Answer letter distribution check: C, B, C, A, C, A, C, A, B, A+B, A, B — singles: A×4, B×3, C×4, D×0 + multi (A,B). D underused this lesson (D×1 across L3–4) — Lesson 5 key will include D answers deliberately.
Compression won't appear in your PT program — but the trade-off reasoning pattern will, and it's worth internalizing now. The exam's written responses and the PT's design decisions reward the same sentence shape:
"I chose X over Y because the purpose required , and I accepted the cost of ."
That's the lossless-vs-lossy sentence. It's also the sentence for choosing a list over separate variables (Lesson 8) and choosing a procedure over repeated code (Lesson 14). Trade-off framing — benefit, cost, purpose — is the single most reusable answer skeleton in this course.
Mini practice: Write the trade-off sentence for a photo-sharing app choosing lossy compression for uploads. Model: "I chose lossy compression because the purpose — fast uploads on mobile data — makes transmission size more important than perfect fidelity, and I accepted the cost that original image detail cannot be recovered from the uploaded copy."
1. (C). Complete reconstruction is the defining property. (A) describes lossy. (B) reverses the size trade-off. (D) is a fabricated restriction.
2. (B). Greater reduction by discarding information — both halves of the definition. (A) describes lossless. (C) reverses appropriateness. (D) is nonsense.
3. (C). "Quoted verbatim in court" = exactness is the purpose → lossless. (A)/(D) sacrifice recoverability that the purpose demands.
4. (A). Runs: 4 W's, 3 B's, then count the tail: W W W W W W = 6 W's → 4W 3B 6W. (B) miscounts the last run (off-by-one — the classic). (C) reverses pair order and miscounts. (D) swaps the first two counts.
5. (C). 2 + 5 + 1 + 4 = 12 pixels. (D) is a digit-mash; (B) drops a run; (A) counts pairs, not pixels.
6. (A). Smaller files with reduced detail = information discarded = lossy. (B) wouldn't reduce detail. (D) is a lossless technique and irrelevant to photos-with-reduced-detail.
7. (C). Alternating pixels = 60 runs of length 1 → maximal overhead, worst case (may even expand — see Example 4). (A), (B), (D) all have long runs, RLE's best case.
8. (A). The archive's purpose (future remastering) needs perfect masters → lossless; streaming's purpose (casual listening on limited bandwidth) tolerates loss → lossy. Purpose decides per use, even for the same organization. (C)/(D) apply one answer to two different purposes.
9. (B). Lossy's defining consequence: approximation out, originals unrecoverable. (A) describes lossless.
10. (A) and (B). These are the CED's two decision factors — reconstruction need vs. size/time need. (C) is universal (everything is binary); (D) is irrelevant to the algorithm choice.
11. (A). 2 pairs × 6 bits = 12 bits vs. 30 raw bits → 60% reduction. (D) forgets each pair costs 6 bits, not 7.5; (C) multiplies wrongly.
12. (B). Encoding overhead vs. redundancy — when runs are short, count-markers cost more than they save (Example 4's alternating row). (A) is false in general; (D) confuses lossless with lossy and misstates why size grows.
Answer letter distribution check: C, B, C, A, C, A, C, A, B, A+B, A, B — singles: A×4, B×3, C×4, D×0 + multi (A,B). D underused this lesson (D×1 across L3–4) — Lesson 5 key will include D answers deliberately.
Exam tip: In any compression scenario, underline the purpose phrase before reading the choices. "Must recover the exact original" → lossless. "Wants faster transmission / smaller files and can tolerate quality loss" → lossy. The scenario always contains exactly one such phrase — it is the question.