Train a byte-pair-encoding tokenizer from a list of word frequencies.
What to build
A program that learns k BPE merges and prints how each word is split at the end.
Requirements
- Start each word as its characters plus
_. In each round, count neighbouring pairs weighted by word counts, choose the most frequent pair (ties: alphabetically first pair,_before letters), print it and merge it in every word, joining each occurrence from left to right without overlaps. - Print each merge as
i: a + b -> ab (count). Stop early if no word has two symbols left. - Finally print every word, in input order, as
word: s1 s2 ....
Input
Line 1: k. Line 2: n. Then n lines word count.
Output
The merge lines, then n lines.
Constraints
k ≤ 100; n ≤ 500.
Example
Input:
6
4
low 5
lower 2
newest 6
widest 3
Output:
1: e + s -> es (9)
2: es + t -> est (9)
3: est + _ -> est_ (9)
4: l + o -> lo (7)
5: lo + w -> low (7)
6: e + w -> ew (6)
low: low _
lower: low e r _
newest: n ew est_
widest: w i d est_
Why it works
Each merge turns the currently most frequent pair into one symbol, so frequent letter sequences grow into longer tokens step by step while rare ones stay split.
Examples
6 4 low 5 lower 2 newest 6 widest 3
1: e + s -> es (9) 2: es + t -> est (9) 3: est + _ -> est_ (9) 4: l + o -> lo (7) 5: lo + w -> low (7) 6: e + w -> ew (6) low: low _ lower: low e r _ newest: n ew est_ widest: w i d est_
2 1 aaaa 1
1: a + a -> aa (3) 2: aa + _ -> aa_ (1) aaaa: aa aa_
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Keep each word as a list of symbols; after choosing the best pair, rebuild each list from left to right, joining the pair wherever it occurs.
Hint 2
`min(counts, key=lambda p: (-counts[p], p))` picks the most frequent pair, alphabetically first on a tie.
Solution
Show one correct solution (try it yourself first)
k = int(input())
corpus = []
for _ in range(int(input())):
word, c = input().split()
corpus.append([list(word) + ["_"], int(c), word])
for step in range(1, k + 1):
counts = {}
for symbols, c, _ in corpus:
for pair in zip(symbols, symbols[1:]):
counts[pair] = counts.get(pair, 0) + c
if not counts:
break
best = min(counts, key=lambda p: (-counts[p], p))
print(f"{step}: {best[0]} + {best[1]} -> {best[0] + best[1]} ({counts[best]})")
for item in corpus:
symbols, out, i = item[0], [], 0
while i < len(symbols):
if i + 1 < len(symbols) and (symbols[i], symbols[i + 1]) == best:
out.append(symbols[i] + symbols[i + 1])
i += 2
else:
out.append(symbols[i])
i += 1
item[0] = out
for symbols, _, word in corpus:
print(f"{word}: {' '.join(symbols)}")