Question
Given an input string and a vocabulary, tokenize from left to right using longest-prefix matching. ```python def tokenize(text: str, vocab: dict[str, int], collapse_unk: bool = False) -> list[int]: ... ``` At each position, emit the integer ID of the longest vocabulary entry matching the remaining text. If nothing matches, emit `vocab["UNK"]` and advance by one character. With `collapse_unk=True`, collapse consecutive unknown IDs into a single ID; otherwise emit one for each unmatched character. The literal vocabulary entry `UNK` is reserved and must not match input text as an ordinary token. Assume every token has a distinct integer ID and the vocabulary contains `UNK`. ## Requirements and edge cases - Return an empty list for empty input. - Resolve overlapping prefixes by length, not vocabulary iteration order. - Support Unicode strings using the language's ordinary string indexing semantics. - Reject an empty-string vocabulary token with `ValueError`. - Bound the scan by the longest usable token. ## Implementation approach 1. Implement the straightforward bounded scan. 2. Add optional unknown-run collapse and verify both flag values. ## Design discussion (not graded) - Replace repeated prefix checks with a trie and analyze complexity. - Stream text in chunks without breaking tokens at chunk boundaries. - Discuss normalization, byte-level tokenization, and memory layout for a production vocabulary.