Stretch tasks Data Compression, Huffman and RLE

Round 1: Quiz Blitz

1. PNG PNG and ZIP are lossless. JPEG and MP3 are lossy.
2. 5W 2B 6W 3B Five W, two B, six W, three B.
3. Data with no runs gives a pair for every single value ABABABAB becomes eight pairs: sixteen values instead of eight.
4. The most frequent Short codes for common characters cut the total number of bits.
5. The two with the lowest frequencies Joining the lowest pushes rare characters deepest, giving them the longest codes.
6. 42 6 characters x 7 bits = 42 bits.
7. 9 B 2 bits, three As 3 bits, two Ns 4 bits: 9 bits.
8. False Read it from the root down to the leaf.
9. They take less storage; They take less time to send Less storage, faster transmission and less bandwidth.
10. Lossless, so nothing changes Removing characters from a program gives a broken program.
11. True The original can be reconstructed exactly.
12. Frequencies most people cannot hear MP3 is lossy: it discards what listeners are least likely to notice.

Round 2: Quick Fire

1. • It replaces a sequence of repeated values with a count and the value
   • For example, WWWWW becomes 5W
   Model answer

   Run length encoding replaces each sequence of repeated values with a count and the value: WWWWWBB becomes 5W 2B.

2. • No character's code is the start of another's
   • So following the bits from the root always reaches exactly one leaf
   Model answer

   No character's code is the start of another character's code, so following the bits from the root of the tree always reaches exactly one leaf, then decoding starts again at the root.

3. • Lossy permanently removes data, giving a large reduction
   • Lossless reconstructs the original exactly, with a more modest reduction
   Model answer

   Lossy compression permanently removes data, giving a large reduction, and the original cannot be recovered. Lossless compression reconstructs the original exactly, but the reduction is more modest.

4. • 4 pairs of 2 bytes = 8 bytes
   • A saving of 8 bytes, or 50 per cent
   Model answer

   The compressed version is 4 pairs of 2 bytes, which is 8 bytes. The saving is 16 - 8 = 8 bytes, which is 50 per cent.

Round 3: Big Think

1. • Join the two lowest frequencies, B and N, first
   • Codes such as A = 0, N = 10, B = 11
   • The Huffman total is 9 bits
   • ASCII needs 42 bits, so 33 bits are saved
   Model answer

   The frequencies are A 3, N 2 and B 1. Join the two lowest, B and N, into a node worth 3, then join that with A to make the root. Labelling left branches 0 and right branches 1 gives A = 0, N = 10 and B = 11. BANANA then needs 2 + 3 + 4 = 9 bits, compared with 6 x 7 = 42 bits in ASCII, a saving of 33 bits.

2. • Photographs: lossy, such as JPEG, because the eye will not notice
   • Music: lossy, such as MP3, which removes sounds people cannot hear
   • Spreadsheets must be reconstructed exactly, such as in a ZIP
   • Losing data from a spreadsheet would corrupt it
   • Lossy gives much smaller files
   • Smaller files are faster to send and use less bandwidth
   Model answer

   Photographs should use lossy compression such as JPEG, because it discards fine colour detail the eye barely notices, giving much smaller files. Music should also be lossy, such as MP3, which removes frequencies most people cannot hear; smaller files are faster to send and use less bandwidth. Spreadsheets must use lossless compression, such as a ZIP archive, because every value must be reconstructed exactly: removing data would corrupt the numbers.

This or That

1. A logo with flat blocks of colour RLE needs long runs of the same value. Photographs have almost none.
2. No: it stores it more efficiently The original can be rebuilt exactly.
3. 0 Left branches 0 and right branches 1, applied consistently.
4. MP3 ZIP must give back every file exactly.
5. There is less data to send Smaller files use less bandwidth and arrive faster.
6. A Huffman code Each bit chooses a branch until a leaf is reached.
7. Bigger Every run has length one, so the pairs double the size.
8. A broken program That is why code must only ever be compressed losslessly.

Memory Match

• A 4 Lossy: Original cannot be recovered
• B 1 Lossless: Reconstructed exactly
• C 5 RLE: A value and a count for each run
• D 6 Huffman coding: Short codes for frequent characters
• E 3 5W: WWWWW
• F 2 Bandwidth: Data sent in a given time

Sort It

1. Lossy JPEG discards fine colour detail That is lossy compression.
2. Huffman BANANA in 9 bits instead of 42 Huffman coding's saving over 7-bit ASCII.
3. Huffman Codes are read from the root of a tree Huffman codes come from the tree.
4. Run length Can make data with no runs bigger Every run of one becomes a pair.
5. Lossy MP3 removes sounds most people cannot hear MP3 is lossy.
6. Run length Replaces a run of values with a count That is run length encoding.
7. Run length 5W 2B 6W 3B Run length pairs: a count and a value.
8. Huffman Frequent characters get the shortest codes That is Huffman coding.
9. Lossy The original cannot be recovered Lossy compression is irreversible.
10. Huffman Join the two lowest frequencies first That is how a Huffman tree is built.
11. Run length Suits graphics with blocks of flat colour Long runs compress well.