Lesson plan: data compression
This is an example of one approach to teaching data compression. It uses the specification content to set the learning objectives for the lesson. It assumes that the lesson duration is 1 hour.
Topic
3.5.6.7 (AS), 4.5.6.9 (A-level) Data compression
This example of one approach to introducing the topic is designed for a lesson lasting one hour.
Learning objectives
Know why images and sound files are often compressed and that other files, such as text files, can also be compressed.
Understand the difference between lossless and lossy compression and explain the advantages and disadvantages of each.
Explain the principles of run length encoding (RLE) as a technique for lossless compression.
Next lesson: dictionary-based methods.
Prior knowledge needed
Ability to design, code and test simple programs.
Experience of using image viewing and/or sound files and software.
Lesson preparation
Appropriate computer facilities to explore solutions, develop and run code.
Datafile 1: simulated or real data from a weather station or other sensor taking frequent observations over 24 hours. There are likely to be extended runs of unchanging values, making this a good example for compression.
Datafile 2: RAW image file of highest available resolution, ideally showing a fine-detailed subject such as a map.
Image processing software capable of importing RAW image and exporting in both lossy (eg JPEG) and lossless (eg GIF) formats. (eg Irfanview, with plugins installed.)
CD recording of a timeless track (personal taste dictates the choice, but The Grateful Dead have a place in computer science – through the WELL, which has links to the Electronic Frontier Foundation); and an MP3 or compressed YouTube version of the same.
Activity
| Duration | Activity | Group size | Assessment objective |
|---|---|---|---|
| 5 mins | Discuss purpose of compression, such as reduced bandwidth and storage.
Suggested resource: Run Length Encoding Visualization video (1:37) |
Whole class | Understand the point of compressing data. |
| 5 mins |
Consider Datafile 1 or part of it. Estimate a compression ratio. |
Individual | Understand the concept of RLE. |
| 20 mins |
Write and test code to implement a lossless compression algorithm for Datafile1. Compare the output with the estimated compression ratio. Suggested resource for teachers: https://rosettacode.org/wiki/Run-length_encoding Note: if students’ skills and experience make completion of this activity in this time unrealistic, it could be set as homework. |
Individual or pairs |
Practical experience with RLE. Enhance experience of algorithms, coding and testing. |
| 3 mins | Compare the performance of a standard compression utility (eg Zip) on the same file. | Individual or pairs | Experience of widely used utility |
| 15 mins | Load Datafile 2 and experiment with different compressed versions, with varying settings for lossy compression (eg JPEG) and exploring small areas at high magnification. | Individual or pairs |
Observe compression artefacts – perhaps with difficulty Compare file sizes |
| 5 mins | Compare audio quality of CD and compressed versions, using best speakers available. | Whole class |
Observe compression artefacts – or not Discuss uses of different formats |
| 7 mins |
Plenary discussion:
|
Whole class |
Know why images and sound files are often compressed and that other files, such as text files, can also be compressed. Understand the difference between lossless and lossy compression and explain the advantages and disadvantages of each. |
Further work and reading
Extension
Consider the effect of open or restricted licensing on the use of compression algorithms (eg GIF vs PNG).
Explore the working of the Lempel-Ziv-Welch lossless compression algorithm. Where is LZW used? (eg GIF, Pkzip). For example, Elegant Compression in Text (The LZ 77 Method) – Computerphile video.
Preparation for next lesson
Research Huffman compression, eg Text Compression with Huffman Coding
Homework
Compile revision notes or podcasts, perhaps using a class Wiki, on the topic.
Answer specimen/past exam questions.