That Blue Square Thing

AQA Computer Science GCSE

24 March 2020: as the position regarding GCSE exams is now a bit clearer, I've decided to stop adding updates to the revision pages.

Data Representation - Compression

Compression involves the reduction in file size of data. Basically finding clever ways to make it smaller.

This is dead handy and makes using the modern internet much easier - iPlayer, Spotify, online multiplayer games, Skype - all of it uses compression to make it possible.

There are two specific methods of compression you need to know about:

PDF iconCompression - intro slides

Run Length Encoding

Run Length Encoding is fairly straightforward. In an exam you might see it applied to text but it's more likely that it will be applied to a bitmap image of some kind - quite possibly a black and white bitmap.

PDF iconCompression and Run Length Encoding - everything you need to know

PDF iconRun Length Encoding examples - slides from class

PDF iconRLE summary - single slide

It is possible to code RLE without too much difficulty. Decoding is easier than encoding an RLE string.

The slides below summarise the basic problem and demonstrate basic algorithms for the process. They could be programmed in Python.

PDF iconRLE Decoding algorithm

PDF iconRLE Encoding algorithm - a little more complex

Huffman Coding

Huffman Coding is more complex when you learn about it. To the extent that it might well appear to be just weird. It uses an idea called a Binary Tree - which is actually used quite widely in all sorts of ways in computing.

The exam board will use Huffman Coding to encode short pieces of text - the chances are they will use a word with no more than 4 letters in it.

PDF iconHuffman Coding basics

PDF iconExample Huffman Tree - a Huffman Tree to work through, preferably with a teacher

PDF iconHuffman Tree questions - the easiest way to learn Huffman Trees is probably to work through some questions

Creating Huffman Trees is a tricky process. It is possible you may need to create one in an exam - although I think that it's quite unlikely. This is how you do it (again, working through two or three of these will get the method in your brain - probably...)

PDF iconCreating Huffman Trees

PDF iconExam board method - in their teacher's guide the exam board does things a little differently. Whilst I don't think you'll see this in an exam, this shows you how they do it.

You can see the solution to the final tree from the exam board example.

There are plenty of web resources which will create Huffman Trees for you. Two are linked to below.

Web Resources for Huffman Trees

Note that the exam board seems to work on the principle that the left-hand branch of a tree is coded using a 0. This follows the wikipedia article on Huffman Coding which says "as a common convention, bit '0' represents following the left child and bit '1' represents following the right child". The problem is that plenty of the Huffman Tree generators on the internet do it the other way around and use 1 for the left brnach and 0 for the right branch.