/ The Arena

Problem Overview

Large Language Models process text through subword integer sequences rather than raw strings. Modern serving engines (such as Tiktoken in GPT-4 and the Llama 3 tokenizer) rely on Byte-Pair Encoding (BPE) with byte-level fallback to achieve optimal context compression without Out-Of-Vocabulary (OOV) errors.

In this landmark capstone, you will implement a complete, production-grade Byte-Pair Encoding (BPE) Tokenizer Engine with byte-level fallbacks, iterative merge training, priority-based subword encoding, UTF-8 string decoding, and atomic special token isolation.

---

Architectural Requirements

1. Base Vocabulary: Initialize with all 256 single-byte values ($\mathrm{0..255}$). New merges start at ID 256.
2. Merge Training (train(corpus, targetVocabSize)): Iteratively find the most frequent adjacent pair, assign a new integer ID, and replace all occurrences. Terminate early if max frequency $<2$.
3. Subword Encoding (encode(text)): Isolate registered special tokens atomically (e.g. <|endoftext|>). For regular text, merge pairs according to learned merge rank priority (lowest merge ID first).
4. Decoding (decode(tokens)): Map token IDs back to bytes / special strings and decode losslessly into a UTF-8 string.