Greedy longest-match

A deterministic scan that turns raw text into a sequence of vocabulary tokens.

Greedy longest-match (sometimes called maximal munch) is the tokenisation algorithm used here. It works left-to-right: at each position it tries to match the longest string that exists in the vocabulary, consumes those characters, and advances past them. No backtracking. No ambiguity. One pass through the input, one output token per match. For a character-level vocabulary — say 26 letters plus space — every single character is in the vocabulary, so there is always a match of length 1 and the algorithm never fails.

The same principle governs byte-pair encoding (BPE) tokenisers in production models, but the vocabulary is far richer: "quick" might be a single entry, so the scan matches it in one step rather than five. If the input contains a rare word no vocabulary entry spans, the algorithm falls back to shorter entries until it finds one — ultimately to individual bytes in byte-level BPE. Longest-match is greedy, not optimal: a different segmentation might produce a shorter sequence, but greedy is fast, deterministic, and good enough in practice when the vocabulary is trained jointly with the model.

The chips below show "the quick brown fox" after greedy longest-match. Each chip consumed as many characters as the vocabulary allowed from that position. "brown" splits into "bro" and "wn" because no single entry spans all five characters; space tokens always match exactly one character since no multi-character vocabulary entry starts with a space in this example.

Each chip is the longest vocabulary match at that position. 'brown' requires two chips because no single entry covers it; greedy scans left-to-right and never revisits a consumed character.

Related: Vocabulary · Character vs sub-word · Token ids