Implement a Longest-Match Tokenizer

Problem Statement

Implement a greedy, case-sensitive longest-match tokenizer (LongestMatchTokenizer). Given a vocabulary mapping token strings to unique integer IDs, the tokenizer scans input text from left to right, always matching the longest possible vocabulary token starting at the current position.

Your implementation must support the following features:

1. Vocabulary Validation: During initialization, ensure that token strings are non-empty and mapped IDs are non-negative. Raise a ValueError if any token is empty or if any ID is negative.
2. Longest-Match Tokenization: At each position i, match the longest vocabulary token that equals a prefix of text[i:].
3. Unknown Handling (coalesce_unk):
   • When coalesce_unk=False, an unmatched character emits (unk_id, char) and advances the cursor by 1 code point.
   • When coalesce_unk=True, consecutive characters that cannot start any vocabulary match must be grouped into a single unknown token: (unk_id, unk_span).
4. Unicode Safety: Handle arbitrary Unicode code points accurately without corrupting surrogate pairs or multi-byte characters.

Interface

class LongestMatchTokenizer:
    def __init__(self, vocab: dict[str, int], unk_id: int = -1, coalesce_unk: bool = False):
        """
        Initializes the tokenizer with a vocabulary dictionary.
        Raises ValueError on invalid vocabulary entries.
        """
        pass

    def tokenize(self, text: str) -> list[tuple[int, str]]:
        """
        Tokenizes the input text into a list of (token_id, text_span) tuples.
        """
        pass

Examples

Example 1

vocab = {"app": 1, "apple": 2, "pie": 3, "let": 4}
tokenizer = LongestMatchTokenizer(vocab, unk_id=-1, coalesce_unk=False)

tokens = tokenizer.tokenize("applepie!")
# Output: [(2, "apple"), (3, "pie"), (-1, "!")]
# Explanation: At index 0, both "app" and "apple" match; "apple" is longer, so ID 2 is chosen.
# Then "pie" matches at index 5. Index 8 is '!', which is not in vocab, emitting (-1, "!").

Example 2

vocab = {"cat": 10, "cater": 11, "pillar": 12}
tokenizer = LongestMatchTokenizer(vocab, unk_id=0, coalesce_unk=True)

tokens = tokenizer.tokenize("cat xyz cater")
# Output: [(10, "cat"), (0, " xyz "), (11, "cater")]
# Explanation: "cat" matches first. The sequence " xyz " cannot form any match starting at
# indices 3, 4, 5, 6, or 7. Because coalesce_unk=True, it is merged into a single span.

Constraints

• 1 <= len(vocab) <= 100,000
• Token lengths in vocab are between 1 and 100 Unicode code points.
• 0 <= len(text) <= 500,000
• Token IDs are integers in [0, 10^9].
• Tokenization should run in O(N * L_max) time, where N is len(text) and L_max is the maximum token length in vocab.