Byte-Pair Encoding Tokenizer from Scratch
Problem statement
Implement a subword tokenizer with byte-pair encoding (BPE): learn merges from a corpus, build the vocabulary, encode a new text into token ids, and decode the ids back into text.
Write bpe_tokenize(corpus, num_merges, text) that returns [ids, decoded].
Training.
- The words are
corpus.split(). Each distinct word is a list of its characters followed by the end-of-word symbol</w>, and it is weighted by how often it occurs. - The vocabulary starts as
["<unk>", "</w>"]followed by the corpus's distinct characters in sorted order. A token's id is its position in this list. - Repeat up to
num_mergestimes: count every adjacent pair of symbols in every word (each adjacent position counts, weighted by the word's frequency); pick the pair with the highest count, breaking ties by the smallest(left, right)tuple under Python string ordering; stop early if no pair occurs at least twice. Record the merge, replace every occurrence of the pair in every word (scanning left to right, without overlap), and append the merged string to the vocabulary unless it is already there.
Encoding. For each word of text.split(), replace characters that are not in the base vocabulary with <unk>, append </w>, apply the learned merges in the order they were learned, and emit the ids of the resulting symbols. Concatenate the ids of all words.
Decoding. Concatenate the token strings of ids, replace each </w> with a space and strip the result.
def bpe_tokenize(corpus: str, num_merges: int, text: str) -> list:
# returns [ids: list[int], decoded: str]
...
Constraints
- Corpus of up to 60 words;
textof up to 8 words; words of up to 8 characters; $0 \le$num_merges$\le 100$. - The output is compared exactly.
Examples
Example 1: corpus = "low low low lower lower newest newest newest widest", num_merges = 4, text = "lowest newer" returns [[13, 15, 1, 6, 3, 11, 3, 8, 1], "lowest newer"]. The base vocabulary is <unk>, </w>, d, e, i, l, n, o, r, s, t, w (ids 0-11). The first merge is (l, o): it ties with (o, w) and (w, e) at a count of 5 and is the smallest tuple. Then (lo, w), (e, s) and (es, t) give ids 12-15 for lo, low, es, est. lowest encodes as low, est, </w>; newer contains no learned pair and stays as single characters.
Example 2: the same corpus with num_merges = 0 and text = "low" returns [[5, 7, 11, 1], "low"].
Example 3: corpus = "", num_merges = 10, text = "abc" returns [[0, 0, 0, 1], "<unk><unk><unk>"] (nothing is known except </w>).
Show hint
How can you store the corpus so that each distinct word is processed once but still contributes according to how often it appears?
Relevant roles: LLM Engineer, ML Engineer, Deep Learning Engineer and Research Scientist.
Related free problems
- Multi-Head AttentionMedium
- Masked Self-AttentionMedium