Learn · Module 16 · ML from scratch · Lesson 4 of 5
A BPE tokenizer
Turn the tokenization lesson into code: learn merges from word counts, then apply them to new words.
4 minute read
- Learning: count weighted neighbouring pairs, merge the most common, repeat.
- Tokenizing: apply merges in learned order; unseen words split into known pieces.
- Real tokenizers work on bytes so every text is covered.
The idea
Learning: start with every word split into characters. Count every neighbouring pair, weighted by how often the word appears. Merge the most common pair everywhere. Repeat. Tokenizing: apply the learned merges to a new word, in the order they were learned.
The code
from collections import Counter
def learn_bpe(word_counts, merges):
words = {w: list(w) for w in word_counts}
rules = []
for _ in range(merges):
pairs = Counter()
for w, n in word_counts.items():
s = words[w]
for a, b in zip(s, s[1:]):
pairs[(a, b)] += n
if not pairs:
break
best = max(pairs, key=pairs.get)
rules.append(best)
for w in words:
words[w] = merge(words[w], best)
return rules
def merge(symbols, pair):
out, i = [], 0
while i < len(symbols):
if i + 1 < len(symbols) and (symbols[i], symbols[i + 1]) == pair:
out.append(symbols[i] + symbols[i + 1])
i += 2
else:
out.append(symbols[i])
i += 1
return out
def tokenize(word, rules):
symbols = list(word)
for pair in rules: # apply merges in the order they were learned
symbols = merge(symbols, pair)
return symbols
rules = learn_bpe({"chai": 6, "chat": 4, "hat": 3, "that": 8}, merges=3)
print(rules)
# [('h', 'a'), ('ha', 't'), ('t', 'hat')]
print(tokenize("chat", rules), tokenize("chai", rules), tokenize("hatch", rules))
# ['c', 'hat'] ['c', 'ha', 'i'] ['hat', 'c', 'h']- 1Same merges as the lesson
h + a, then ha + t, then t + hat.
- 2A word it never saw
'hatch' still tokenizes, into known pieces: hat · c · h. Nothing is ever unknown, because single characters are always in the vocabulary.
- 3merge skips ahead by 2
After joining a pair, i += 2, so a symbol is never used in two merges at once.
Why must tokenize apply the merges in the order they were learned?
Take it further
Real tokenizers work on bytes rather than characters so any text, including emoji and every language, is covered. Tokenizing by looping over every rule is slow; real ones rank pairs and merge the best-ranked pair repeatedly. Then think about how vocabulary size trades sequence length against embedding table size.
Common mistakes
- Counting pairs without weighting by how often each word appears.
- Merging overlapping pairs twice, such as in 'aaa'; skip ahead after a merge.
- Applying merges to new words in a different order from the one learned.
Answer in your own words, out loud or on paper, before you open the model answer.
Implement byte-pair encoding training and tokenization.
There are two parts. Training: take a word-frequency count, and represent each word as a list of characters. Repeat for the number of merges you want: count every adjacent pair of symbols across all words, weighted by each word's frequency; pick the most frequent pair; record it as a merge rule; and replace that pair with the joined symbol in every word. Merging walks through the symbols, and when it finds the pair it appends the joined symbol and skips ahead two, so overlapping pairs aren't merged twice. Tokenizing a new word: split it into characters and apply each merge rule in the order learned. I'd mention that real tokenizers work on bytes so any text is covered.
- Why do production tokenizers work on bytes?
- How does vocabulary size affect a model?
Go further
- VideoLet's build the GPT TokenizerAndrej Karpathy
- Docsminbpe: minimal byte-pair encoding codeAndrej Karpathy
- PaperNeural Machine Translation of Rare Words with Subword UnitsSennrich et al., 2015
This lesson is part of Pro
The first two lessons of every module are free. Pro opens every lesson and every project.
See Pro plansFrom ₹119 a month. No auto-renewal.