GCSE · Computer Science · AQA · Spec 8525

Data compression

The letter E turns up everywhere and Q almost never, so why give them codes of the same length? Shorten the common ones and the message shrinks, losing nothing.

Computer Science · Huffman tree

Walk the tree, collect the code

Predict first: which character do you think is closest to the root? Walk to it and see. Then walk to the rarest one and count the turns. Every code you collect is just the 0s and 1s of your route.

1st bit → 2nd bit → 3rd bit → 4th bit

Every code starts here. Each bit you read is a turn: 0 means left, 1 means right.

5 characters, one at each end of the tree.

On Root: start here. 2 branches to choose from.

Characters sit only at the ends of branches, never at a fork. So once you land on a character you are finished with it, which means no code can ever be the start of another code.

Watch out: A code is a route, not a number. 10 means 'right, then left', not 'ten'.

Computer Science · Compression

What do you think compression is?

You have just watched common characters get short codes and rare ones get long codes. Time to check the big ideas behind it.

Which of these is closest to what you think?

Compression saves space by throwing away the least important bits, so some of the original is always lost.Every character has to get a code of the same length, otherwise the computer could not tell where one character stops and the next begins.Compression only helps with storage. It makes no difference to how fast a file can be sent.Compression stores the same data in fewer bits, which saves storage and makes sending quicker with less bandwidth. With Huffman coding and run length encoding the original comes back exactly.

How sure are you?

I'm sureI think soI'm guessing

Compression saves space by throwing away the least important bits, so some of the original is always lost.

This is a common misconception

Some methods do throw detail away, and those are called lossy. Huffman coding and run length encoding are lossless: they write exactly the same data using fewer bits, and decompressing rebuilds the original perfectly. Nothing has been deleted, only re-written.

Every character has to get a code of the same length, otherwise the computer could not tell where one character stops and the next begins.

This is a common misconception

Fixed-length codes are one way to do it, but they are not the only way. Huffman coding uses codes of different lengths, and the computer still knows where each one ends: characters sit only at the ends of the tree's branches, so no code is the start of another. The tree you walked proves it.

Compression only helps with storage. It makes no difference to how fast a file can be sent.

This is a common misconception

Fewer bits means less to send. Compressed data is quicker to transmit and needs less bandwidth, as well as taking up less storage.

Compression stores the same data in fewer bits, which saves storage and makes sending quicker with less bandwidth. With Huffman coding and run length encoding the original comes back exactly.

This matches the evidence

Yes. Fewer bits for the same data is the whole idea, and because these two methods are lossless, nothing is lost on the way back.

Compression means the same data in fewer bits. Huffman coding and run length encoding are lossless: they never throw anything away.

Computer Science · Algorithms

Trace table — dry run the code

That tree did not appear from nowhere. Here is how it is built from the table E 8, T 5, A 3, N 2, Q 1. Step through it. A bracket like (QN) is a joined node, and the number after the colon is its frequency.

1Write every character as a node with its frequency

2REPEAT

3 pick the two nodes with the lowest frequencies

4 join them under a new parent node (frequency = their sum)

5UNTIL only one node is left: the root

6Label every left branch 0 and every right branch 1

Nodes in the list

Two lowest

New parent

Press Start to run the first line.

Ready when you are — step through one line at a time.

Computer Science · Sizes

How many bits did Huffman save?

A message has 19 characters: E appears 8 times, T 5 times, A 3 times, N twice and Q once. The Huffman codes are E = 0, T = 10, A = 110, Q = 1110 and N = 1111. Taking ASCII as 7 bits per character, how many bits does Huffman coding save? Fill in the missing steps.

E: 8 characters × 1 bit = 8 bitsEach character's frequency is multiplied by the length of its own code.
missing step

Which line is step 2?

T: 5 characters × 2 bits = 10 bitsT: 5 characters × 1 bit = 5 bitsT: 5 characters × 10 = 50 bitsT: 5 + 2 = 7 bits

Computer Science · Run length encoding

Squash the runs

The row to encode is R R R R G G B B B B B. Step along it and watch the pairs appear.

Before you step: how many runs of identical values do you think this row has?

 1  count = 1
 2  FOR each next value in the row
 3    IF it matches the previous value THEN count = count + 1
 4    ELSE write the pair (count, previous value) and set count = 1
 5  After the last value, write the final pair

Variables

count=1pairs written=none yetprevious value=R

Output

Step 1: The first value is R, and we have seen one of it so far.

1 / 12

Step through the trace — every value is the lesson’s, not run by the page.

Step 1 of 12: The first value is R, and we have seen one of it so far..

Predict, then check

Both rows are 12 values long. RLE writes each run as a frequency/data pair.

Row X is A A A A A A A A A A A A. Row Y is A B A B A B A B A B A B. Which row gets BIGGER after RLE?

