Data Compression, Huffman and RLE

1 State two reasons why a file might be compressed before being sent over the internet. 2

One mark for each of the following, to a maximum of 2.

• It takes less time to transmit
• It uses less bandwidth, or takes less storage space at the other end

Model answer. A compressed file contains fewer bits, so it takes less time to send, which matters particularly on a slow connection. It also uses less bandwidth, which reduces congestion on the network and lowers the cost for anybody paying for the data they use.

2 Explain the difference between lossy and lossless compression, and give one appropriate use of each. 4

One mark for each of the following, to a maximum of 4.

• Lossy compression permanently removes data, so the original cannot be recovered
• Gives a suitable lossy use such as photographs, music or video
• Lossless compression stores the same data more efficiently, so the original is recovered exactly
• Gives a suitable lossless use such as text, program code or a spreadsheet

Model answer. Lossy compression achieves a large reduction by permanently discarding data judged to be less important, which means the original file cannot be reconstructed exactly. It is appropriate for photographs and music, where human perception does not register the detail that is removed, which is why JPEG and MP3 are used. Lossless compression instead finds a more efficient way of storing exactly the same information, so the original is recovered perfectly, at the cost of a more modest reduction in size. It is essential for text documents, program code and spreadsheets, where every character carries meaning and discarding any of it would corrupt the file.

3 A row of an image contains the pixels W W W W B B W W W W W W. Show how this row would be stored using run length encoding, and state one reason why RLE would be a poor choice for a photograph. 4

One mark for each of the following, to a maximum of 4.

• Identifies the runs correctly as four W, two B, six W
• Writes them as value and count pairs
• A photograph has very few long runs of identical pixels
• So RLE would give little saving and could make the file larger

Model answer. The row contains four W, then two B, then six W, so under run length encoding it is stored as the pairs 4W, 2B, 6W. That is three pairs, six values in total, in place of the original twelve, and nothing has been lost. Run length encoding would be a poor choice for a photograph because photographs contain gradients and noise rather than blocks of identical colour, so almost every run has a length of one. Each single pixel would then be stored as a value and a count, which is two values where one was needed, and the compressed file would be larger than the original.

4 The word ABRACADABRA is to be compressed using Huffman coding. Describe how the Huffman tree would be constructed, and explain how the code for a character is obtained from it. 5

One mark for each of the following, to a maximum of 5.

• Counts the frequency of each character
• Creates a node for each character with its frequency
• Repeatedly combines the two nodes with the lowest frequencies under a new parent
• Continues until one root node remains, and labels branches 0 and 1
• A character's code is read by following the branch labels from the root down to that character

Model answer. First count how often each character occurs: A appears five times, B twice, R twice, C once and D once. Each character becomes a node carrying its frequency. The two nodes with the lowest frequencies, C and D, are then joined under a new parent node whose frequency is their total of two. That process repeats, always taking the two lowest frequencies still available, until a single root node remains holding the total of eleven. Every left branch is then labelled 0 and every right branch 1. To obtain the code for a character you start at the root and follow the branches down to that character's leaf, writing down each label as you pass it. Because A is the most frequent it ends up nearest the root and gets the shortest code, while C and D are deepest and get the longest, which is what makes the total number of bits smaller than fixed length coding would need.

5 A message of 40 characters is stored in 7 bit ASCII. After Huffman coding it needs 148 bits. Calculate the number of bits saved and the saving as a percentage of the original. 3

One mark for each of the following, to a maximum of 3.

• Calculates the ASCII size as 280 bits
• Calculates the saving as 132 bits
• Gives approximately 47 per cent

Model answer. In 7 bit ASCII the message takes 40 multiplied by 7, which is 280 bits. Huffman coding needs 148 bits, so the saving is 280 minus 148, which is 132 bits. As a percentage of the original that is 132 divided by 280, which is 0.4714, or approximately 47 per cent.