NLP: Encode words with BPE merges

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 print word: tokens (the word as given) and ids: .... At the end print total 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

Example 1 · Input
6
e s
es t
est _
l o
lo w
e w
2
lowest
newer
Expected output
lowest: low est_
ids: 32 30
newer: n ew e r _
ids: 15 33 6 19 1
total tokens: 7
Example 2 · Input
2
u g
h ug
2
hugs
mug!
Expected output
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)

Lesson: Byte-pair encoding tokenization →