Реализация BPE-токенизатора с нуля¶
~7 минут чтения
Предварительно: Токенизация LLM | Сравнение токенизаций
Зачем это нужно¶
Токенизация -- первый шаг любой LLM, и BPE (Byte Pair Encoding) -- самый распространенный алгоритм: его используют GPT-⅔/4, LLaMA, RoBERTa. Идея проста: начни с отдельных символов и итеративно склеивай самые частые пары. За 10K итераций алгоритм сам выучит, что "th"+"e" = "the", "ing" -- частый суффикс, а "##" в WordPiece отмечает продолжение слова. Реализация с нуля на Python занимает ~100 строк и дает глубокое понимание того, как текст превращается в числа для модели.
Обзор¶
Ключевой инсайт: BPE начинает с отдельных символов и итеративно сливает самые частые пары в новые токены, пока не достигнет целевого размера словаря. Это балансирует между размером словаря и длиной последовательности, обрабатывая редкие слова через subword-декомпозицию.
Токенизаторы 2026:
| Токенизатор | Модели | Особенность |
|---|---|---|
| BPE | GPT-⅔/4, RoBERTa | Merge-based, greedy |
| Unigram | T5, ALBERT | Вероятностный, несколько сегментаций |
| WordPiece | BERT | ## префикс для subwords |
| SentencePiece | mT5, XLNet | Language-agnostic |
| Byte-level BPE | GPT-2+, LLaMA | Работает с сырыми байтами |
Алгоритм BPE¶
Основной алгоритм¶
graph TD
IN["Input: корпус текста,<br/>целевой размер словаря V"] --> S1
S1["1. Инициализация<br/>vocab = все уникальные символы<br/>text = посимвольная разбивка"] --> S2
S2["2. Подсчет пар<br/>pairs = {('t','h'): 50, ('h','e'): 100, ...}"] --> S3
S3["3. Слияние лучшей пары<br/>best = ('t','h') → 'th'<br/>vocab.add('th')"] --> CHECK
CHECK{"|vocab| = V?"} -->|Нет| S2
CHECK -->|Да| OUT["Output: словарь + merge rules"]
style IN fill:#e8eaf6,stroke:#3f51b5
style S1 fill:#e8f5e9,stroke:#4caf50
style S2 fill:#e8f5e9,stroke:#4caf50
style S3 fill:#fff3e0,stroke:#ef6c00
style CHECK fill:#f3e5f5,stroke:#9c27b0
style OUT fill:#e8eaf6,stroke:#3f51b5Пошаговый пример¶
Corpus: "the cat the dog"
Initial (character level):
["t", "h", "e", " ", "c", "a", "t", " ", "t", "h", "e", " ", "d", "o", "g"]
Iteration 1: ("t", "h") → "th"
["th", "e", " ", "c", "a", "t", " ", "th", "e", " ", "d", "o", "g"]
Iteration 2: ("th", "e") → "the"
["the", " ", "c", "a", "t", " ", "the", " ", "d", "o", "g"]
Iteration 3: ("t", "h") already merged...
Continue with next most frequent pair
... until vocabulary size reached
Реализация на Python¶
Базовый BPE Trainer¶
import re
from collections import defaultdict
from typing import Dict, List, Tuple, Set
class BPETrainer:
"""Train a BPE tokenizer from scratch."""
def __init__(self, vocab_size: int = 1000):
self.vocab_size = vocab_size
self.vocab: Set[str] = set()
self.merges: List[Tuple[str, str]] = [] # (1)!
def train(self, corpus: str) -> None:
"""Train BPE on corpus."""
# Step 1: Tokenize to characters
words = re.findall(r'\w+|\S', corpus) # (2)!
word_freqs = defaultdict(int)
for word in words:
word_freqs[tuple(word)] += 1 # (3)!
# Initialize vocabulary with characters
self.vocab = set(char for word in word_freqs for char in word)
self.merges = []
# Iteratively merge pairs
while len(self.vocab) < self.vocab_size:
# Count pairs
pairs = self._get_pairs(word_freqs)
if not pairs:
break
# Find best pair
best_pair = max(pairs, key=pairs.get) # (4)!
# Merge
word_freqs = self._merge_pair(word_freqs, best_pair)
new_token = best_pair[0] + best_pair[1]
self.vocab.add(new_token)
self.merges.append(best_pair) # (5)!
def _get_pairs(self, word_freqs: Dict) -> Dict[Tuple[str, str], int]:
"""Count all adjacent pairs."""
pairs = defaultdict(int)
for word, freq in word_freqs.items():
for i in range(len(word) - 1):
pairs[(word[i], word[i + 1])] += freq
return pairs
def _merge_pair(
self,
word_freqs: Dict,
pair: Tuple[str, str]
) -> Dict:
"""Merge all occurrences of pair."""
new_word_freqs = {}
bigram = pair
replacement = pair[0] + pair[1]
for word, freq in word_freqs.items():
new_word = []
i = 0
while i < len(word):
if i < len(word) - 1 and (word[i], word[i + 1]) == bigram:
new_word.append(replacement)
i += 2
else:
new_word.append(word[i])
i += 1
new_word_freqs[tuple(new_word)] = freq
return new_word_freqs
- Порядок merges критичен -- при encoding применяем их в том же порядке. Это единственное, что нужно сохранить вместе со словарем.
- Pre-tokenization: разбиваем на слова/символы ДО обучения BPE. GPT-2 использует более сложный regex для лучшего разбиения.
- Слова хранятся как tuple символов:
"cat"->("c", "a", "t"). Tuple нужен как ключ dict (list нельзя хэшировать). - Greedy: всегда сливаем самую частую пару. Не оптимально глобально, но работает хорошо на практике.
- Merge rules записываются в порядке обучения -- этот порядок используется при encode.
BPE Tokenizer (кодирование)¶
class BPETokenizer:
"""BPE tokenizer for encoding text."""
def __init__(self, vocab: Set[str], merges: List[Tuple[str, str]]):
self.vocab = vocab
self.merges = merges
self.merge_ranks = {merge: i for i, merge in enumerate(merges)}
def encode(self, text: str) -> List[str]:
"""Encode text using learned BPE."""
# Start with characters
tokens = list(text)
# Apply merges in order of priority
while len(tokens) >= 2:
# Find the best pair to merge (lowest rank)
best_pair = None
best_rank = float('inf')
for i in range(len(tokens) - 1):
pair = (tokens[i], tokens[i + 1])
if pair in self.merge_ranks:
rank = self.merge_ranks[pair]
if rank < best_rank:
best_rank = rank
best_pair = pair
if best_pair is None:
break
# Merge all occurrences
tokens = self._merge(tokens, best_pair)
return tokens
def _merge(self, tokens: List[str], pair: Tuple[str, str]) -> List[str]:
"""Merge all occurrences of pair in token list."""
new_tokens = []
i = 0
while i < len(tokens):
if i < len(tokens) - 1 and tokens[i] == pair[0] and tokens[i + 1] == pair[1]:
new_tokens.append(pair[0] + pair[1])
i += 2
else:
new_tokens.append(tokens[i])
i += 1
return new_tokens
def decode(self, tokens: List[str]) -> str:
"""Decode tokens back to string."""
return ''.join(tokens)
Полный пример¶
# Train
corpus = "the cat sat on the mat the cat the dog"
trainer = BPETrainer(vocab_size=50)
trainer.train(corpus)
print(f"Vocabulary: {trainer.vocab}")
print(f"Merges: {trainer.merges}")
# Encode
tokenizer = BPETokenizer(trainer.vocab, trainer.merges)
tokens = tokenizer.encode("the cat")
print(f"Tokens: {tokens}") # ['the', ' ', 'c', 'a', 't']
# Decode
text = tokenizer.decode(tokens)
print(f"Decoded: {text}") # 'the cat'
Byte-Level BPE¶
Зачем byte-level?¶
Проблемы character-level BPE:
- Unicode содержит 100K+ символов -- огромный начальный словарь
- Невиданные символы становятся UNK
- Мультиязычный текст взрывает размер словаря
Byte-level решение:
- Начальный словарь фиксирован: 256 байтовых токенов -- и всё
- Любой Unicode-текст представим через UTF-8 байты
- Ноль UNK -- работает для всех языков, эмодзи, спецсимволов
Пример: "hello" → [104, 101, 108, 108, 111] (байты) | "你好" → [228, 189, 160, 229, 165, 189] (UTF-8)
Реализация Byte-Level BPE¶
class ByteLevelBPE:
"""Byte-level BPE as used in GPT-2/3/4."""
def __init__(self, vocab_size: int = 50257):
self.vocab_size = vocab_size
# Base vocabulary: 256 bytes + special tokens
self.byte_encoder = self._bytes_to_unicode()
self.byte_decoder = {v: k for k, v in self.byte_encoder.items()}
def _bytes_to_unicode(self) -> Dict[int, str]:
"""Map bytes to unicode characters for readability."""
# Printable ASCII stays as-is
bs = list(range(ord('!'), ord('~') + 1))
bs += list(range(ord('¡'), ord('¬') + 1))
bs += list(range(ord('®'), ord('ÿ') + 1))
cs = bs[:]
n = 0
for b in range(256):
if b not in bs:
bs.append(b)
cs.append(256 + n)
n += 1
return {b: chr(c) for b, c in zip(bs, cs)}
def tokenize(self, text: str) -> List[str]:
"""Tokenize text using byte-level BPE."""
# Convert to bytes, then to unicode representation
tokens = []
for byte in text.encode('utf-8'):
tokens.append(self.byte_encoder[byte])
return tokens
Сравнение токенизаторов¶
BPE vs Unigram vs WordPiece¶
BPE (GPT, RoBERTa): greedy merging частых пар, детерминированная сегментация, быстрый encoding, может пропустить оптимальное разбиение.
Unigram (T5, ALBERT): вероятностная модель, несколько возможных сегментаций, лучше для языков без пробелов (CJK), EM-алгоритм для обучения.
WordPiece (BERT): похож на BPE, но с ## префиксом для subwords. "playing" → ["play", "##ing"] -- четкие границы подслов.
Таблица сравнения¶
| Свойство | BPE | Unigram | WordPiece |
|---|---|---|---|
| Обучение | Слияние пар | EM-алгоритм | Слияние пар |
| Сегментация | Детерминированная | Вероятностная | Детерминированная |
| Маркер subword | Нет | Нет | ## |
| Скорость | Быстрая | Средняя | Быстрая |
| Мультиязычность | Хорошая | Лучше | Хорошая |
| Используется | GPT, RoBERTa | T5, XLNet | BERT |
Специальные токены¶
Распространенные специальные токены¶
| Токен | Назначение | Модели |
|---|---|---|
<|endoftext|> |
End of text | GPT-⅔/4 |
<|pad|> |
Padding | Most models |
<|unk|> |
Unknown token | Legacy models |
<s> |
Start of sequence | LLaMA |
</s> |
End of sequence | LLaMA |
[CLS] |
Classification | BERT |
[SEP] |
Separator | BERT |
[MASK] |
Masking for MLM | BERT |
Обработка специальных токенов¶
class BPETokenizerWithSpecial:
"""BPE tokenizer with special tokens."""
SPECIAL_TOKENS = {
'<|endoftext|>': 50256,
'<|pad|>': 50257,
'<|unk|>': 50258,
}
def encode(self, text: str) -> List[int]:
"""Encode text to token IDs."""
tokens = []
# Check for special tokens first
i = 0
while i < len(text):
found_special = False
for special, token_id in self.SPECIAL_TOKENS.items():
if text[i:].startswith(special):
tokens.append(token_id)
i += len(special)
found_special = True
break
if not found_special:
# Regular BPE encoding
# ... (implementation as before)
i += 1
return tokens
Продакшен-оптимизации¶
Оптимизация производительности¶
class OptimizedBPE:
"""Production-ready BPE with optimizations."""
def __init__(self, vocab: Set[str], merges: List[Tuple[str, str]]):
self.vocab = vocab
self.merges = merges
self.merge_ranks = {merge: i for i, merge in enumerate(merges)}
# Pre-compile regex for word splitting
self.pattern = re.compile(r"""'s|'t|'re|'ve|'m|'ll|'d| ?\w+| ?\d+| ?[^\s\w\d]+|\s+(?!\S)|\s+""")
def encode_batch(self, texts: List[str]) -> List[List[int]]:
"""Encode multiple texts in parallel."""
return [self.encode(text) for text in texts]
def encode_fast(self, text: str) -> List[int]:
"""Fast encoding with word-level caching."""
words = self.pattern.findall(text)
tokens = []
for word in words:
# Could add word-level cache here
word_tokens = self._encode_word(word)
tokens.extend(word_tokens)
return tokens
def _encode_word(self, word: str) -> List[str]:
"""Encode a single word."""
tokens = list(word)
while len(tokens) >= 2:
# Find best pair
pairs = [(tokens[i], tokens[i + 1]) for i in range(len(tokens) - 1)]
ranked = [(p, self.merge_ranks.get(p, float('inf'))) for p in pairs]
best_pair, best_rank = min(ranked, key=lambda x: x[1])
if best_rank == float('inf'):
break
tokens = self._merge(tokens, best_pair)
return tokens
Компромиссы размера словаря¶
| Размер словаря | Длина последовательности | Размер модели | Покрытие |
|---|---|---|---|
| 10K | Длиннее | Меньше | Слабое |
| 30K | Баланс | Средний | Хорошее |
| 50K | Короче | Больше | Отличное |
| 100K | Самая короткая | Самый большой | Очень высокое |
Числа для интервью¶
Размеры словарей¶
| Модель | Размер словаря | Тип |
|---|---|---|
| GPT-2 | 50,257 | Byte-level BPE |
| GPT-¾ | ~100,000 | Byte-level BPE |
| LLaMA | 32,000 | SentencePiece BPE |
| BERT | 30,000 | WordPiece |
| T5 | 32,000 | SentencePiece Unigram |
Коэффициенты сжатия¶
| Язык | Отношение символы:токены | Сжатие |
|---|---|---|
| Английский | 4:1 | 75% |
| Китайский | 1.5:1 | 33% |
| Код | 3:1 | 66% |
| Смешанный | 3:1 | 66% |
Потребление памяти¶
| Размер словаря | Память Embedding (d=4096) |
|---|---|
| 32K | 512 MB |
| 50K | 800 MB |
| 100K | 1.6 GB |
Время обучения¶
| Размер корпуса | Размер словаря | Время обучения |
|---|---|---|
| 1 GB | 30K | 5 минут |
| 10 GB | 50K | 30 минут |
| 100 GB | 100K | 3 часа |
Gotchas¶
Порядок merge правил критичен
При encoding BPE должен применять merges в том порядке, в котором они были выучены при training. Merge ('t','h')->'th' перед ('th','e')->'the'. Если нарушить порядок -- получишь другую токенизацию и модель будет видеть незнакомые токены. Это самая частая ошибка при реализации с нуля.
Byte-level BPE -- не то же что Character-level BPE
Character-level BPE начинает с Unicode символов (~100K+ начальный словарь). Byte-level BPE начинает с 256 байтов. Byte-level = 0 UNK для любого языка, фиксированный начальный словарь. Но CJK символы разбиваются на 3 байта (UTF-8) -- отсюда хуже compression ratio для китайского/японского (1.5:1 vs 4:1 для английского).
vocab_size напрямую влияет на размер модели
Embedding matrix = vocab_size x d_model. При d_model=4096: 32K vocab = 512 MB, 100K vocab = 1.6 GB. Это не "просто словарь" -- это trainable параметры. Увеличение vocab в 3x увеличивает embedding layer в 3x. А vocab определяется до обучения и не меняется -- ошибка = переобучение модели с нуля.
Interview Q&A¶
Q: Объясните алгоритм BPE пошагово.
Red flag: "BPE разбивает слова на символы" (это только инициализация, не алгоритм)
Strong answer: "BPE Training: (1) Разбить корпус на символы. (2) Подсчитать частоту всех пар соседних токенов. (3) Слить самую частую пару в новый токен, добавить в словарь. (4) Повторять 2-3 пока |vocab| не достигнет целевого размера. BPE Encoding: применить выученные merges к тексту в порядке приоритета (порядок обучения). Пример: 'the' -> ['t','h','e'] -> ['th','e'] -> ['the']. Training greedy (всегда лучшая пара), encoding детерминированный (фиксированный порядок merges)."
Q: Почему GPT-2+ используют byte-level BPE?
Red flag: "Потому что байты меньше символов"
Strong answer: "Три причины: (1) Фиксированный начальный словарь 256 токенов вместо 100K+ Unicode символов -- предсказуемый и компактный. (2) Ноль UNK -- любой текст на любом языке представим через UTF-8 байты. (3) Мультиязычность без специальной обработки -- китайский, код, эмодзи -- всё работает. Trade-off: CJK получают худший compression ratio (1 символ = 3 байта), отсюда 'token tax' для не-латинских языков."
Q: Как vocab_size влияет на качество модели?
Strong answer: "Маленький vocab (10K): длинные последовательности, медленный inference, маленькая embedding matrix. Большой vocab (100K): короткие последовательности, быстрый inference, но 1.6 GB только на embedding при d=4096. Sweet spot: 30-50K для большинства задач. Для мультиязычных моделей больше (100K+), для доменных -- можно меньше. LLaMA выбрал 32K (баланс), GPT-4 ~100K (покрытие всех языков)."
Самопроверка
-
Ручной BPE: Дан корпус
"aaabdaaabac". Проведите 3 итерации BPE вручную. Какой словарь получится? Какие merge rules? Проверьте: закодируйте"aaba"полученными правилами. -
Compression ratio: Текст на русском (UTF-8) обрабатывается byte-level BPE. Символ "Д" = 2 байта (0xD0 0x94). Слово "Данные" = 12 байтов. Если BPE выучил merge "Данные" -> один токен, каков compression ratio в токенах vs байтах? Почему русский текст дороже английского в API с оплатой за токены?
-
Vocab size trade-off: У вас модель с d_model=4096. Текущий vocab=32K. Клиент просит добавить 10 языков, и вы рассматриваете увеличение vocab до 100K. Посчитайте: (a) на сколько MB вырастет embedding matrix, (b) как это повлияет на inference latency, © предложите альтернативу увеличению vocab.
See Also¶
- Токенизация LLM -- обзор подходов к токенизации
- Сравнение токенизаций -- BPE vs Unigram vs WordPiece: детальное сравнение
Источники¶
- arXiv — "Neural Machine Translation of Rare Words with Subword Units" (Sennrich et al., 2016)
- Sebastian Raschka — "Implementing BPE from Scratch" (Jan 2025)
- Hugging Face — Tokenizers library documentation
- OpenAI — GPT-2 paper and code
- Andrej Karpathy — "Let's build GPT" (tokenization section)
- Google — SentencePiece documentation
- BPE Tokenizer tutorials (fancyerii, Medium)
- Byte-level BPE explanation (GPT-2 paper)
- Hugging Face LLM Course — Tokenization chapter
- MarkTechPost — BPE algorithm explanation