Tokenization Theory: BPE, WordPiece, and Unigram
Module: Natural Language Processing | Difficulty: Advanced
Byte-Pair Encoding (BPE)
- Initialize vocabulary with all characters
- Count adjacent symbol pairs
- Merge most frequent pair
- Repeat until vocabulary size reached
WordPiece
Maximize likelihood:
Unigram (Kudo, 2018)
Optimize vocabulary by removing tokens with smallest marginal likelihood contribution.
SentencePiece
Language-agnostic tokenization treating text as raw bytes.
import re
from collections import Counter, defaultdict
class BPE:
def __init__(self, vocab_size=30000):
self.vocab_size = vocab_size
self.merges = []
def train(self, corpus):
vocab = Counter()
for word in Counter(corpus).elements():
vocab[' '.join(list(word)) + ' </w>'] += 1
for _ in range(self.vocab_size - len(vocab)):
pairs = self._get_pairs(vocab)
if not pairs: break
best = max(pairs, key=pairs.get)
vocab = self._merge_pair(best, vocab)
self.merges.append(best)
def _get_pairs(self, vocab):
pairs = Counter()
for word, freq in vocab.items():
symbols = word.split()
for i in range(len(symbols)-1):
pairs[(symbols[i], symbols[i+1])] += freq
return pairs
def _merge_pair(self, pair, vocab):
new_vocab = {}
pattern = re.escape(' '.join(pair))
for word in vocab:
new_word = re.sub(pattern, ''.join(pair), word)
new_vocab[new_word] = vocab[word]
return new_vocab
Research Insight: Tokenization choice affects performance more than many architectural decisions. BPE is most common because it balances between character-level and word-level representations. The optimal vocabulary size is typically 30K-50K tokens.