BPE: как строится словарь токенов (запускаемый пример)

Разбираем алгоритм, которым реально строят словари токенов в GPT и многих других моделях — Byte-Pair Encoding (BPE). С запускаемым примером.

BPE (Byte-Pair Encoding) — алгоритм, который начинает с отдельных символов и многократно сливает самую частую соседнюю пару в новый токен, пока словарь не достигнет нужного размера.

Идея в одном предложении

Начинаем с алфавита из отдельных символов. Затем смотрим, какая пара соседних токенов встречается в корпусе чаще всего, и склеиваем её в один новый токен. Повторяем. Частые сочетания постепенно «срастаются» в целые подслова и даже слова, а редкие так и остаются набором мелких кусков.

Алгоритм по шагам

Разбить все слова корпуса на символы (добавив маркер конца слова).
Посчитать частоты всех соседних пар токенов.
Слить самую частую пару в новый токен по всему корпусу.
Повторять шаги 2–3 заданное число раз (или пока не наберём нужный размер словаря).

Запускаем BPE руками

Возьмём крошечный «корпус» из четырёх слов с частотами и сделаем четыре слияния. Нажмите «Запустить» и проследите, как из букв собираются подслова.

from collections import Counter

# Учебный "корпус": слова с частотами. Каждое слово храним как
# последовательность символов с маркером конца слова "_".
corpus = {"low": 5, "lower": 2, "newest": 6, "widest": 3}
vocab = {tuple(word) + ("_",): freq for word, freq in corpus.items()}

def get_pair_stats(vocab):
    pairs = Counter()
    for symbols, freq in vocab.items():
        for i in range(len(symbols) - 1):
            pairs[(symbols[i], symbols[i + 1])] += freq
    return pairs

def merge_pair(pair, vocab):
    a, b = pair
    new_vocab = {}
    for symbols, freq in vocab.items():
        merged, i = [], 0
        while i < len(symbols):
            if i < len(symbols) - 1 and symbols[i] == a and symbols[i + 1] == b:
                merged.append(a + b)   # склеиваем пару в один токен
                i += 2
            else:
                merged.append(symbols[i])
                i += 1
        new_vocab[tuple(merged)] = freq
    return new_vocab

for step in range(1, 5):
    stats = get_pair_stats(vocab)
    best = max(stats, key=stats.get)
    print(f"Слияние {step}: {best[0]!r} + {best[1]!r} -> {(best[0]+best[1])!r} (частота {stats[best]})")
    vocab = merge_pair(best, vocab)

print()
print("Слово 'newest' теперь разбито на токены:")
for symbols in vocab:
    if "".join(symbols).replace("_", "") == "newest":
        print(" ", list(symbols))

Вывод:

Слияние 1: 'e' + 's' -> 'es' (частота 9)
Слияние 2: 'es' + 't' -> 'est' (частота 9)
Слияние 3: 'est' + '_' -> 'est_' (частота 9)
Слияние 4: 'l' + 'o' -> 'lo' (частота 7)

Слово 'newest' теперь разбито на токены:
  ['n', 'e', 'w', 'est_']

Что произошло: пара e+s встречалась чаще всего (в «newest» и «widest»), её слили в es. Затем es+t → est, потом приклеился маркер конца слова. В итоге частый суффикс est_ стал единым токеном — и слово «newest» теперь кодируется всего четырьмя токенами: n, e, w, est_. Именно так BPE «выучивает» осмысленные куски без всякого словаря морфем — чисто по статистике.

Почему это работает

Частые слова и морфемы естественным образом склеиваются в крупные токены (потому что их пары встречаются часто), а редкие остаются мелкими кусками. Так словарь автоматически расходует «слоты» на то, что реально часто встречается. Незнакомое слово всегда можно собрать хотя бы из символов — поэтому никаких <UNK>.

Байтовый BPE: ещё один трюк

Современные модели часто начинают не с символов, а с байтов (byte-level BPE). Тогда базовый «алфавит» — это 256 байтов, и абсолютно любой текст на любом языке, эмодзи или даже бинарные данные гарантированно кодируются без пропусков. Это делает токенизатор по-настоящему универсальным.

Итог

BPE стартует с символов и жадно сливает самые частые пары в новые токены.
Частые морфемы и слова срастаются в крупные токены, редкие остаются мелкими.
Любое слово всегда собирается хотя бы из символов — проблема незнакомых слов исчезает.
Byte-level BPE стартует с байтов и кодирует абсолютно любой текст.