Year 9 · Spring 2 · Representations: going audio-visual

Lossy vs lossless compression

What this lesson covers

Topic 7 Compression

KS3 Computing · Compression stores the same information in fewer bits. Lossless gets every bit back. Lossy throws away detail you probably won't notice.

Computer SystemsCambridge Lower Secondary Computing 0860

You will learn to

Explain the difference between lossless and lossy compression.
Compress a row of pixels with run-length encoding, and decode it again.
Build a Huffman code from letter counts, so common letters get shorter codes.
Calculate a compression ratio, and compare a zipped text file with a zipped photo.

Success criteria

I can turn WWWWWWWWBBBW into 8W3B1W, and back again.
I can show that my Huffman code uses fewer bits than 8 bits per letter.
I can explain why a zipped photo hardly gets smaller.

Key words

Say each word, then read what it means. Every one is in the glossary too.

RLE: Run-length encoding: store how many and what, for repeats.
Huffman coding: Lossless compression giving common characters short codes.
Lossless: A reversible way of writing the same data in fewer bits. Every bit comes back exactly. ZIP, PNG, FLAC. Needed for text, code and spreadsheets.
Lossy: Throw away detail that people barely notice. The original cannot be recovered. JPEG, MP3, MP4. Fine for photos, music and video.
Compression ratio: Original size ÷ compressed size. A ratio of 4 means a quarter of the size. Percentage saved = (1 − compressed ÷ original) × 100.

The explanation

Read it here, or open the study page below to go one step at a time with things to try.

Lossless vs lossy

	Lossless	Lossy
What happens	Writes repetition more cleverly	Removes detail for ever
Original back?	Yes, exactly	No
Size saving	Medium	Large
Used for	Text, code, PNG, ZIP, FLAC	JPEG, MP3, MP4, streaming

!Watch out

Never use lossy on text or programs. One wrong bit can change a word, a number or an instruction.

Run-length encoding (RLE)

RLE (lossless): instead of writing the same thing many times, write how many and what.

AAAABBBCCD: four A's → 4A.
Three B's → 3B.
Two C's → 2C.
One D → 1D.
Result: 4A3B2C1D. 8 characters instead of 10.

!Watch out

ABCD becomes 1A1B1C1D: twice as long. RLE only helps when things repeat in a row.

Huffman coding

Huffman coding (lossless) gives common characters short codes and rare ones long codes.

Count each letter in BANANA: A = 3, N = 2, B = 1.
Join the two smallest: B(1) + N(2) = group 3.
Join again: A(3) + group(3) = 6. The tree is done.
Label branches: left = 0, right = 1.
Codes: A = 0, B = 10, N = 11.
BANANA → 10 0 11 0 11 0 = 9 bits. ASCII needs 48.

        (6)
       0/ \1
      A(3) (3)
          0/ \1
         B(1) N(2)

?Why?

How does it know where each code ends? No code is the start of another (0, 10, 11). Reading left to right, the first match is always right.

Study it

Open the study page and go one step at a time.

Topic 7 · Year 9

Compression

Compression stores the same information in fewer bits. Lossless gets every bit back. Lossy throws away detail you probably won't notice.

The steps for this lesson

Topic 7, step 3: RLE (Run-length encoder)
Topic 7, step 2: Lossless vs lossy (How much did compression save?)
Topic 7, step 7: Counting the bits (Total bits with Huffman coding)

Try it

Check yourself

One question at a time. The reason shows after each answer.

Saved on this device.