📘

BPE Trainer

Implement BPE training for a given number of merges.

Starting with a character-level tokenization of the input text (each character is a token, words separated by spaces are kept separate), repeatedly find the most frequent adjacent token pair and merge them.

Input:

Line 1: The text
Line 2: Number of merges to perform

Output: The final vocabulary (unique tokens after all merges), sorted alphabetically, space-separated.

Rules:

Split text into words by spaces; each word is tokenized into characters
At each step, count adjacent pairs across all words, find the most frequent
If there's a tie, pick the pair that comes first alphabetically (by concatenation)
Merge that pair in all words
Repeat for the given number of merges

Example:

Input:

low lower newest
2

Output:

e er l lo n ow s t w

Reasoning:

The input text "low lower newest" is first tokenized into characters, resulting in the tokens: l-o-w, l-o-w-e-r, n-e-w-e-s-t
The most frequent adjacent token pair is found to be "o-w", which appears in both "low" and "lower", so it is merged into a single token "ow", resulting in the tokens: l-ow, l-ow-er, n-e-w-e-s-t
After the first merge, the most frequent adjacent token pair is found to be "l-ow" is not more frequent than "n-e" or "e-w" or "w-e" but "l-ow" is not the most frequent, "e-w" is, however "lo" and "ow" and "ew" have the same frequency and "lo" comes first alphabetically (by concatenation), so "lo" is not merged, "ow" is already merged and "ew" is merged into a single token "ew" is not, "lo" is, resulting in the tokens: l-o-w, l-o-w-er, n-e-w-e-s-t, then "lo" is merged, resulting in the tokens: lo-w, lo-w-er, n-e-w-e-s-t
The final vocabulary after the two merges is: e, er, l, lo, n, ow, s, t, w, which when sorted alphabetically and space-separated gives the output: e er l lo n ow s t w

Constraints:

1 <= number of merges <= 20
Text contains lowercase letters and spaces
Words are separated by single spaces
Output sorted unique tokens after all merges

Editor

Python 3.13.1

Test Results

0/0

Run code to see test results.

📘