Growing phrase dictionary
Trace a small dictionary encoder and reconstruct the exact starting message.
Adult planning suggestion: about 9–12 · Logic & rule checking
- Players
- 1–4 cooperatively
- Time
- 15–25 minutes
- Materials
- A/B letter cards; numbered dictionary; output log
Prepare
Use input ABABAB and initial dictionary A=1,B=2. Set the working phrase to the first letter A. Keep input, dictionary, working phrase and emitted codes in separate columns. This is a tiny paper dictionary example, not a general file compressor.
Play
For each next letter c, test whether working phrase+c is already a dictionary entry. If yes, extend the working phrase. If no, emit the code for the working phrase, add phrase+c using the next unused integer, and set the working phrase to c. After the last letter emit the remaining phrase once.
Worked example
At the second letter B, emit 1 and add AB=3. At the third A, emit 2 and add BA=4. At the fourth B, AB exists, so extend to AB. At the fifth A, ABA is new: emit 3, add ABA=5, and restart with A. At the sixth B extend to AB, then finish by emitting 3.
Finish and check
The output is 1,2,3,3. For this trace, reconstruct A+B+AB+AB = ABABAB. Each code is one dictionary number, not separate decimal digits. Check the new dictionary entries in creation order: AB3, BA4, ABA5.
Adaptation and limits
Finish after the original message and reconstructed message match character for character. Do not infer a compression ratio from these printed numerals: storage needs a defined code width and dictionary convention. Keep to the supplied trace; general decoding needs additional special-case rules.
Purpose, observation and provenance
Within this activity: Trace a small dictionary encoder and reconstruct the exact starting message.
Observe whether every emitted code already exists and every new phrase receives the next unused number.
Our rules, examples and printable diagrams are separately prepared. The earliest inventor of the broader mechanism is not established here.
CS Field Guide: General purpose compression — Supports adaptive phrase dictionaries; our A/B trace is independently prepared.
Secondary practice: Cooperation and explaining a check.
For a class of 30, use ten groups of three. Prepare one player-material set per group and keep the host key with the adult. Rotate operator, recorder and checker after each worked example; a reader or scribe may help without choosing answers. Avoid public ranking or diagnostic labels.
Age bands are planning suggestions. Background references may address older learners and do not validate suitability for this age band. Goals describe observable actions, not measured long-term gains or institutional endorsement.
Free alternative: Copy the supplied grids, labels and cards onto reused paper. No specialist product is needed. Adults may prepare pieces or act as a scribe.
Printable materials
Preview at 100% scale, with browser headers and footers off. Cut with suitable help. Keep host keys separate. This is a manual tabletop kit, not an online opponent, automatic judge or solver.
Rules to keep beside the materials
- Use input ABABAB and initial dictionary A=1,B=2. Set the working phrase to the first letter A. Keep input, dictionary, working phrase and emitted codes in separate columns. This is a tiny paper dictionary example, not a general file compressor.
- For each next letter c, test whether working phrase+c is already a dictionary entry. If yes, extend the working phrase. If no, emit the code for the working phrase, add phrase+c using the next unused integer, and set the working phrase to c. After the last letter emit the remaining phrase once.
- At the second letter B, emit 1 and add AB=3. At the third A, emit 2 and add BA=4. At the fourth B, AB exists, so extend to AB. At the fifth A, ABA is new: emit 3, add ABA=5, and restart with A. At the sixth B extend to AB, then finish by emitting 3.
- The output is 1,2,3,3. For this trace, reconstruct A+B+AB+AB = ABABAB. Each code is one dictionary number, not separate decimal digits. Check the new dictionary entries in creation order: AB3, BA4, ABA5.
- Finish after the original message and reconstructed message match character for character. Do not infer a compression ratio from these printed numerals: storage needs a defined code width and dictionary convention. Keep to the supplied trace; general decoding needs additional special-case rules.
Growing phrase dictionary — play materials
| Initial phrase | Code |
|---|---|
| A | 1 |
| B | 2 |
| Next letter | Working phrase | Emitted code | New dictionary entry |
|---|---|---|---|
| ________ | ________ | ________ | ________ |
| ________ | ________ | ________ | ________ |
| ________ | ________ | ________ | ________ |
| ________ | ________ | ________ | ________ |
| ________ | ________ | ________ | ________ |
| ________ | ________ | ________ | ________ |
| Decoded code | Phrase |
|---|---|
| ________ | ________ |
| ________ | ________ |
| ________ | ________ |
| ________ | ________ |
Host check — keep private until finished
Output 1,2,3,3; added AB3,BA4,ABA5; reconstruction ABABAB.
These are model answers or legal examples, not records of an experiment or learner outcomes.