WHAT YOU'VE LEARNED

A quick recap of today's lesson.

Fewer bits, same data: how common characters get short codes, and when repeats can be squashed.

What you need to know

Compression stores the same data in fewer bits, so it takes less storage and travels faster with less bandwidth.
Huffman coding and run length encoding are lossless: the original is rebuilt exactly.
In a Huffman tree the common characters are near the root with short codes, the rare ones are deep with long codes, and no code is the start of another.
Huffman size = sum of (frequency × code length). Uncompressed size = number of characters × bits per character.
RLE writes each run as a frequency/data pair. It shrinks data with long runs and can enlarge data that keeps changing.

The big picture

Compression stores the same data in fewer bits, which saves storage and makes sending quicker. Huffman coding gives common characters short codes and rare ones long codes, read by walking a tree from the root to a leaf. Run length encoding swaps each run of identical values for a frequency/data pair. Both are lossless, and RLE can backfire on data that keeps changing.

Key points

1Compression means fewer bits for the same data, so less storage and faster, lower-bandwidth transmission.

2Lossless means nothing is thrown away. Huffman coding and RLE are both lossless.

3Build a Huffman tree by joining the two lowest-frequency nodes again and again until one root remains.

4Read a code by walking from the root to the leaf: left is 0, right is 1. Decode by returning to the root after each leaf.

5Characters only sit at leaves, so no Huffman code is the start of another and decoding is never ambiguous.

6To compare sizes, multiply frequency by code length and add, then compare with number of characters × bits per character.

7RLE replaces each run with a frequency/data pair. It helps with long runs and hurts when values keep changing.

.we-_R_18slubsnpfiv5ubrb_ [data-we-step]{display:flex !important}.we-_R_18slubsnpfiv5ubrb_ [data-we-solution]{display:block !important}.we-_R_18slubsnpfiv5ubrb_ [data-we-reveal]{display:none !important}

Worked example

Problem

Using the tree from the top of the page (E = 0, T = 10, A = 110, Q = 1110, N = 1111), decode the bit stream 0101101111.

⚠ Watch out

Treating a code as a number. The code 10 is a route (right, then left) with a length of 2, not the value ten. In size sums, multiply each frequency by its code's length, and count every character, repeats included, for ASCII.

🧠

Memory hook

Busy letters live by the front door (the root). Rare letters live at the bottom of the garden, and it takes a long walk to reach them.

✓

Check yourself

Without looking back: why does E get a one-bit code while Q gets four bits, and what would go wrong if one code were the beginning of another?

Flashcards

(11)

What does data compression do, and why bother?

It stores the same data using fewer bits. That saves storage space and makes data quicker to send, with less bandwidth.

What does 'lossless' mean?

The original data can be rebuilt exactly from the compressed version. Huffman coding and run length encoding are both lossless.

ASCII codes are all the same length. How are Huffman codes different?

Huffman codes have different lengths. Common characters get short codes and rare characters get long ones.

How do you build a Huffman tree from a frequency table?

Repeatedly pick the two nodes with the lowest frequencies and join them under a new parent whose frequency is their sum. Stop when one node, the root, is left.

How do you read a character's code from a Huffman tree?

Walk from the root to the character's leaf. Write 0 for each left branch and 1 for each right branch. The 0s and 1s in order are the code.

While decoding, what do you do the moment you land on a leaf?

That character is finished. Note it down and return to the root before reading the next bit.

Why can a decoder tell where one Huffman code ends?

Characters sit only at the ends of branches, so no code is the start of another. Landing on a leaf means that character is complete.

How do you work out the size of data after Huffman coding?

Multiply each character's frequency by the length of its own code, then add the results. Take that away from the uncompressed size to find the saving.

How do you work out the uncompressed size of text in ASCII?

Multiply the number of characters by the bits per character. Use the number the question gives you: in this course ASCII is 7 bits per character unless told otherwise.

What does run length encoding (RLE) do?

It replaces each run of identical values with a frequency/data pair, such as (5, B) for five Bs in a row. It is lossless.

When does RLE help, and when can it hurt?

It helps when the data has long runs of repeated values. When values keep changing, every run is short, so RLE can make the data bigger.

Tap any card to flip it, or use Study as deck to go through them one at a time. In the full lesson these run as a spaced-repetition deck — you rate each card Hard, Good or Easy and the tricky ones keep coming back until they stick.

Learning with Lightbulb is opening soon

You can use this lesson now. Join the waitlist and we'll let you know when the full Lightbulb experience is ready.

Keep me posted

Walk the tree, collect the code

What do you think compression is?

Trace table — dry run the code

How many bits did Huffman save?

Squash the runs

More AQA GCSE Computer Science topics