Greedy Longest-Match Tokenizer - Transformer Architecture

Implement Greedy Longest-Match Tokenizer in Python with NumPy. medium exercise with examples, hints, and instant feedback. No setup or signup required.

Greedy Longest-Match Tokenizer

What you'll build

A tokenizer that turns text into token ids with a fixed vocabulary using greedy longest match ("maximal munch"), plus a WordPiece mode that works the way BERT's tokenizer does.

Background

Once a vocabulary exists (for example, learned by BPE Tokenization), you still need an encoding rule. The simplest rule is to take, at each position, the longest vocabulary entry that matches, emit its id and continue after it. WordPiece (BERT) applies this inside each word, marking pieces that continue a word with ##. It's fast, but it's not globally optimal: with tokens {'ab', 'abc', 'cd', 'd'}, "abcd" becomes abc + d, even though ab + cd also covers it.

Algorithm, default mode (`wordpiece=False`)

Scan text left to right; spaces are ordinary characters and can be tokens.

At position i, find the longest vocabulary token that is a prefix of text[i:].
If one exists, emit its id and move past it.
Otherwise emit vocab[unk_token] for the single character text[i] and move on by one character. A run of unknown characters gives one unknown id per character.

Algorithm, WordPiece mode (`wordpiece=True`)

Split text on whitespace (text.split()); whitespace never produces tokens.
Tokenize each word with greedy longest match. The first piece is looked up as-is; every later piece is looked up with a ## prefix ("playing" becomes play, ##ing).
If at some point no piece matches, the whole word becomes a single unknown id (BERT's behaviour), and the pieces already matched in that word are dropped.

Inputs

text: str (may be empty)
vocab: dict token string -> int id; always contains unk_token
unk_token: str, default '[UNK]'
wordpiece: bool, default False

Expected Return Format

A list of token ids (Python ints), in order. The empty string gives [].

Edge cases and conventions

Default mode never drops characters: unknown characters become one [UNK] each.
WordPiece mode drops whitespace and collapses an untokenizable word into a single [UNK].

Constraints

Plain Python. Bound the inner search by the longest token length, so each position costs O(max_token_len) lookups.

Follow-up

Which tokenization of "abcd" would a dynamic program that minimises the number of tokens choose? What does that cost?
Why do LLM tokenizers work on bytes rather than characters (no [UNK] at all)?

Examples

Input: tokenize("abcab", {'[UNK]': 0, 'a': 1, 'b': 2, 'ab': 3, 'abc': 4, 'c': 5, 'bc': 6, ' ': 7, 'the': 8, 'th': 9, 't': 10, 'h': 11, 'e': 12})
Output: [4, 3]

"abc" is the longest match at position 0, then "ab".

Input: tokenize("abxc", same vocab)
Output: [3, 0, 5]

No token starts with "x", so it becomes [UNK] (id 0).

Input: tokenize("unaffable plays", {'[UNK]': 0, 'un': 1, '##aff': 2, '##able': 3, 'play': 4, '##ing': 5, '##s': 6, 'u': 7, '##n': 8, 'a': 9, '##a': 10}, wordpiece=True)
Output: [1, 2, 3, 4, 6]

un, ##aff, ##able, then play, ##s.

Practice in Python

def tokenize(text, vocab, unk_token='[UNK]', wordpiece=False):
    """
    Greedy longest-match (maximal munch) tokenization.

    Args:
        text: Input string
        vocab: Dict mapping token string -> id (contains unk_token)
        unk_token: Token used for text that no vocabulary entry matches
        wordpiece: If True, split on whitespace and look up non-initial
                   pieces of a word with a '##' prefix

    Returns:
        List of token ids (one unk id per unknown character in default mode,
        one unk id per untokenizable word in WordPiece mode)
    """
    # Your code here
    pass

The interactive editor loads with Python and NumPy. Run your implementation against 10 tests, or use the progressive hints.

More exercises in this section →

Greedy Longest-Match Tokenizer - Transformer Architecture