AP® Computer Science Principles · Big Idea 2 · Topic 2.2
Lossless Compression
Lossless compression shrinks a file by rewriting predictable patterns more efficiently, so every original bit can be rebuilt exactly. It saves space, not information.
A file is bits, and bits are often repetitive or uneven in frequency. Lossless compression finds that structure and rewrites it in a shorter form that can be reversed perfectly, so decompressing gives back the exact original, bit for bit. This only works because real data is rarely random: pixel rows have long stretches of the same color, English text uses 'e' far more than 'z'. Compression exploits that predictability instead of fighting it.
Run length encoding targets repetition directly. Instead of storing a run of identical values one at a time, it stores a count and the value once: a run of six white pixels becomes the pair (6, white) rather than six separate 1-bit entries. The longer and more uniform the run, the more bits you save, because the cost of encoding stays fixed at one count-value pair no matter how long the run is. A row that is already choppy, alternating colors constantly, barely compresses at all, since there are no long runs to collapse.
Variable length encoding attacks a different kind of redundancy: unequal frequency. Give common letters short bit codes and rare letters long ones, and the average number of bits per character drops below what fixed-length codes need, even though no letter's meaning changes. Both techniques sit under the same idea as the next topic, lossy compression: squeezing files smaller. The difference is that lossy compression accepts permanent loss of detail, like rounding colors a person can't distinguish, while lossless compression never discards anything real, it only removes redundancy that was recoverable anyway.
Key terms
- Lossless compression
- A way of shrinking a file that allows the exact original data to be reconstructed with no loss.
- Run length encoding
- Replacing a repeated run of identical values with a single count and value pair.
- Variable length encoding
- Assigning shorter bit codes to frequent symbols and longer codes to rare symbols to reduce average size.
- Redundancy
- Predictable, repeated, or uneven patterns in data that compression can exploit without losing information.
Watch it explained
- How it worksHow does run length encoding replace a long stretch of repeated values with a single count?
- How it worksWalk me through giving common letters short codes and rare letters long ones to shrink a file.
- Worked exampleFind the run length encoding of the pixel row WWWWWWBBBWWWWWWWWB and count the bits saved.
- Common mistakeWhy isn't fewer bits automatically the same thing as less information?
Check yourself
End of topic.