Implement a byte-pair encoding tokenizer with train, encode and decode, where training keeps merging the most frequent adjacent pair until counts fall below a threshold.

Work on bytes so any text encodes. Training merges the most frequent adjacent pair into a new ID until its count falls below the threshold.

from collections import Counter

def pairs(ids):
    return zip(ids, ids[1:])

def merge(ids, pair, new):
    out, i = [], 0
    while i < len(ids):
        if tuple(ids[i:i + 2]) == pair:
            out.append(new)
            i += 2
        else:
            out.append(ids[i])
            i += 1
    return out

def train(text, min_count):
    ids, merges = list(text.encode()), {}
    while len(ids) > 1:
        pair, n = Counter(pairs(ids)).most_common(1)[0]
        if n < min_count:
            break
        merges[pair] = 256 + len(merges)
        ids = merge(ids, pair, merges[pair])
    return merges

def encode(text, merges):
    ids = list(text.encode())
    while len(ids) > 1:
        cand = [p for p in set(pairs(ids)) if p in merges]
        if not cand:
            break
        p = min(cand, key=merges.get)  # earliest merge
        ids = merge(ids, p, merges[p])
    return ids

def decode(ids, merges):
    vocab = {i: bytes([i]) for i in range(256)}
    for (a, b), i in merges.items():  # in merge order
        vocab[i] = vocab[a] + vocab[b]
    return b"".join(vocab[i] for i in ids).decode(
        "utf-8", errors="replace")

Encoding applies merges in training order, always the earliest-learned pair present; decoding concatenates byte strings. Interviewers check the round trip, overlapping pairs like aaa, and the stopping rule.