NLP: Learn BPE merges

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

Example 1 · Input
6
4
low 5
lower 2
newest 6
widest 3
Expected 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_
Example 2 · Input
2
1
aaaa 1
Expected output
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)}")

Lesson: Byte-pair encoding tokenization →