Tokenizer data structures: byte pair encoding from scratch
A tokenizer turns text into a list of integer IDs the model can look up, and it's built from classic structures: a hash map from token to ID, an ordered table of merge rules, and often a trie for longest-match lookups. Byte pair encoding (BPE) learns its vocabulary by repeatedly merging the most frequent pair of adjacent symbols, so common words become one token and rare words split into pieces. Knowing this explains why token counts differ across languages and models, and why "strawberry" can be hard for a model to spell.
What a tokenizer stores
| Structure | Holds | Used for |
|---|---|---|
| Vocabulary hash map | Token string to ID | Encoding |
| Reverse array | ID to token string | Decoding |
| Merge table | Ordered pairs to merge, with rank | Applying BPE to new text |
| Trie (some tokenizers) | Prefixes of all tokens | Longest-match lookup |
| Special tokens | `< | endoftext |
Vocabularies range from about 32,000 tokens to over 200,000, depending on the model. A bigger vocabulary means fewer tokens per text and a bigger embedding table.
Byte pair encoding
Start with every word split into characters (or bytes). Count every adjacent pair across the corpus, merge the most frequent pair into a new symbol, and repeat until you reach the vocabulary size you want. The order of merges is the model's tokenizer: to encode new text, you apply the same merges in the same order.
from collections import Counter
def pair_counts(words: dict[tuple[str, ...], int]) -> Counter:
counts = Counter()
for symbols, freq in words.items():
for pair in zip(symbols, symbols[1:]):
counts[pair] += freq
return counts
def merge(words: dict[tuple[str, ...], int], pair: tuple[str, str]) -> dict[tuple[str, ...], int]:
out = {}
for symbols, freq in words.items():
merged, i = [], 0
while i < len(symbols):
if i < len(symbols) - 1 and (symbols[i], symbols[i + 1]) == pair:
merged.append(symbols[i] + symbols[i + 1])
i += 2
else:
merged.append(symbols[i])
i += 1
out[tuple(merged)] = freq
return out
corpus = "low low low lower lower newest newest newest widest widest".split()
words = dict(Counter(tuple(w) + ("</w>",) for w in corpus))
merges = []
for _ in range(8):
counts = pair_counts(words)
best = max(counts, key=counts.get)
merges.append(best)
words = merge(words, best)
print("merges:", merges)
print("tokens:", list(words))
After a few merges, "low" and "est" become single tokens, because they repeat.
Why this matters in practice
- Cost and limits are counted in tokens, not words, and the same text can be a different number of tokens in two models.
- Languages that appear less in the training data split into more tokens, so the same message can cost more and fill the context window faster.
- Models see tokens, not letters, which is part of why character-level tasks (counting letters, reversing strings) are unreliable.
- Numbers split in odd ways ("12345" can be one token or three), which affects arithmetic.
Count tokens with the model's own tokenizer, not by estimating from words. See tokens and tokenization.
Tries and prefixes
A trie stores strings by shared prefixes: "low", "lower" and "lowest" share the path l, o, w. Some tokenizers use one for longest-match lookup. The same idea appears again in the KV cache, where requests that share a prompt prefix can share cached computation. See KV cache.
Check your understanding
Run the trainer with 4 merges instead of 8 and explain why the token list changes.
From the floor
In the AI data structures lecture, I put tokenization at the point where discrete becomes continuous: the tokenizer maps text to integer IDs with ordinary hash maps, and only after that does each ID get a vector of decimal numbers from the embedding table.