Why compress files?
- Compression makes files smaller, so they take up less storage space and are quicker to send or download, using less bandwidth.
Lossy compression
- Lossy compression permanently removes some data, usually detail that people are unlikely to notice. It greatly reduces the file size, but the original can't be recovered exactly.
- It is used for photos (JPEG), music (MP3) and video. It is not suitable for text or program files.
Lossless compression
- Lossless compression makes a file smaller without losing any data, so the original can be recovered exactly.
- It is used for text, program files and some images (PNG). It usually reduces the file size less than lossy compression.
Run-length encoding (RLE)
- RLE stores each run of repeated data as a count and a value: AAAAABBB becomes 5A 3B. In binary, 0000011100 becomes 5 0s, 3 1s and 2 0s.
- It works well when there are long runs of repeated values, but can make data bigger when there are few repeats.
Huffman coding
- Huffman coding gives shorter binary codes to the characters that appear most often, using a Huffman tree. It is lossless.
- Bits needed = the total of (frequency × code length) for each character. A text with 4 As, 2 Bs and 1 C, coded A = 0, B = 10 and C = 11, needs 4 × 1 + 2 × 2 + 1 × 2 = 10 bits, compared with 7 × 7 = 49 bits in 7-bit ASCII.
Key terms
- Compression
- Making a file smaller.
- Lossy compression
- Compression that permanently removes some data.
- Lossless compression
- Compression that keeps all the data, so the original can be recovered exactly.
- Run-length encoding
- Storing runs of repeated data as a count and a value.
- Huffman coding
- Lossless compression that gives shorter codes to more frequent characters.
- Bandwidth
- The amount of data that can be sent over a network each second.
Quick questions on Data compression
- Why are files compressed?
- To make them smaller, so they use less storage and transfer faster: Smaller files also use less bandwidth.
- Which type of compression permanently removes data?
- Lossy: The removed data can't be recovered.
- Which type of compression should be used for a program file?
- Lossless: Losing any data would stop the program working.
- Why is lossy compression not suitable for text?
- Removing data would change the text: Every character matters.
- Which file type usually uses lossy compression?
- MP3: MP3 removes sounds people are unlikely to hear.
- What is AAAAABBB in run-length encoding?
- 5A 3B: Five As followed by three Bs.
- When does run-length encoding work well?
- When there are long runs of repeated values: Each run shrinks to a count and a value.
- What does lossless compression allow?
- The original file to be recovered exactly: No data is lost.
Data compression: questions and answers
- In Huffman coding, which characters get the shortest codes?
- The most frequent characters. This saves the most bits overall.
- With codes A = 0, B = 10 and C = 11, how many bits does 'AABC' take?
- 1 + 1 + 2 + 2 = 6.
- Is Huffman coding lossy or lossless?
- Lossless. The original text can be recovered exactly.