What is data compression and why do we need it?
Compression means storing the same information using fewer bits. A program called an encoder makes the file smaller. A decoder opens it again.
- Less storage: more photos and songs fit on a phone.
- Faster transfer: smaller files download and upload faster and use less mobile data.
- Less bandwidth: video calls and streaming work even on slower networks.
Compression works because real data has redundancy: repeated values, common letters, or detail our eyes and ears do not notice. The price is time: the computer must spend work to compress and decompress.
Lossless and lossy compression
Lossless compression gives back exactly the original bits. We need it for text, program files, spreadsheets and anything where one wrong bit matters. Examples: ZIP, PNG, GIF, FLAC.
Lossy compression removes detail that people are unlikely to notice: tiny colour changes in a photo, very high or masked sounds in music. Files become much smaller, but the removed data is gone for ever. Examples: JPEG photos, MP3 and AAC music, MP4 video.
| Lossless | Lossy | |
|---|---|---|
| Original back? | Yes, exactly | No, close copy |
| Size saving | Smaller | Much bigger |
| Good for | text, code, data | photos, music, video |
Run-length encoding (RLE)
A run is a group of the same value next to each other. RLE stores each run as a pair: (count, value).
Example: WWWWWWBBBWWWWWWW becomes 6W 3B 7W, or as numbers 6 0 3 1 7 0 if white = 0 and black = 1.
RLE is great for images with large flat areas (icons, cartoons, scanned pages). It can make data bigger if values rarely repeat: ABCD becomes 1A 1B 1C 1D, which is twice as long.
Huffman coding and dictionary methods
Normal ASCII gives every character 8 bits. Huffman coding gives short codes to frequent symbols and long codes to rare ones.
- Count how often each symbol appears.
- Take the two least frequent items and join them into one node whose count is their sum.
- Repeat until one tree is left.
- Read codes from the root: left branch = 0, right branch = 1.
In ABRACADABRA: A×5, B×2, R×2, C×1, D×1. One Huffman tree gives A = 0, R = 10, B = 110, C = 1110, D = 1111. Total = 5×1 + 2×2 + 2×3 + 1×4 + 1×4 = 23 bits instead of 11 × 8 = 88 bits.
Huffman codes are prefix-free: no code is the start of another, so the decoder never gets confused. The tree (or the code table) must be stored with the file.
Dictionary methods
Methods like LZ (used in ZIP and PNG) keep a dictionary of patterns already seen. When a pattern repeats, they store a short reference ("go back 12 places, copy 5") instead of the pattern itself.
Measuring compression
Compression ratio = original size ÷ compressed size. A 10 MB file squeezed to 2 MB has a ratio of 5 : 1.
Space saving = (original − compressed) ÷ original × 100%. Here (10 − 2) ÷ 10 = 80%.
For images: raw size (bits) = width × height × colour depth. Fewer bits per pixel or fewer pixels means a smaller file, but lower quality. A good choice balances quality, size and speed.
Key formulas and definitions
- Compression ratio = original size ÷ compressed size
- Space saving (%) = (original − compressed) ÷ original × 100
- RLE: each run → (count, value)
- Huffman total bits = Σ (frequency × code length)
- Uncompressed text bits = number of characters × bits per character
- Raw image bits = width × height × colour depth
Worked examples
1. Encode AAAABBBCCD with RLE.
Runs: AAAA, BBB, CC, D. RLE: 4A 3B 2C 1D. 10 characters became 8 symbols (4 pairs).
2. A 12 MB video is compressed to 3 MB. Find the ratio and the space saving.
Ratio = 12 ÷ 3 = 4 : 1. Saving = (12 − 3) ÷ 12 × 100 = 75%.
3. Which compression would you use for (a) a school report in a word processor, (b) a holiday photo for social media?
(a) Lossless – every letter must stay exactly right. (b) Lossy (JPEG) – a tiny loss of colour detail is fine and the file becomes much smaller.
4. Symbols: E×6, T×3, A×2, Z×1. Huffman codes E = 0, T = 10, A = 110, Z = 111. How many bits are needed? How many in 8-bit ASCII?
Huffman: 6×1 + 3×2 + 2×3 + 1×3 = 6 + 6 + 6 + 3 = 21 bits. ASCII: 12 characters × 8 = 96 bits. Ratio ≈ 4.6 : 1.
5. Decode 0101100 using A = 0, R = 10, B = 110.
Read from the left and stop as soon as a code matches: 0 → A, 10 → R, 110 → B, 0 → A. Answer: ARBA.
6. A 1000 × 800 image uses 24-bit colour. Find its raw size in kB. Lossy compression gives a 120 kB file. What is the ratio?
Bits = 1000 × 800 × 24 = 19 200 000. Bytes = 2 400 000 = 2400 kB. Ratio = 2400 ÷ 120 = 20 : 1.
Common mistakes
- Thinking lossy files can be 'uncompressed' back to the original. The removed detail is gone for ever.
- Using RLE on data with few repeats. ABCDEF becomes 1A1B1C1D1E1F, which is bigger.
- Giving the most common symbol the longest Huffman code. It is the other way round: common = short.
- Writing the ratio upside down. Ratio = original ÷ compressed, so it is bigger than 1 when the file shrinks.