CS22: Data Compression
Lossy and lossless compression methods including Huffman coding and run length encoding, and when to use each type.
📋 Why Compress Data?
Definition: Data compression reduces the number of bits needed to represent data. This saves storage space and reduces the time needed to transmit data over a network.
Uncompressed files can be very large. A single uncompressed 3-minute CD-quality song is about 30 MB. A high-resolution photograph can be 50 MB or more. Compression makes files smaller so they take up less storage and can be transmitted faster.
- Reduces file size - saves storage space on disk
- Reduces transmission time - faster uploads and downloads
- Reduces bandwidth usage - cheaper for data-heavy applications
- Essential for streaming media (video, music) over the internet
- Two main types: lossy and lossless
⚖️ Lossy vs Lossless Compression
| Property | Lossy Compression | Lossless Compression |
|---|---|---|
| How it works | Permanently removes data that is less important or noticeable | Reduces file size without losing any data |
| Data recovery | Original data CANNOT be fully restored | Original data CAN be fully restored |
| Compression ratio | Higher (much smaller files) | Lower (moderately smaller files) |
| Quality | Some quality is lost | No quality loss - exact original |
| File examples | JPEG, MP3, MP4 | PNG, FLAC, ZIP |
| Typical use | Streaming, web images, music | Text files, code, medical images, archives |
Key Difference: Lossy compression discards some data permanently - you cannot get the original back. Lossless compression finds more efficient ways to represent the same data - the original can be perfectly reconstructed.
Example
A 50 MB uncompressed WAV file can be compressed to about 5 MB as an MP3 (lossy) or about 30 MB as a FLAC file (lossless). The MP3 loses audio detail that most listeners won't notice. The FLAC preserves every detail of the original recording.
🌳 Huffman Coding (Lossless)
Definition: Huffman coding is a lossless compression algorithm that assigns shorter binary codes to more frequently occurring characters and longer codes to less frequent characters.
How Huffman Coding Works
- Count the frequency of each character in the data
- Build a Huffman tree by repeatedly combining the two lowest-frequency nodes
- Assign binary codes: left branch = 0, right branch = 1
- More frequent characters get shorter codes (closer to the root)
- Less frequent characters get longer codes (further from the root)
Constructing a Huffman Tree - Step by Step
Worked Example
Data: "ABRACADABRA"
Step 1: Count frequencies:
A = 5, B = 2, R = 2, C = 1, D = 1
Step 2: Build the tree (combine two lowest each time):
Combine C(1) and D(1) → CD(2)
Combine B(2) and R(2) → BR(4)
Combine CD(2) and BR(4) → CDBR(6)
Combine A(5) and CDBR(6) → root(11)
Step 3: Assign codes (left=0, right=1):
A = 0 (1 bit - most frequent)
C = 100 (3 bits)
D = 101 (3 bits)
B = 110 (3 bits)
R = 111 (3 bits)
Calculating Bit Length with Huffman Coding
Bit Length Calculation
Using "ABRACADABRA" with the codes above:
A(5 chars x 1 bit) = 5 bits
B(2 chars x 3 bits) = 6 bits
R(2 chars x 3 bits) = 6 bits
C(1 char x 3 bits) = 3 bits
D(1 char x 3 bits) = 3 bits
Total Huffman = 23 bits
Comparing to Fixed-Length Encoding
Comparison
With 5 distinct characters, fixed-length encoding needs 3 bits per character (22=4 is too few, 23=8 is enough).
Fixed-length total = 11 characters x 3 bits = 33 bits
Huffman total = 23 bits
Saving = 33 - 23 = 10 bits (30.3% reduction)
Huffman Key Points:
More frequent characters = shorter code
Less frequent characters = longer code
No code is a prefix of another (prefix-free property)
This means the encoded data can be uniquely decoded
More frequent characters = shorter code
Less frequent characters = longer code
No code is a prefix of another (prefix-free property)
This means the encoded data can be uniquely decoded
🔢 Run Length Encoding (RLE) (Lossless)
Definition: Run length encoding (RLE) is a lossless compression method that replaces sequences of the same data value (runs) with a count and the value, stored as frequency/data pairs.
How RLE Works
RLE is most effective when data contains long runs of repeated values. Instead of storing each value individually, it stores the count followed by the value.
Example 1: Simple RLE
Uncompressed: AAAAAABBCCCCCCDDDDDD
Compressed with RLE: 6A2B6C6D
Original = 20 characters; Compressed = 8 characters
This is a significant saving because there are many repeated runs.
Example 2: RLE with Bitmap Images
A row of a bitmap image with 1-bit colour depth:
Uncompressed: 000000001111111100000000
RLE: 0,8 1,8 0,8 (frequency,data pairs)
Original = 24 values; Compressed = 6 values
Example 3: When RLE Doesn't Work Well
Data: ABCDEFGHIJKLMNOP
RLE: 1A1B1C1D1E1F1G1H1I1J1K1L1M1N1O1P
Original = 16 characters; Compressed = 32 characters
RLE actually makes the file LARGER when there are no repeated runs. Each character needs a count of 1 plus the character itself.
Important: RLE only works well when data has many consecutive repeated values. It is very effective for simple graphics with large areas of the same colour (like icons or diagrams) but poor for complex data with little repetition (like photographs or random data).
🔄 When to Use Each Compression Type
| Scenario | Best Compression | Why |
|---|---|---|
| Streaming music online | Lossy (MP3) | Small file size needed; slight quality loss acceptable |
| Archiving important documents | Lossless (ZIP) | Must preserve exact data; no data loss acceptable |
| Web page photographs | Lossy (JPEG) | Fast loading important; small visual difference OK |
| Medical imaging (X-rays) | Lossless (PNG) | Every detail matters for diagnosis |
| Simple bitmap with blocks of colour | RLE | Long runs of same colour compress very well |
| Text with varying character frequencies | Huffman coding | Frequent characters get short codes, saving space |
| Source code files | Lossless (ZIP/Huffman) | Code must be exact - no data loss acceptable |
| Video streaming (Netflix, YouTube) | Lossy (MP4/H.264) | Massive size reduction needed; some quality loss OK |
Rule of Thumb: Use lossy when small file size matters more than perfect accuracy (media streaming, web images). Use lossless when data integrity is essential (documents, code, medical images). Use RLE when data has long runs of identical values. Use Huffman when characters have varying frequencies.
⚠️ Common Mistakes to Avoid
| Mistake | Why It's Wrong | How to Fix It |
|---|---|---|
| Saying "lossy compression is bad because it loses data" | Lossy is ideal for many purposes where small size matters | Consider the use case - streaming needs lossy |
| Building Huffman tree incorrectly | Must always combine the TWO lowest frequency nodes | |
| Forgetting RLE can increase file size | RLE adds a count to every value, even singles | RLE is only effective with long repeated runs |
| Not comparing Huffman to fixed-length | Exam questions often ask for the comparison | Calculate both and show the saving |
| Confusing Huffman with RLE | They work on completely different principles | Huffman = variable-length codes; RLE = frequency/data pairs |
❓ Practice Questions
Q1: Explain the difference between lossy and lossless compression.
Q2: The string "MISSISSIPPI" has these character frequencies: M=1, I=4, S=4, P=2. Construct a Huffman tree and assign codes to each character.
Q3: Using the Huffman codes from Q2, calculate the total bit length of "MISSISSIPPI" and compare it to a fixed-length encoding.
Q4: Apply run length encoding to this bitmap row: 111110000011111
Q5: Explain why RLE would not be a good compression method for a photograph.
✅ Answers
- Lossy compression permanently removes some data to achieve a smaller file size; the original cannot be restored. Lossless compression reduces file size without losing any data; the original can be perfectly reconstructed.
- Combine M(1) and P(2) → MP(3). Combine MP(3) and I(4) or S(4): e.g. MP(3) and one of the 4s → e.g. MP(3) + I(4) = MPI(7). Then MPI(7) + S(4) = root(11). Codes will vary depending on tree construction, but shorter codes for I and S, longer for M and P.
- With 4 characters, fixed-length needs 2 bits each. Fixed = 11 x 2 = 22 bits. Huffman depends on your tree from Q2, but should be fewer than 22 bits (likely around 18-19 bits). The saving comes from I and S having short codes.
- RLE: 5,1 5,0 5,1 (or 51150051 depending on notation). Original = 15 values; Compressed = 6 values.
- A photograph contains thousands of subtly different colours in adjacent pixels, with very few long runs of identical values. RLE would produce frequency/data pairs for nearly every pixel, making the compressed file similar in size to or larger than the original. Lossy compression (JPEG) is better for photographs.
🎯 Exam Tips
- Know the difference between lossy and lossless and give examples of each
- Practise building Huffman trees step by step - show all stages
- Always compare Huffman encoding to fixed-length and calculate the saving
- Remember RLE uses frequency/data pairs - show the format clearly
- Explain WHY a compression method is suitable for a given scenario, not just which one
- For Huffman, remember: no code is a prefix of another code
- State that RLE can increase file size if data has few repeated runs
⚠️ Common Errors
✗ Confusing lossy and lossless compression ✓ Lossy compression permanently removes data to reduce file size; the original cannot be restored. Lossless compression reduces file size without losing any data; the original can be perfectly reconstructed.
✗ Thinking lossy compression makes files useless ✓ Lossy compression removes data that is less noticeable to humans (e.g. high frequencies in audio, fine detail in images). The result is still usable — just not identical to the original.
✗ Not understanding how RLE works — thinking it compresses all data ✓ Run-length encoding (RLE) only compresses data with repeated sequences. Data without repetition (e.g. ABCDEF) would actually increase in size with RLE, not decrease.
✗ Believing lossless compression can achieve any compression ratio ✓ Lossless compression has limits based on the information content of the data. Typical lossless ratios are 2:1 to 3:1; claiming 100:1 for lossless is unrealistic.
✍️ Model Answer
Full-Mark Response
A bitmap image contains the following pixel data: RRRRGGGGBBBBYYYY. Explain how run-length encoding would compress this data, and calculate the compression ratio. [4 marks]
Original data: RRRRGGGGBBBBYYYY (16 characters) RLE compression stores each colour and its count: R4G4B4Y4 (8 characters) Each run is encoded as: colour character + count digit. Compression ratio = original size ÷ compressed size = 16 ÷ 8 = 2:1 The data has been compressed to half its original size. RLE is effective here because the data contains long runs of identical values. If the data were RGBYRGBY (no repeats), RLE would not compress it effectively.
📊 AO Deep Dive
Assessment Objective Analysis
AO1 (Computational Thinking — 40%): Demonstrate knowledge and understanding of the principles and concepts of computer science, including data compression: lossy and lossless methods for AQA 8525, OCR J277 & Edexcel 1CP2.
AO2 (Application — 40%): Apply knowledge and understanding of computer science, including data compression: lossy and lossless methods to analyse problems in computational terms and to design, write and evaluate solutions.
AO3 (Evaluation — 20%): Evaluate the effectiveness, correctness and efficiency of computational solutions, including data compression: lossy and lossless methods, and make reasoned judgements about trade-offs.
📝 Exam Technique
GCSE Computer Science Exam Tips:
Lossy: permanently removes data, smaller files, cannot reconstruct original. Use for streaming, photos, music. Lossless: no data loss, larger files, exact reconstruction. Use for text, code, medical images. RLE: stores (value, count) pairs for repeated data. Effectiveness depends on repetition length. When asked which to use, consider: is exact reproduction needed? Is the data text/audio/video?
Lossy: permanently removes data, smaller files, cannot reconstruct original. Use for streaming, photos, music. Lossless: no data loss, larger files, exact reconstruction. Use for text, code, medical images. RLE: stores (value, count) pairs for repeated data. Effectiveness depends on repetition length. When asked which to use, consider: is exact reproduction needed? Is the data text/audio/video?
📝 Exam Questions by Topic
- AQA Past Papers - Topic Questions -- AQA
- Edexcel Past Papers - Topic Questions -- Edexcel
- OCR Past Papers - Topic Questions -- OCR
- Eduqas Past Papers - Topic Questions -- Eduqas
🎬 Video Resources
Ready to ace your GCSE Computer Science exams?
Get the best revision books and guides to boost your grades.