Debug Tokenization and Detokenization

Debug Tokenization and Detokenization

You are tasked with fixing and hardening an in-memory subword tokenizer used in an inference pipeline. The existing prototype has several critical bugs:

1. Matching order dependency: It iterates through the vocabulary in insertion order rather than prioritizing the longest matching prefix (greedy maximal matching).
2. Silent drops: When encountering characters or substrings not in the vocabulary, it silently skips them instead of signaling failure.
3. Corrupted vocabularies: It accepts empty tokens ("") and maps multiple distinct tokens to the identical token ID, making detokenization ambiguous.
4. Round-trip violation: Valid token sequences occasionally produce strings that re-tokenize into different ID sequences.

Implement the Tokenizer class to resolve these issues while keeping the public interface purely ID-based.

Class Interface

class Tokenizer:
    def __init__(self, vocab: dict[str, int]):
        """
        Initializes the tokenizer with a dictionary mapping string tokens to integer IDs.
        Raises ValueError if:
          - Any token is an empty string.
          - Any token ID is mapped to multiple distinct token strings.
          - Any token ID is negative.
        """
        pass

    def tokenize(self, text: str) -> list[int]:
        """
        Tokenizes input text into a list of token IDs using greedy longest-match prefixing.
        At each step, selects the longest token in the vocabulary that matches the prefix
        of the remaining text. If multiple tokens match the same maximum length, breaks ties
        lexicographically by token string.
        
        Raises ValueError if any portion of text cannot be matched to a token.
        """
        pass

    def detokenize(self, token_ids: list[int]) -> str:
        """
        Converts a list of token IDs back into the concatenated string.
        Raises ValueError if any token ID is not recognized in the vocabulary.
        """
        pass

Examples

vocab = {"a": 1, "app": 2, "apple": 3, "ple": 4, "b": 5}
tok = Tokenizer(vocab)

# Greedy longest match chooses 'apple' (ID 3) over 'app' + 'le'
tok.tokenize("apple") # Output: [3]

# 'appl' matches 'app' (2), then 'l' fails -> raises ValueError
tok.tokenize("appl") # Raises ValueError

# Round trip guarantee
ids = tok.tokenize("appleb") # Output: [3, 5]
tok.detokenize(ids)          # Output: "appleb"

Constraints

• 1 <= len(vocab) <= 50,000
• 0 <= len(text) <= 100,000
• Token IDs are non-negative integers (0 <= id <= 10^9).
• Tokens contain arbitrary Unicode characters.