Data Compression
Olivia is streaming a show on her phone and watches her data meter drop. A song that would take 40 MB as raw audio fits in 4 MB on her playlist, and she can barely hear the difference. How can a file get ten times smaller and still sound fine? And when would shrinking a file be a bad idea? By the end of this page you will be able to answer both questions.
Why compress?
Data compression is a way to represent the same data using fewer bits. Smaller files take less storage space, upload and download faster, and use less of your cellular data.
Remember that a computer stores everything as bits. If a file has a lot of repetition or details nobody will notice, there are shortcuts that need fewer bits to describe it.
The size change is usually reported as a percent reduction:
$$\text{percent reduction} = \frac{\text{original size} - \text{new size}}{\text{original size}} \times 100\%$$A 12 MB file is compressed to 3 MB. a) By what percentage was the file size reduced? b) Can you tell from these numbers alone whether the compression was lossless or…
A 12 MB file is compressed to 3 MB.
- a) By what percentage was the file size reduced?
- b) Can you tell from these numbers alone whether the compression was lossless or lossy? Explain.
Olivia has a phone plan with a monthly data cap of 6,000 MB. One hour of video streams at 1,200 MB at high quality and 450 MB at a lossy "data saver" quality. a) How…
Olivia has a phone plan with a monthly data cap of 6,000 MB. One hour of video streams at 1,200 MB at high quality and 450 MB at a lossy "data saver" quality.
- a) How many full hours of video can she watch each month at each quality?
- b) Describe one trade-off she makes by choosing data saver quality.
Lossless compression
Lossless compression makes a file smaller in a way that lets you rebuild the exact original, bit for bit. Nothing is lost. The trade-off is that the savings are usually modest.
Common lossless formats: ZIP files, PNG images, and FLAC audio.
Use lossless compression when every detail matters: text documents, spreadsheets, computer programs, legal contracts, medical images.
Run-length encoding
One simple lossless idea is run-length encoding (RLE). Replace each run of repeated characters with a count followed by the character.
RLE is lossless because you can always decode it back to exactly the original. But it only helps when there are long runs. The string ABCD becomes 1A1B1C1D, which is longer.
A law office wants to compress a scanned contract before emailing it, and every character must stay exactly the same. Should the office use lossless or lossy…
A law office wants to compress a scanned contract before emailing it, and every character must stay exactly the same. Should the office use lossless or lossy compression? Explain your choice in two or three sentences.
Run-length encoding replaces repeated characters with a count followed by the character. For example, AAA becomes 3A. a) Encode the string AAAABBBCCD. How many…
Run-length encoding replaces repeated characters with a count followed by the character. For example, AAA becomes 3A.
- a) Encode the string
AAAABBBCCD. How many characters does the original have, and how many does the encoded version have?
- b) Decode
3X5Y1Z.
- c) Is run-length encoding lossless or lossy? Justify your answer.
Lossy compression
Lossy compression gets a much smaller file by permanently discarding some information. You can only rebuild an approximation of the original, not the exact data.
It works because people do not notice every detail. A JPEG photo removes tiny color differences your eye barely sees. An MP3 removes sounds that are very quiet or hidden by louder ones.
Common lossy formats: JPEG images, MP3 and AAC audio, and most streaming video.
| Lossless | Lossy | |
|---|---|---|
| Rebuild the exact original? | Yes | No |
| Typical file size | Somewhat smaller | Much smaller |
| Quality | Perfect | Drops as you compress more |
| Good for | Text, code, contracts, archives | Streaming, photos on the web, music on a phone |
| Examples | ZIP, PNG, FLAC | JPEG, MP3 |
Most lossy tools let you choose a setting. More compression means a smaller file and lower quality. That is the central trade-off.
Define lossless compression and lossy compression in your own words. Then classify each as lossless or lossy: (i) a ZIP file of a spreadsheet, (ii) an MP3 version of a…
Define lossless compression and lossy compression in your own words. Then classify each as lossless or lossy: (i) a ZIP file of a spreadsheet, (ii) an MP3 version of a song, (iii) a JPEG photo saved at low quality.
Sofia has a 24 MB original photo. The photo-editing app offers these lossy export settings: | Setting | File size | |---|---| | High | 6 MB | | Medium | 2 MB | | Low |…
Sofia has a 24 MB original photo. The photo-editing app offers these lossy export settings:
| Setting | File size |
|---|---|
| High | 6 MB |
| Medium | 2 MB |
| Low | 0.5 MB |
- a) Compute the percent reduction in file size for each setting, rounded to the nearest tenth of a percent.
- b) Which setting would you choose for a thumbnail on a website? Which would you keep for printing a poster later? Explain, and say what Sofia should do with the original file.
Variable-length codes
Here is another lossless trick. Normally every character gets the same number of bits. But some characters appear more often than others. Give frequent characters short codes and rare characters long codes, and the average length drops.
Say a message uses four letters. With a fixed code, 4 letters need 2 bits each (00, 01, 10, 11). Now try this variable-length code:
| Letter | Frequency | Code |
|---|---|---|
| A | 50% | 0 |
| B | 25% | 10 |
| C | 12.5% | 110 |
| D | 12.5% | 111 |
No code is the beginning of another code, so a string of bits can only be read one way. That is why this code is lossless.
A message has 1,000 characters, and each character is one of four letters: A, B, C, or D. The letters appear with these frequencies: A 50%, B 25%, C 12.5%, D 12.5%. a)…
A message has 1,000 characters, and each character is one of four letters: A, B, C, or D. The letters appear with these frequencies: A 50%, B 25%, C 12.5%, D 12.5%.
- a) How many bits does the message need if each character is stored with 8 bits? With a fixed 2 bits per character?
- b) A variable-length code uses A =
0, B =10, C =110, D =111. Compute the average number of bits per character and the total bits for the 1,000-character message.
- c) Is the variable-length code lossless or lossy? Explain why no information is lost, and explain why a frequent letter should get a shorter code.
Choosing and comparing
When you decide how to compress something, ask:
-
Must the exact data be kept? If yes, use lossless.
-
How much space or bandwidth do I have? If it is limited and small flaws are acceptable, lossy may be best.
-
Will I need to edit or reuse it later? If yes, keep a lossless original.
Storage totals are a multiplication. For example, 500 songs at 4 MB each is $500 \times 4 = 2{,}000$ MB, which is 2 GB when $1\text{ GB} = 1{,}000\text{ MB}$.
Back to the start: Olivia's 4 MB song is a lossy version of the 40 MB original. Her ears hardly notice the missing details, so the 90% saving is worth it for earbuds. A sound engineer who will remix the track needs every detail and should keep the lossless version.
A music streaming service stores each song in two versions: a lossless version of 40 MB and a lossy version of 4 MB. A user's library has 500 songs. a) Compute the total…
A music streaming service stores each song in two versions: a lossless version of 40 MB and a lossy version of 4 MB. A user's library has 500 songs.
- a) Compute the total storage needed for the library in each version, in GB. Use $1\text{ GB} = 1{,}000\text{ MB}$.
- b) Recommend a version for (i) a casual listener who uses earbuds on the school bus and has a phone with limited storage, and (ii) a sound engineer who archives recordings to remix them later. Justify each choice using the size and quality trade-off.
- c) Explain why converting a lossy file back to lossless format does not restore the original quality.