Topic 2.2: Data Compression | AP CSP Big Idea 2 | APCSExamPrep.com

AP CSP Course› Big Idea 2› 2.2 Data Compression
2.2
Big Idea 2 • Data

Data Compression

🕐 ~30 min FREE 📖 6 MCQ questions 🎮 Compression Challenge game DAT-1.D
2.1
Binary
2.2
Compression
2.3
Extract
2.4
Programs

After this lesson, you will be able to:

  • Explain why data is compressed and what redundancy has to do with it
  • Compare lossless and lossy compression and state exactly what each guarantees
  • Work a run-length encoding example by hand and show why it is lossless
  • Reason about the size-versus-quality trade-off and pick the right method for a use case
  • Explain why fewer bits does not automatically mean less information
  • Describe how data-format and compression choices appear in your Create Task written response
📈 Exam weight: Big Idea 2 (Data) is 17 to 22 percent of the AP CSP exam, and compression is one of its most reliably tested ideas. Expect MCQs that ask you to choose lossless versus lossy for a scenario, judge whether the exact original can be recovered, and reason about how much a file will shrink. These are quick points once the distinctions are automatic.
💡 Think about this first

A single minute of raw, uncompressed audio is over 10 megabytes, yet a three-minute song streams to your phone in seconds. A photo straight off a camera sensor is enormous, yet it fits in a text message. Nothing about the original recording changed; the file just got dramatically smaller on the way to you. Compression is the reason almost everything on the internet is fast enough to use, and the key question this lesson answers is: when is it safe to make a file smaller, and when does making it smaller quietly throw away something you needed?

Why We Compress Data

Data compression reduces the number of bits used to store or transmit a piece of data. Smaller files take less storage space and travel faster across a network, which is why compression sits underneath streaming, messaging, backups, and nearly every download you make. A compression method looks for redundancy in the data, which is repeated or predictable patterns, and finds a shorter way to represent the same content.

How much a file shrinks is not fixed. The amount of size reduction depends on both how much redundancy the original contains and which compression method is used. A page of text with long repeated stretches compresses a great deal; data that is already varied or close to random barely compresses at all, no matter how clever the algorithm.

🎯 A distinction the exam loves

Fewer bits does not automatically mean less information. Removing redundancy shortens how the data is written down without changing what it says, so a smaller file can still carry all of the original information. Only certain methods actually discard information. Keep "fewer bits" and "less information" as two separate ideas.

That last point splits every compression method into two families. Some methods promise the original can be rebuilt exactly, and some trade that promise away for a much smaller file. Those two families are lossless and lossy, and knowing which one a scenario needs is the whole skill.

Lossless Compression

Lossless compression reduces the number of bits while guaranteeing that the original data can be reconstructed exactly. Nothing is lost. You compress, and later you decompress, and what comes back is bit-for-bit identical to what you started with. Common lossless formats include ZIP for general files, PNG for images, and run-length encoding as a simple teaching example. Lossless is the only acceptable choice whenever the exact original must survive, which is why it is used for text, source code, spreadsheets, and archives.

A worked example: run-length encoding

Run-length encoding (RLE) is the clearest way to see lossless compression happen. It scans the data left to right and replaces each run of identical symbols with a count followed by the symbol. Watch it compress an 8-character string:

Original (8 characters): A A A A A B B B |---- 5 A ----| |-3 B-| Encoded (4 characters): 5A3B Decoded back: AAAAABBB (exactly the original)

The five A characters become 5A and the three B characters become 3B, so AAAAABBB shrinks to 5A3B: from 8 characters down to 4, a saving of 4. Crucially, the counts and symbols carry everything needed to rebuild the string, so decoding returns AAAAABBB perfectly. That exact-recovery guarantee is what makes RLE lossless.

⚠ Redundancy is what RLE feeds on

RLE only helps when there are long runs. Encode ABABAB and you get 1A1B1A1B1A1B, which is longer than the original because there is no redundancy to remove. This is the general rule in miniature: compression pays off in proportion to how much repetition the data actually contains.

