Byte Pair Encoding

Learn the merge rules that every modern tokenizer is built from.

You are given words, a dict mapping a word to how often it appears. Start with each word split into single characters. Then repeat num_merges times:

1. Count every adjacent symbol pair across all words, weighting each occurrence by that word's frequency.
2. Take the most frequent pair. Break ties by choosing the lexicographically smallest pair.
3. Merge that pair into a single symbol everywhere it occurs, and record it.

Stop early if no pair occurs more than once, or if no pairs remain.

Return the list of merges in order, each a tuple (left, right).

Two things to be careful about:

• Count within words, never across them. The pair spanning the end of one word and the start of the next does not exist.
• Merge left to right without overlapping. In a a a, merging (a, a) produces aa a, not aa plus a dangling symbol. Scan with an index and skip two positions when you merge.

This is why a subword vocabulary has no unknown tokens: common words end up as single symbols, rare ones fall back to pieces, and anything at all can be spelled out from characters.

Function signature

def train_bpe(words, num_merges):

Example

Input

words = {"low": 5, "lower": 2}
train_bpe(words, 2)

Output

[('l', 'o'), ('lo', 'w')]

Reasoning

Weighted pair counts are (l, o): 7, (o, w): 7, (w, e): 2 and (e, r): 2. (l, o) and (o, w) tie, and (l, o) is smaller, so it merges first. After that, (lo, w) occurs 7 times and merges next.

Constraints and notes

• Break ties by the lexicographically smallest pair.
• Stop early when no pair occurs more than once.
• Count pairs within words, never across them.