2.2 Data compression: losslessSame information, fewer bits

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 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.
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.
| Original | Length | Run-length version | Length | Result |
|---|---|---|---|---|
| SSSSSRRRSSSSCC | 14 | 5S3R4S2C | 8 | smaller |
| 12 W, 1 B, 11 W | 24 | 12W1B11W | 8 | much smaller |
| SRSRSR | 6 | 1S1R1S1R1S1R | 12 | bigger! |
?Wait, what's redundancy?
I thought about it. Show me
- (a) Count the runs in order: 12 W, 1 B, 11 W, so the encoding is 12W1B11W.
- (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. - (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
- Write each run as a count followed by the color.
- Count every character in your encoding, digits included.
- To check, write out each run again in full.
- AIt always reduces a file to half its size.
- BIt lets the original data be reconstructed exactly.
- CIt works by permanently removing details people can't notice.
- 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.