Byte Pair Encoding (BPE): Building a Vocabulary from the Corpus

Byte Pair Encoding (BPE), originally a 1994 data-compression algorithm repurposed for NLP by Sennrich et al. in 2016, is the most widely used subword tokenization algorithm — it's what powers the GPT family of tokenizers, among many others. Its core idea is refreshingly simple: instead of a human deciding what counts as a 'meaningful' subword, let the algorithm DISCOVER useful subwords automatically, purely from how often character sequences co-occur in a large corpus of text.

The training algorithm works like this. Start by splitting every word in your training corpus into individual characters — this is your initial vocabulary (just the alphabet, essentially). Then repeat the following step a fixed number of times (this count is a hyperparameter you choose, and it directly determines your final vocabulary size): count every PAIR of adjacent tokens across the entire corpus, find the single most frequently occurring pair, and MERGE that pair into one new token, adding it to the vocabulary. For example, if 'e' and 's' appear next to each other extremely often (as in 'trees', 'cats', 'runs'), 'es' becomes a new single token. Next round, maybe 't' + 'h' merges into 'th'. Keep going, and eventually whole common words ('the', 'and') end up merged into single tokens too, because they appeared as adjacent-character-pairs frequently enough at every step along the way.

The number of merge operations you run IS your vocabulary size knob: more merges means more (and often longer) tokens in the vocabulary, capturing more whole words as single tokens; fewer merges leaves more text broken into short pieces. Real tokenizers typically run tens of thousands of merges (GPT-2's tokenizer has roughly 50,000 tokens, for instance).

Once trained, APPLYING the tokenizer to new text uses the same learned merge rules, in the same order they were learned: start with characters, and repeatedly apply whichever learned merge rule matches, in priority order, until no more merges apply. This is why a rare or made-up word still tokenizes sensibly — it gets broken down into whatever combination of learned subword pieces best covers it, even if the WHOLE word was never seen during training, directly solving the vocabulary problem from the previous subtopic.

# A minimal from-scratch BPE trainer -- the same core algorithm real
# tokenizers (like GPT-2's) use, simplified to be readable end to end.
from collections import Counter

def get_pair_counts(word_freqs: dict) -> Counter:
    """Count every adjacent symbol pair across the corpus."""
    pairs = Counter()
    for word, freq in word_freqs.items():
        symbols = word.split()
        for i in range(len(symbols) - 1):
            pairs[(symbols[i], symbols[i + 1])] += freq
    return pairs

def merge_pair(pair, word_freqs: dict) -> dict:
    """Replace every occurrence of the given adjacent pair with one merged token."""
    merged = "".join(pair)
    new_word_freqs = {}
    for word, freq in word_freqs.items():
        new_word = word.replace(" ".join(pair), merged)
        new_word_freqs[new_word] = freq
    return new_word_freqs

# Corpus: word -> frequency, pre-split into characters (with </w> = end-of-word)
word_freqs = {
    "l o w </w>": 5, "l o w e r </w>": 2,
    "n e w e s t </w>": 6, "w i d e s t </w>": 3,
}

num_merges = 6
for i in range(num_merges):
    pairs = get_pair_counts(word_freqs)
    if not pairs:
        break
    best_pair = max(pairs, key=pairs.get)   # the MOST FREQUENT adjacent pair
    word_freqs = merge_pair(best_pair, word_freqs)
    print(f"merge {i+1}: {best_pair} (count={pairs[best_pair]}) -> {''.join(best_pair)!r}")

print("\nfinal tokenization:")
for word in word_freqs:
    print(" ", word)