Skip to main content
CSP LabBy Educator Today
AP CSP course

C11 · Topic 2.2 · 40 minutes · DAT-1.D

Recovering compressed information

By the end you can:

  • Encode and decode with an explicit dictionary.
  • Identify information needed for exact recovery.
  • Include decoding overhead in a size comparison.

Before this lesson: topics 2.1.

Lossless compression
An encoding that allows exact reconstruction of the original data.
Lossy compression
An encoding that discards distinctions so exact reconstruction is not generally possible.

Understand

Compression represents information using a form that can require fewer bits for some inputs. A lossless method must allow exact reconstruction, including the information its decoder needs. A dictionary code without its dictionary or an unambiguous format cannot justify a claim of exact recovery.

Compression does not guarantee that every possible file gets smaller. Required dictionary, header or format information can outweigh payload savings on short messages. Compare the full sizes for the supplied system rather than counting only the most favourable component.

Worked example

Dictionary 1=team,2=go; codes are separated by spaces. The message team team go encodes as 1 1 2.

  1. Decode each code using the supplied dictionary to reconstruct team team go exactly.
  2. An unknown code 3 cannot be decoded by guessing.
  3. If payload 12 and dictionary 10 replace an original 20 bytes, total 22 is 2 bytes larger.

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
Open this example on its own

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

Ready to explore: Decode losslessly or discard information
  1. EncodingdictionaryWaiting
  2. 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

Ready to experiment
  1. Input 120Waiting
  2. Input 212Waiting
  3. 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.

Check a misconception

Claim: Any dictionary replacement necessarily reduces total size.

Required dictionary/format overhead can make a short encoding larger.

Guided practice

Encode go team go and explain what the receiver needs.

Work with a partner. Make a prediction, compare your reasoning, then identify the rule that supports your answer.

Independent transfer

Give a concrete original size for which 12 payload plus 10 dictionary saves space, and calculate the saving.

Exit check

Does an encoded unknown symbol establish losslessness?

Write your reasoning before comparing with a classmate. If your teacher assigned this task, submit it through My classes to save your work and receive feedback.

Check yourself

  1. Question 1 of 2Which property defines lossless compression?

    Select one answer.

  2. Question 2 of 2Original 30 bytes, payload 18, required header 5. What is saved?

    Select one answer.

Your practice so far

Check an answer to see its rationale.

Teacher guidance and scoring