AP Computer Science Principles · Unit 2 lecture · Part 6 of 11 · 8 min

2.2 Data compression: losslessSame information, fewer bits

Mr. Thompkins
A minute of music is ten megabytes raw, yet your phone streams it in a fraction of that. Compression is the trick, and the first kind is almost magic: smaller files with nothing lost at all.

Data compression reduces the number of bits used to store or send data. Fewer bits mean files take less space and travel faster over a network. And here is the key idea: fewer bits does not necessarily mean less information. Most data has redundancy, parts that repeat or can be predicted, and a clever encoding can describe the same information in fewer bits.

Lossless compression algorithms reduce the number of bits stored or transmitted while guaranteeing complete reconstruction of the original data. Decompress the file and you get back every bit exactly as it was. Zip files work this way, and so do the formats used for text, spreadsheets and program code.

?Wait, what's an algorithm?
An algorithm is a finite set of step-by-step instructions that accomplishes a task. A compression algorithm is a set of steps for turning data into a shorter encoding, and a matching set of steps for turning it back.

An example: run-length encoding

Here's one simple lossless method, so you can see the idea. The exam won't ask you to know any specific compression algorithm by name, but it will ask you to reason about why compression works. Run-length encoding replaces a run of repeated values with a count and the value. Two weeks of weather, sun, sun, sun, sun, sun, rain, rain, rain..., becomes "5 suns, 3 rains" and so on.

14 days of weather: Sun, Rain, CloudSSSSSRRRSSSSCCcount each run5S3R4S2C14 symbols become 8expand it back: the same 14 days, exactly
Run-length encoding: 14 symbols become 8, and expanding them gives back the exact original.

Now notice what happens when the data has no repeats. The pattern sun, rain, sun, rain, sun, rain has runs of length 1, so the encoding 1S1R1S1R1S1R is twice as long as the original. Compression isn't free: how much size reduction you get depends on how much redundancy the original data has and on which compression algorithm is applied. Some data barely compresses at all.

OriginalLengthRun-length versionLengthResult
SSSSSRRRSSSSCC145S3R4S2C8smaller
12 W, 1 B, 11 W2412W1B11W8much smaller
SRSRSR61S1R1S1R1S1R12bigger!
Run-length encoding shines on long runs and backfires on data that keeps changing.
?Wait, what's redundancy?
Redundancy is repetition or predictability in data: long runs of the same color in an image, common words in text, silence in a recording. Compression algorithms work by describing the repeated or predictable parts more briefly.
Pause and think
Which would shrink more with run-length encoding: a scan of a page that is mostly white with a few lines of text, or a photo of a busy crowd? Why?
I thought about it. Show me
The mostly white page. Its rows have long runs of identical white pixels, which encode as just a count and a color. A crowd photo changes color almost every pixel, so the runs are short and the encoding saves little or even grows.
Compress and restore
A row of a black-and-white icon has 24 pixels: 12 white, then 1 black, then 11 white. (a) Write its run-length encoding. (b) How many symbols does it save? (c) Decompress your answer and check that nothing was lost.
  1. (a) Count the runs in order: 12 W, 1 B, 11 W, so the encoding is 12W1B11W.
  2. (b) The original has 24 symbols. The encoding has 8 characters: 1, 2, W, 1, B, 1, 1, W. It saves 16.
    Why?
    The long white runs are redundant, so they shrink to a count.
  3. (c) Expand: 12 W, then 1 B, then 11 W gives 24 pixels in the same order, exactly the original row. Nothing is lost, so this is lossless.
    Why?
    Lossless means complete reconstruction is guaranteed.

Answer: (a) 12W1B11W. (b) 24 symbols become 8, saving 16. (c) Expanding gives back all 24 pixels exactly.

Stuck? Get a hint
  1. Write each run as a count followed by the color.
  2. Count every character in your encoding, digits included.
  3. To check, write out each run again in full.
Check yourself
Which statement about lossless compression is true?
  1. AIt always reduces a file to half its size.
  2. BIt lets the original data be reconstructed exactly.
  3. CIt works by permanently removing details people can't notice.
  4. DIt makes every file smaller, no matter what data is in it.
Show the answer

B. Lossless compression guarantees complete reconstruction of the original. How much it shrinks a file depends on the data's redundancy, and data with no repeats may not shrink at all. Removing details is what lossy compression does.

  • Compression reduces the number of bits for stored or transmitted data. Fewer bits does not necessarily mean less information.
  • Lossless: the original can be reconstructed exactly, every bit.
  • How much a file shrinks depends on its redundancy and on the compression algorithm.
  • You won't be asked to know specific compression algorithms; you will be asked to reason about them.