✍ Mini Exercise 1 • Predict first
A file is compressed, stored, and later decompressed. The decompressed file is confirmed to be bit-for-bit identical to the original. Which statement must be true?

Lossy Compression

Lossy compression can reduce the number of bits far more than lossless, but it does so by permanently discarding some of the data. Once compressed, the exact original cannot be reconstructed; decompressing gives back an approximation, not a perfect copy. The classic lossy formats are JPEG for photos and MP3 for audio. They work by throwing away detail a human is unlikely to notice, such as subtle color shifts or sounds masked by louder ones, so the file gets much smaller while still looking or sounding acceptable.

Lossy is the right tool when transmission and storage efficiency matter more than a perfect reproduction, and when a person perceiving the media will tolerate the loss. That describes most photos, music, and video on the web. It is the wrong tool the instant an exact copy is required, because the discarded data is gone for good and no amount of decompressing brings it back.

⚠ The one-way door

Lossy loss is permanent. Saving a JPEG at high compression and later "saving it again at full quality" does not restore the detail; that detail no longer exists in the file. Re-compressing a lossy file repeatedly only degrades it further. Treat lossy as a door that opens one way only.

✍ Mini Exercise 2 • Spot the flawed reasoning
A student says: "Lossy compression is strictly better than lossless because it makes files smaller." Which choice best identifies the flaw in that reasoning?

The Size-versus-Quality Trade-off

Choosing a compression method is a trade-off between size and fidelity (how faithful the copy is to the original). Lossless keeps perfect fidelity but reduces size less. Lossy sacrifices some fidelity to reduce size much more. Neither is "better" in the abstract; the right choice depends entirely on what the data is for.

A reliable way to decide is to ask one question: must the reconstructed data be exactly the original?

  • If yes, use lossless. Text, source code, spreadsheets, executable programs, legal contracts, and medical scans all break or lose meaning if a single value changes. When the data must be reconstructed exactly, lossless is preferred.
  • If no, lossy is often the smart choice. For photos, music, and video that a human will simply view or hear, lossy delivers a much smaller file at a quality the person will accept, which is why it dominates streaming and the web.
🎯 How the exam frames it

Scenario questions almost always hinge on one clue: does the situation demand a perfect copy or just a good-enough one? "Archive," "legal record," "source code," and "must be recovered exactly" point to lossless. "Stream," "download quickly," "small thumbnail," and "a listener or viewer" point to lossy. Read the stem for that clue before you look at the options.

✍ Mini Exercise 3 • Encode it yourself
Using run-length encoding (count then symbol for each run), what is the encoding of the string AAAAABBB? Type it with no spaces.
encoding:

Key Vocabulary

Term Definition Example
Data compression Reducing the number of bits used to store or transmit data Zipping a folder before emailing it
Redundancy Repeated or predictable patterns in data that compression can remove A long run of the same pixel color
Lossless Compression that guarantees the original can be reconstructed exactly ZIP, PNG, RLE
Lossy Compression that permanently discards data for a much smaller file JPEG, MP3
Run-length encoding A lossless method that replaces each run of repeats with count + symbol AAAAABBB becomes 5A3B
Reconstruction Rebuilding the data from its compressed form when decompressing Unzipping restores every byte
Trade-off Balancing smaller file size against loss of quality or detail Lower JPEG quality for a smaller photo
📋 Create Performance Task • Where data choices earn points

The Create Task is a program you build, and your written response has to explain how the program manages data. You will not compress files by hand, but the same reasoning you just practiced, choosing a representation that fits the purpose, is exactly what graders want to see described clearly. When your program stores or moves data, the format you pick is a decision you can justify.

What a clear data explanation sounds like

Suppose your Create Task saves a list of user scores and reads them back later:

scores <- [88, 92, 75, 100] DISPLAY(scores)

A response earns credit when it names the data, states how it is stored, and ties that choice to the program's purpose. The habit is the same one compression teaches: match the representation to what the data is for.

  • "The list scores stores each user's results so the program can display and total them later."
  • "Because every score must be kept exactly, the data is stored without any loss, the way lossless compression preserves the original values."
  • "Choosing a list lets the program handle any number of scores, which is how it manages the complexity of varied input."

