Project 15

Build a Lossless Dictionary Text Codec

Encode strict UTF-8 source bytes with one bounded phrase dictionary, store fixed-width codes in a versioned file, and prove exact recovery.

  • 10 milestones
  • Optional
  • Browser workspace

Project question: Can you encode strict UTF-8 source bytes with one bounded phrase dictionary, store fixed-width codes in a versioned binary file, and prove exact byte and text recovery?

What makes this a project

A lossless codec is a conversation between bytes, dictionary state, codes, and the decoder. In this project you will verify safe source files, distinguish text from its UTF-8 bytes, grow one bounded dictionary per document, pack two-byte codes, write an exact payload and outer container, and recover every source byte and digest. You will also measure headers honestly and inspect a small dictionary-limit audit.

This is one inspectable lossless text codec. It does not claim to implement a standard LZW file format or to shrink every input. A result is trustworthy only when its source identity, traces, recovered bytes, digest, and decoded text agree.

You will produce:

  • checked source-file identities, strict UTF-8 boundaries, and codec settings;
  • byte-symbol dictionary records, encoder and decoder traces, and special-code evidence;
  • fixed-width code streams, exact DTC1 payloads, and versioned outer files;
  • malformed-stream results, byte/digest/text round trips, and final-size checks;
  • honest per-document and corpus size accounting and a dictionary-limit audit;
  • saved figures from exact plot data, read-back checks, and a separate replay; and
  • an evidence-limited lossless-codec card.

What you should know first

The project follows the Python path through Chapter 13. You should be able to distinguish text from bytes, read and write binary files, work with integer byte values, maintain mappings whose entries grow over time, preserve invariants across encoder and decoder, pack fixed-width integers, validate bounded records, compare exact artifacts, and report measured evidence. TXT-13 and FILE-15 are useful but optional. This project restates its complete algorithm and container rules.

Supplied inputs

Use a versioned manifest of small repository-owned strict UTF-8 documents with unique IDs, safe relative paths, byte counts, SHA-256 digests, and text identity. Also use empty, ASCII, repeated, non-repeated, non-ASCII, underscore, newline, and mixed-punctuation fixtures; plans/codec_config.json; hand-worked source bytes, phrase matches, dictionary additions, codes, packed fields, decoder steps, recovered bytes, and size records; and malformed code and byte streams.

The primary and audit dictionary limits are unique non-boolean integers from 256 through 65536, with the primary limit appearing once in the ordered audit list. Code width is fixed at two bytes and is not a reader choice.

The project workspace

project/
  README.md
  data/                              # supplied, read only
  plans/codec_config.json             # supplied starting config
  src/config.py                       # reader implementation
  src/sources.py                      # reader implementation
  src/dictionary.py                   # reader implementation
  src/codes.py                        # reader implementation
  src/payload.py                      # reader implementation
  src/container.py                    # reader implementation
  src/measure.py                      # reader implementation
  src/report.py                       # reader implementation
  src/main.py                         # reader implementation
  output/                             # generated artifacts
  tests/public_cases.py               # supplied, read only

Keep one continuous workspace through every milestone. Source loading, encoder state, decoder state, code packing, payload parsing, container validation, recovery comparison, size accounting, and limit auditing should remain independently inspectable.

Project milestones

Work through these in order. Each milestone produces evidence used by the next one, while project completion remains separate from lesson progress.

  1. 1Verify source files, UTF-8, identities, configuration, and bounds

    Check safe manifest paths, exact bytes and digests, strict UTF-8, format identities, dictionary limits, fixed width, and positive parser bounds.

  2. 2Map text bytes and hand-trace the initial dictionary

    Separate characters from UTF-8 byte values and establish the exact 256-entry literal dictionary for empty, ASCII, repeated, and non-ASCII inputs.

  3. 3Implement and trace the bounded encoder

    Emit the longest known byte phrase, grow consecutively below the limit, stop exactly at the bound, and retain complete source-range evidence.

  4. 4Implement 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.

  5. 5Prove encoder and decoder agreement

    Check normal, empty, repeated, special-code, full-dictionary, and malformed streams while comparing bytes, codes, traces, and final dictionary sizes.

  6. 6Pack and parse the fixed-width codec payload

    Write exact DTC1 fields and two-byte big-endian codes, validate configured bounds, and reject malformed lengths, magic, fields, and code bytes.

  7. 7Wrap and validate versioned codec files

    Apply the LMP version and payload-length boundary independently to every document and reject each outer-container failure before payload decoding.

  8. 8Round-trip the complete corpus

    Recover every file independently and prove exact length, bytes, digest, strict text, code order, and encoder-decoder dictionary agreement.

  9. 9Measure, audit limits, save, reload, and replay

    Separate body, payload, and container sizes; aggregate corpus totals; compare bounded dictionary limits; save exact artifacts and figures; and reproduce them separately.

  10. 10Write and audit the lossless-codec card

    State the byte and dictionary rules, special code, fixed formats, malformed behavior, recovery evidence, size denominators, audit results, replay, and claim limits.

Required evidence

Save versioned codec configuration and source manifest identity; source_inventory.csv; primary encoder_trace.jsonl, decoder_trace.jsonl, and dictionary_summary.csv; document_codes.jsonl and exact per-document .lmpc files with digests; payload/container read-back and malformed-stream results; round_trip_results.csv; size_accounting.csv, corpus totals, dictionary_limit_audit.csv, and figures with exact plot_data.json; dictionary_codec_manifest.json; read-back checks; a separate replay agreement or first-mismatch record; and project-root report.md.

Limits

This project does not claim standard LZW compatibility. It does not teach character-symbol dictionaries, arbitrary non-text binary-file products, variable-width or bit-packed codes, end markers, dictionary reset or eviction heuristics, cross-document dictionaries, run-length, Huffman, arithmetic, LZMW, or LZAP coding, lossy compression, archive directories, streaming, concurrency, encryption, general corruption detection or correction, production formats, or performance benchmarking. It does not claim every input shrinks or one dictionary limit is universally best.

Review

The final review asks whether source identity and strict UTF-8 checks hold, bytes rather than characters drive the codec, dictionary state resets per document, special codes and bounds are explicit, payload and container lengths are exact, recovery includes bytes/digest/text, empty ratios remain null, headers remain visible, audit limits stay separate, replay is independent, and the card avoids standard-format, universal-compression, optimality, corruption, and speed claims.