Growing a Tokenizer

Subword tokenizers keep common words whole and split rare ones into pieces. But where do the pieces come from? Nobody writes them by hand: they are learned from counts, by repeatedly gluing together the two neighbouring symbols that sit side by side most often in the training text. The method is called byte-pair encoding (BPE).

Task: write learn_and_split(word_counts, num_merges, new_word).

word_counts maps each training word to the number of times it appeared, for example {"rain": 6, "train": 3}.

Learning the merges

1. Write every training word as a list of single characters: "rain" becomes r a i n.
2. Count every pair of neighbouring symbols across all the words. Each occurrence counts with its word's frequency, so in the example above the pair a i scores $6 + 3 = 9$. A pair that appears twice inside one word counts twice.
3. Pick the pair with the highest total. If several pairs tie, pick the one that comes first alphabetically: compare the left symbols, and only if those are equal, the right symbols — exactly how Python compares tuples such as ("a", "i") < ("r", "a").
4. Merge that pair in every word. Scan left to right; wherever the two symbols stand next to each other, replace them with one symbol made by joining them, then carry on scanning after the new symbol. So z z z merged on (z, z) becomes zz z.
5. Record the pair, then go back to step 2 and count again.

Stop after num_merges merges — or sooner, if every word has already become a single symbol and there is no pair left to count.

Splitting a new word

Write new_word as single characters, then go through the learned merges in the order they were learned, applying each one to the word exactly as in step 4. A character the training words never contained just stays a piece of its own — nothing is ever unknown.

Return a tuple (merges, pieces): the learned pairs in order, each as a 2-tuple of strings, and the list of pieces new_word was split into.