The idea that carries over

Compression is a concrete case of a bigger CSP theme: data must be represented in a way that fits its use. Exact-copy data (text, records, code) is kept losslessly; human-perceived media (images, sound) can accept lossy trade-offs. Being able to state why a representation fits the purpose is what turns a vague answer into a point-earning one. See the full Create Task module →

📈
MCQ Practice
6 questions • Exam difficulty and above • Predict before you peek
Question 1 of 6Spot the flaw
Predict first: decide what is wrong with the claim before you read the choices.
A student argues: "Run-length encoding is lossy, because the encoded string 5A3B has fewer characters than AAAAABBB, and fewer characters means information was lost." Which choice best identifies the error in this argument?
Incorrect. Removing characters is not what makes a method lossy; discarding recoverable information is. RLE removes redundancy while keeping everything needed to rebuild the original.
Incorrect. 5A3B is 4 characters and AAAAABBB is 8, so the encoded form really is shorter. The flaw is elsewhere in the reasoning.
Correct. Fewer bits does not mean less information. RLE removes only redundancy, and 5A3B decodes back to AAAAABBB exactly, so nothing was lost and the method is lossless.
Incorrect. RLE applies to any sequence of symbols, including letters. That is not the flaw in the argument.
Question 2 of 6I, II, III
A team needs a compression method that guarantees the original data can be reconstructed exactly. Which of the following formats satisfy that requirement?
  • I. Saving a diagram as a PNG image
  • II. Compressing a folder of documents into a ZIP file
  • III. Saving a photograph as a JPEG image
Incorrect. PNG (I) is lossless, but ZIP (II) is lossless too, so I alone is incomplete.
Correct. PNG and ZIP are both lossless, so each guarantees exact reconstruction. JPEG (III) is lossy and permanently discards data, so it fails the requirement.
Incorrect. JPEG (III) is lossy, so it cannot guarantee exact reconstruction. II is lossless, but it must pair with I, not III.
Incorrect. JPEG (III) is lossy and cannot rebuild the original exactly. Only the lossless formats, I and II, satisfy the requirement.
Question 3 of 6NOT question
Which of the following is NOT a property of lossy compression?
Incorrect. This IS a property of lossy compression, so it is not the answer. Lossy can achieve smaller sizes precisely because it discards data.
Incorrect. This IS true of lossy compression: what it discards is gone permanently. The question asks for the property that does not fit.
Incorrect. This IS a property of lossy compression, which dominates streaming media. Look for the statement that describes lossless instead.
Correct. Exact reconstruction is a property of lossless, not lossy. Lossy permanently discards data, so the original cannot be rebuilt exactly, which makes this the statement that does NOT belong.
Question 4 of 6Best use case
Predict first: does this scenario demand a perfect copy or just a good-enough one?
A hospital must store an MRI scan that radiologists will later zoom into to make a diagnosis. Which compression choice is best, and why?
Incorrect. Faster transfer does not justify discarding detail here. A lossy artifact could hide or invent something clinically important, so the smaller size is not worth it.
Correct. Diagnosis depends on exact detail, so the data must be reconstructed exactly. That requires lossless compression, which preserves every value.
Incorrect. How often the scan is viewed is irrelevant; what matters is that the detail must be exact each time it is examined, which requires lossless.
Incorrect. The choice of lossless is right, but the reason is wrong. Lossless does not produce the smallest file; lossy usually produces smaller files. Lossless is chosen to preserve exact detail.
Question 5 of 6Best use case
A music app must stream a 3-minute song over a limited mobile data connection while keeping the sound acceptable to listeners. Which choice is best, and why?
Incorrect. Music for listening does not need bit-for-bit reconstruction. Insisting on it would waste bandwidth the scenario says is limited.
Incorrect. The choice of lossy is right, but the reason is false. Lossy does NOT reconstruct the original perfectly; it discards data permanently. That is exactly why the file is smaller.
Correct. Efficiency matters more than a perfect copy here, and a listener will not notice the discarded detail. Lossy shrinks the file a lot while keeping acceptable quality, which is why streaming uses it.
Incorrect. Lossless does not give the smallest file; lossy does. For acceptable-quality streaming over limited data, lossy is the better fit.
Question 6 of 6Compare algorithms
Two different lossless algorithms compress the same text file. Algorithm X produces a 40 KB file and Algorithm Y produces a 55 KB file. Which statement is best supported?
Incorrect. Both algorithms are lossless, so neither discards original data. A smaller output reflects better compression of redundancy, not lost content.
Correct. Lossless means both outputs rebuild the original text exactly, regardless of size. X simply removed more redundancy on this file, so it compressed better here.
Incorrect. A smaller file does not make a method lossy. The problem states both algorithms are lossless, so X is lossless and just compressed more effectively.
Incorrect. Both are lossless, so both recover the original exactly. File size does not determine whether the original can be rebuilt.

