AP CSP
AP Computer Science Principles / All lessons / Big Idea 2: Data
2Big Idea 2: Data
AP CSP topic 2.2

Data Compression

Compression reduces the number of bits needed to store or send data. Lossless compression lets you rebuild the original data exactly, which matters for text and code. Lossy compression throws away some detail to make files much smaller, which works well for photos, music, and video where small losses are hard to notice. Choosing between them is a tradeoff between file size and quality.

Picture itAAAABBBCDDDD4A3B1C4D12 symbols8 symbols
Run-length encoding replaces each run of the same symbol with a count. It is lossless: the original can be rebuilt exactly.

Data Compression vocabulary

  • Data compression: Reducing the number of bits used to represent data.
  • Lossless: Compression that allows the original data to be restored exactly.
  • Lossy: Compression that permanently removes some data to save more space.
  • Run-length encoding: A lossless method that replaces repeated values with a count, such as AAAA becoming 4A.

AP-style practice questions

Try each one, then open the answer. To save your progress, take this quiz in the interactive course.

Skill: Computing Innovations

1. A student needs to send a copy of their program's source code to a teacher using as few bits as possible. Which type of compression should be used?

  1. (A) Lossy, because it gives the smallest file
  2. (B) Lossless, because every character of the code must be restored exactly
  3. (C) Lossy, because code has many repeated words
  4. (D) No compression is possible for text
Show answer

(B) Lossless, because every character of the code must be restored exactly Code must be restored exactly, so lossless compression is required.

Skill: Code Analysis

2. Using run-length encoding, the string "AAABBBBCC" is stored as "3A4B2C". Which of the following is the encoding of "WWWWWWBB"?

  1. (A) 6W2B
  2. (B) W6B2
  3. (C) 2W6B
  4. (D) 8WB
Show answer

(A) 6W2B Six Ws, then two Bs: 6W2B.

Skill: Computing Innovations

3. A photo-sharing app shrinks images so they upload faster. Users rarely notice the difference in quality. Which of the following best describes this compression?

  1. (A) Lossless, since nothing changes
  2. (B) Lossy, since some detail is removed to reduce size
  3. (C) Encryption, since the image is scrambled
  4. (D) Redundancy, since copies are stored
Show answer

(B) Lossy, since some detail is removed to reduce size Removing hard-to-notice detail to save space is lossy compression.

Skill: Abstraction in Program Development

4. Which of the following is a tradeoff of lossy compression compared with lossless compression?

  1. (A) Lossy files are larger but higher quality
  2. (B) Lossy files are smaller but the original cannot be fully restored
  3. (C) Lossy files can always be restored exactly
  4. (D) Lossy compression only works on text
Show answer

(B) Lossy files are smaller but the original cannot be fully restored Lossy saves more space but permanently loses some data.

Open 2.2 in the interactive course