Milestone 4 of 10

Implement and trace the matching decoder

Resolve existing and special next codes, mirror bounded growth, retain output ranges, and report the first invalid code position without false recovery.

The decoder must mirror the encoder's dictionary state, including one special code that refers to the phrase it is about to add.

Goal

Implement the matching decoder, resolve existing and special next codes, retain exact output ranges and dictionary state, and report the first invalid code.

Inputs

Use two-byte code values and the same 256-entry literal dictionary. For an empty code stream, return empty bytes and final size 256. For a non-empty stream, the first code must select an initial entry. For every later code, either select an existing code or, while growth remains, resolve the one code equal to the next unused code as:

previous_phrase + (previous_phrase[0],)

Any other code is invalid. After selecting a phrase, append it to output and, when space remains, add previous_phrase + (current_phrase[0],) at the next code.

Deliverables

Implement decoding in src/dictionary.py. Produce output/decoder_trace.jsonl with code position, input code, resolution kind (existing or next_code), output phrase, added phrase and code, output byte range, and dictionary size. Invalid streams return first invalid code position and dictionary size reached before failure, without a successful recovered document.

Checks

Check empty, normal existing-code, special next-code, full-dictionary, repeated, and malformed streams. Check invalid first code, invalid later code, negative before packing, above-two-byte values, dictionary-limit behavior, output ranges, consecutive additions, and final state. Verify the decoder never reads a code outside 0..65535 and does not produce success after failure.

Check encoder and decoder state resets per document and source bytes are not mutated.

Workspace

Keep decoder state, special-code resolution, failure records, and traces in src/dictionary.py. Read code streams without mutation. Do not compare full corpus round trips or write payloads yet.

Hints

HintThe special code is precise

The next unused code is valid only when it equals previous_phrase + (previous_phrase[0],) and growth remains. Other unknown codes are invalid.

HintAdd after selecting

Use the previous phrase and selected current phrase to add the next dictionary entry after outputting the current phrase.

HintRecord failure state

Capture the code position and dictionary size before raising or returning. A generic invalid result hides where the stream stopped.

Review

Find a short code stream that triggers the special next-code case. What phrase does it output, and which dictionary entry is added afterward?

How to check your work

Checks compare decoder traces, special-code resolution, invalid positions, output ranges, and final sizes with the fixtures. The supplied fixture mirrors bounded encoder state and distinguishes existing from next-code resolution.