Practice: Compression Challenge

Put the ideas to work. Each round either asks you to pick the right compression method for a real use case or to crack a run-length encoding by hand. Fast, accurate answers build a streak. Aim to reason from the size-versus-quality trade-off, not from a guess.

Compression Challenge

Lossless vs lossy, and the size versus quality trade-off (AP CSP 2.2)

How to play: pick the right compression for each use case, then crack the run-length encoding rounds. Fast answers keep your streak alive.

0Score
0Streak
1Round
Choose the method

Loading...

Nice work!

0

Frequently Asked Questions

Lossless compression reduces the number of bits while guaranteeing that the original data can be reconstructed exactly, bit for bit. Lossy compression can reduce size much more, but it permanently discards some data, so the exact original can never be recovered. ZIP, PNG, and run-length encoding are lossless; JPEG and MP3 are lossy.
No. Lossless compression removes redundancy, not information, so a smaller file can still hold all of the original information and be rebuilt exactly. Only lossy compression actually throws information away. This is why fewer bits does not automatically mean less information.
Run-length encoding is a lossless method that replaces each run of repeated symbols with a count followed by the symbol. For example, AAAAABBB has a run of five A characters and a run of three B characters, so it encodes to 5A3B. Because the counts and symbols are kept, the original can be rebuilt exactly, which makes it lossless.
Choose lossy when smaller size and faster transmission matter more than a perfect copy, and when a human viewer or listener will not notice the discarded detail. Streaming music, web photos, and video use lossy for this reason. Choose lossless when the data must be reconstructed exactly, such as text, source code, spreadsheets, and legal or medical records.
The amount of size reduction depends on both how much redundancy the original data contains and which compression method is used. Data with long runs or repeated patterns compresses a great deal, while data that is already varied or random compresses very little no matter the algorithm.

🔗 Continue studying

← BI2 Hub ← 2.1 Binary Numbers Next: 2.3 Extracting Information → 2.4 Using Programs with Data Create Task Module Daily Practice Questions College Board AP CSP ↗
📦
AP CSP Teacher SuperpackSlides, lesson plans, unit tests for all 5 Big Ideas, $249
Get the Superpack →
🏫
For teachers

The Superpack includes an editable Topic 2.2 slide deck with animated lossless-versus-lossy demos, a run-length encoding worksheet with an answer key, a use-case sorting activity, and a unit quiz. View what's included →

← Previous
2.1 Binary Numbers

Get in Touch

Whether you're a student, parent, or teacher — I'd love to hear from you.

Just want free AP CS resources?

Enter your email below and check the subscribe box — no message needed. Students get daily practice questions and study tips. Teachers get curriculum resources and teaching strategies.

Typically responds within 24 hours
✓

Message Sent!

Thanks for reaching out. I'll get back to you within 24 hours.

🏫 Welcome, fellow educator!

I offer curriculum resources, practice materials, and study guides designed for AP CS teachers. Let me know what you're looking for — whether it's classroom materials, a guest speaker, or Teachers Pay Teachers resources.

✉

Email

[email protected]

📚

Courses

AP CSA, CSP, & Cybersecurity

⏱

Response Time

Within 24 hours

Prefer email? Reach me directly at [email protected]