Turn words into token ids with a trained BPE tokenizer, as a language model's input pipeline does.
What to build
A program that tokenizes words with a list of merges and prints their tokens and ids.
Requirements
- The vocabulary is: id 0
[UNK], id 1_, ids 2 to 27 the letters a to z, then one id per merge in order (from 28), each the two symbols joined. - Lowercase each word and split it into characters plus
_. Apply the merges in the given order; each merge joins every occurrence of its pair, from left to right without overlaps. - A final symbol that is not in the vocabulary (such as a digit or
!) becomes[UNK]. For each word printword: tokens(the word as given) andids: .... At the end printtotal tokens: N.
Input
Line 1: m. Then m merges a b. Then n and n words.
Output
Two lines per word, then the total.
Constraints
m ≤ 200; n ≤ 100; no two merges produce the same symbol.
Example
Input:
6
e s
es t
est _
l o
lo w
e w
2
lowest
newer
Output:
lowest: low est_
ids: 32 30
newer: n ew e r _
ids: 15 33 6 19 1
total tokens: 7
Why it works
Applying the merges in training order rebuilds exactly the pieces the tokenizer learned, so frequent words shrink to few tokens, and every piece has a fixed id that the model's embedding table understands.
Examples
6 e s es t est _ l o lo w e w 2 lowest newer
lowest: low est_ ids: 32 30 newer: n ew e r _ ids: 15 33 6 19 1 total tokens: 7
2 u g h ug 2 hugs mug!
hugs: hug s _ ids: 29 20 1 mug!: m ug [UNK] _ ids: 14 28 0 1 total tokens: 7
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Build the vocabulary list as `["[UNK]", "_"]`, then the letters a to z, then `a + b` for each merge, and a dictionary from token to position.
Hint 2
Apply each merge to the whole symbol list before moving on to the next merge.
Solution
Show one correct solution (try it yourself first)
merges = [tuple(input().split()) for _ in range(int(input()))]
vocab = ["[UNK]", "_"] + [chr(c) for c in range(ord("a"), ord("z") + 1)] + [a + b for a, b in merges]
ids = {tok: i for i, tok in enumerate(vocab)}
total = 0
for _ in range(int(input())):
word = input().strip()
symbols = list(word.lower()) + ["_"]
for pair in merges:
out, i = [], 0
while i < len(symbols):
if i + 1 < len(symbols) and (symbols[i], symbols[i + 1]) == pair:
out.append(symbols[i] + symbols[i + 1])
i += 2
else:
out.append(symbols[i])
i += 1
symbols = out
tokens = [s if s in ids else "[UNK]" for s in symbols]
total += len(tokens)
print(f"{word}: {' '.join(tokens)}")
print("ids:", " ".join(str(ids[t]) for t in tokens))
print("total tokens:", total)