Community resourceWorksheet

OCR H446 1.3.1 Dictionary coding

Part 3 of 7 · H446 1.3.1 · Compression, encryption and hashing

A dictionary-coded file is only complete when the dictionary travels with the coded stream, and H446 1.3.1 expects that cost to be counted before any saving is claimed. Dictionaries are built here by first appearance, decoded exactly, and compared against run-length encoding on the same data.

Students will:

  • construct a dictionary and coded stream using first appearance to assign codes
  • state what a decoder needs in order to reconstruct the original exactly
  • decode a stream and check that spacing and punctuation survive the round trip
  • explain why dictionary coding can exploit repeats that are separated in the data
  • weigh the dictionary cost against the coded stream before claiming a reduction

Inside: 6 explanation cells, 2 multiple-choice questions, 2 fill-in-the-blanks cells and 3 written answers. 28 marks, about 40 to 50 minutes.

Series: H446 1.3.1 · Compression, encryption and hashing, part 3 of 7.

Shared by Coding PathwayVerified teacher

  • 13 cells
  • About 45 minutes
  • CC BY-SA 4.0
  • Shared 31 Aug 2026
  • Updated 3 Sept 2026

Preview

The whole resource, exactly as a class sees it. Answers and marking are held back.

Dictionary coding

Dictionary coding assigns short codes to repeated entries. A complete compressed representation contains both the dictionary and the coded stream. The repeated entries need not be adjacent.

Worked model: two parts travel together

Dictionary coding stores a dictionary plus a coded stream Original: RED BLUE RED GREEN RED BLUE dictionary1 → RED2 → BLUE3 → GREEN coded stream1 2 1 3 1 2 Both parts are required.Decode every code through the matching dictionary.

Using first appearance to assign codes, the dictionary entries are 1 → RED, 2 → BLUE, 3 → GREEN and the stream is 1 2 1 3 1 2. Looking up every code reconstructs RED BLUE RED GREEN RED BLUE exactly.

Supplied widths expose the trade-off

Suppose each original colour token occupies 8 bits, each code occupies 2 bits and each of the three dictionary entries occupies 8 bits.

  • Original: 6 × 8 = 48 bits.
  • Coded stream: 6 × 2 = 12 bits.
  • Dictionary: 3 × 8 = 24 bits.
  • Complete coded representation: 12 + 24 = 36 bits.

The saving comes from reusing short codes enough times to repay the dictionary cost. Do not count only the stream.

Multiple choice1 mark

Which data is required to decode the stream 1 2 1 3?

  • AThe number of adjacent runs
  • BA decryption private key
  • CThe matching mapping from codes to entries
  • DThe original file alongside every code
Fill in the blanks3 marks
For dictionary 1→CAT, 2→DOG, 3→OWL, the stream 1 2 1 3 reconstructs gap 1. The code 1 is reused because CAT appears gap 2 times, even though the appearances are not necessarily gap 3.
  • CAT DOG CAT OWL
  • 2
  • adjacent
  • lossy
Written answer8 marks

Using first appearance to assign codes 1, 2, 3..., construct a dictionary and coded stream for NORTH EAST NORTH WEST EAST NORTH. Then decode your stream to verify the exact original.

Show both parts. A different internally consistent code assignment is acceptable if declared.

Students type their answer here.

Multiple choice1 mark

A dictionary stream reconstructs the words in GO, GO! in the right order but loses the comma, space and exclamation mark. What follows?

  • AThe representation is lossless because only word order matters
  • BThe punctuation can always be inferred without being represented
  • CThe dictionary should be replaced by a decryption key
  • DThe representation is not yet lossless because exact separators and punctuation have not been reconstructed
Written answer4 marks

Explain why dictionary coding can exploit the repeated word NORTH in the sequence even when its appearances are separated, while RLE would not combine those appearances into one run.

Distinguish repeated entries anywhere from adjacent identical symbols.

Students type their answer here.

Apply the model independently

The remaining tasks change the context or reduce the support. Complete them without copying the worked model, then check that each explanation connects a mechanism to its consequence.

A dictionary can cost more than it saves

For SUN MOON STAR CLOUD, first-appearance coding creates four dictionary entries and stream 1 2 3 4. If each original token or dictionary entry uses 8 bits and each code uses 2 bits:

  • original = 4 × 8 = 32 bits;
  • dictionary = 4 × 8 = 32 bits;
  • stream = 4 × 2 = 8 bits;
  • total = 40 bits.

The method remains lossless, but this small mostly-unique input grows. Compression is not guaranteed.

Written answer7 marks

A log contains the six tokens OPEN OPEN OPEN CLOSE OPEN CLOSE. Compare RLE and dictionary coding for this exact sequence. State what each method can exploit, what extra data it stores and which you would test first if token widths and overheads were then supplied.

RLE sees runs; dictionary coding sees recurrence across the stream. Do not assert a bit saving without widths.

Students type their answer here.

Fill in the blanks4 marks
Dictionary coding stores a dictionary plus a coded checkpoint gap 1. A code is interpreted through its matching checkpoint gap 2. Repeated entries need not be checkpoint gap 3. The dictionary cost means compression is not checkpoint gap 4.

Review your understanding

Before submitting, check that you can explain the main distinction in your own words, apply it in an unfamiliar context and justify each consequence rather than only naming a feature.