Pilot · L08 · 50 minutes
Compression and information loss
Encode and decode text with a stated lossless dictionary, count the dictionary as overhead when comparing sizes, explain what a deliberately lossy model discards, choose between lossless and lossy for a stated purpose, and separate compression from confidentiality.
Topics: 2.2 Data Compression
Goals and vocabulary
By the end you can:
- Decode a message with a stated dictionary and check it matches the original.
- Compare original and encoded sizes including dictionary overhead.
- Explain what a lossy method discards and why the original cannot be recovered.
- Choose lossless or lossy compression for a stated purpose and justify it.
- Explain why compression does not keep data confidential.
- Compression
- Representing data with fewer bits.
- Lossless
- Compression from which the exact original can be recovered.
- Lossy
- Compression that permanently discards some information to save more space.
- Dictionary
- A table that says what each short code stands for.
- Overhead
- Extra data, such as a dictionary, that must be sent along with the payload.
- Encryption
- Transforming data so only someone with the key can read it.
Why compress, and the two kinds
Compression stores or sends data using fewer bits. There are two kinds, and the difference is whether the original can be recovered exactly.
| Row | Lossless | Lossy |
|---|---|---|
| Original recoverable? | Yes, exactly, bit for bit. | No. Some information is deliberately discarded. |
| Typical size saving | Usually smaller savings. | Usually much larger savings. |
| Good for | Text, source code, spreadsheets — anything where one changed character matters. | Photos, audio and video previews, where people may not notice small losses. |
A lossless dictionary encoding
Worked example
One lossless approach replaces repeated pieces of text with short codes and stores a dictionary saying what each code means. Anyone with the dictionary can rebuild the exact original.
1 → "go"2 → "team "| Step | Text |
|---|---|
| Original | team team go |
| Encoded codes | 2 2 1 |
| Decoded with the dictionary | "team " + "team " + "go" = team team go |
The decoded text is identical to the original, which is what makes this lossless. If a code is not in the dictionary, the decoder must report it as unknown rather than guess.
Overhead: the dictionary costs space too
The receiver needs the dictionary, so it is part of the cost. The real size is payload plus dictionary.
| Part | Bytes |
|---|---|
| Original message | 20 |
| Encoded payload | 12 |
| Dictionary | 10 |
| Total sent | 12 + 10 = 22 |
Here the encoded version is 2 bytes larger than the original. Dictionary encoding pays off only when there is enough repetition for the savings to exceed the dictionary’s size.
Lossy: discarding information on purpose
A lossy method keeps what matters most for the purpose and throws the rest away. A simple model: store a fictional photo’s brightness values rounded to the nearest 10.
| Original brightness | Stored (nearest 10) |
|---|---|
| 143 | 140 |
| 147 | 150 |
| 151 | 150 |
147 and 151 are both stored as 150. Once stored, nothing can tell them apart again, so the original cannot be recovered. That is acceptable for a small preview image and unacceptable for a bank balance.
Compressed does not mean secret
Compression and encryption have different goals. Compression reduces size; its method and dictionary are meant to be shared so anyone can decompress. Encryption keeps content confidential so that only someone with the key can read it.
Explore each concept
Choose a concept, change its inputs and follow the explanation. Each example models the stated rule or scenario; completing it is practice rather than evidence of mastery.
- Dictionary reconstruction
- Lossy collisions
- Purpose and recovery requirements
Change it · step through · explain
Change an input, predict what will happen, then advance one step. Read why the state changes, reset and experiment. This fixed teaching model does not save progress or award XP.
Ready · Make a prediction
- EncodingdictionaryWaiting
- Original messageteam go teamWaiting
Ready to explore: Decode losslessly or discard information
Why: Change an input, predict the first effect, then advance one step.
Try this: Change one input or choose another listed case. Predict the effect, reset and compare the states and governing rule.
Step through and experiment
Change it · step through · explain
Change an input, predict what will happen, then advance one step. Read why the state changes, reset and experiment. This fixed teaching model does not save progress or award XP.
Ready · Make a prediction
- Input 120Waiting
- Input 212Waiting
- Input 310Waiting
Ready to experiment
Why: Predict the first change, then advance one step.
Try this: Make payload + dictionary equal the original, then change it by one byte.
Common misconceptions
Encoding always makes data smaller
The belief: A dictionary encoding is always smaller than the original.
What is actually true: The dictionary is overhead. With little repetition, payload + dictionary can exceed the original.
Check yourself: Did you add the dictionary’s size?
Lossy data can be restored later
The belief: A good program can rebuild the full-quality original from a lossy file.
What is actually true: Lossy compression discards information permanently; different originals can become identical.
Check yourself: Could you tell 147 from 151 after rounding to 150?
Compressed means encrypted
The belief: No one can read a compressed file without permission.
What is actually true: Decompression is designed to be easy; confidentiality needs encryption.
Check yourself: Who has the tool or dictionary needed to decompress it?
Guided practice
Guided: decode and count
Use this dictionary: 1 → "the ", 2 → "cat ", 3 → "sat".
1 2 3- Decode the message and write the result.
- Decode 1 2 1 2 3, then explain whether the dictionary saves more space for this longer message.
- Decode 1 4 and explain what a correct decoder should do with 4.
- Is this encoding lossless? Give evidence from your decoding.
Independent practice
Independent: choose a method
For each fictional situation, choose lossless or lossy and justify your choice.
- A teacher archives students’ program source code.
- A school app shows small preview photos on slow phone connections.
- A message is 20 bytes; its payload is 12 bytes and its dictionary 10 bytes. Is the encoded version worth sending? Show the sizes.
- A classmate says their compressed file is safe from snooping. Respond to that claim.
Exit check
- With dictionary 1 → "red ", 2 → "blue", decode 1 1 2 and say whether the original can be recovered exactly.
- Give one situation where lossy compression is acceptable and one where it is not, with a reason for each.
Check yourself
Practice only: answers are checked in your browser and nothing is saved or sent to your teacher. Each explanation links back to the section it practises.
Lesson practice
Your practice so far
Check an answer to see its rationale.
Apply it somewhere new
Your practice so far
Check an answer to see its rationale.