BPE Algorithm: Sennrich 2016 Line by Line — Pseudocode, Complexity, Edge Cases

Ders Haritası#

1. BPE'nin tarihi: Gage 1994 → Sennrich 2016
2. Algorithm yüksek seviye: merge-by-frequency
3. Pre-tokenization: word boundary
4. Training pseudo-code satır satır
5. Merge rules: nasıl saklanır
6. Encoding pseudo-code: training tersi
7. Complexity analysis: O(N·V) training, O(L²) encoding
8. Edge cases: Unicode, whitespace, special tokens
9. Byte-level BPE (GPT-2 variant) ön bakış
10. Modül 6.3'e köprü

1. BPE'nin Tarihi#

Philip Gage 1994 — Original BPE#

"Replace most frequent pair of bytes with a new byte (token). Repeat."

Input: "aaabdaaabac"
Frequencies: aa=4, ab=2, bd=1, da=1, ac=1, ba=1
Most frequent: aa → replace with X
Result: "XabdXabac"
Continue...

Sennrich 2016 — NLP adaptation#

1. Words üzerinde çalış (bytes değil)
2. Sub-word units öğren
3. Out-of-vocabulary problem solve

GPT-2 byte-level adaptation (2019)#

Modern modifications#

• GPT-4 cl100k: improved digit handling
• GPT-4o o200k: better multilingual coverage
• Llama 3 tiktoken-style: similar to OpenAI

2. BPE Algorithm Yüksek Seviye#

Pseudo-code (high-level)#

1. Initialize vocab = {all characters/bytes}
2. Pre-tokenize text into words
3. For each word, split into characters: "hello" → ["h", "e", "l", "l", "o"]
4. Repeat until vocab_size hit:
   a. Count all adjacent byte-pairs across corpus
   b. Find most frequent pair (e.g., "lo" appears 1000 times)
   c. Add this pair as new token to vocab
   d. Replace all occurrences in corpus: "hello" → ["h", "e", "l", "lo"]
5. Save vocab + merge rules

Sonuç#

• Vocabulary: characters + learned merged tokens
• Merge rules: sıralı pair → new token mappings

Encoding (yeni text tokenize etme)#

1. Pre-tokenize text → words
2. Split each word into characters
3. Apply merge rules in training order
4. Final tokens

3. Pre-tokenization — Word Boundary#

Pre-tokenization niye?#

1. Cross-word merges'i önle

2. Compute speedup

Pre-tokenization stratejileri#

GPT-2 regex

import regex as re
pat = re.compile(r"""'s|'t|'re|'ve|'m|'ll|'d| ?\p{L}+| ?\p{N}+| ?[^\s\p{L}\p{N}]+|\s+(?!\S)|\s+""")

• English contractions ('s, 't, vb.) ayır
• Letters group (Unicode-aware)
• Numbers group
• Punctuation group
• Whitespace handling

GPT-4 cl100k regex (improved)

pat = re.compile(r"""'(?:[sdmt]|ll|ve|re)| ?\p{L}+| ?\p{N}{1,3}| ?[^\s\p{L}\p{N}]+[\r\n]*|\s*[\r\n]+|\s+(?!\S)|\s+""")

Türkçe için

Alternative: minimal pre-tokenization#

Practical#

4. BPE Training Pseudo-code — Satır Satır#

Algorithm: BPE Training
Input: corpus (text), vocab_size
Output: vocab, merge_rules

# Adım 1: Pre-tokenize
words = pre_tokenize(corpus)  # ["hello", "world", "hello", ...]

# Adım 2: Initialize
vocab = unique_characters(corpus)  # {h, e, l, o, w, r, d, ...}
word_freq = count(words)  # {"hello": 5, "world": 3, ...}

# Adım 3: Her kelimeyi karakter listesi olarak temsil et
word_repr = {}
for word, freq in word_freq:
    word_repr[word] = list(word)  # "hello" → ["h", "e", "l", "l", "o"]

# Adım 4: Iterative merge
merge_rules = []
while len(vocab) < vocab_size:
    # 4a. Count all adjacent pairs
    pair_freq = {}
    for word, freq in word_freq.items():
        chars = word_repr[word]
        for i in range(len(chars) - 1):
            pair = (chars[i], chars[i+1])
            pair_freq[pair] = pair_freq.get(pair, 0) + freq

    # 4b. Find most frequent pair
    if not pair_freq:
        break  # nothing to merge
    best_pair = max(pair_freq, key=pair_freq.get)

    # 4c. Add to vocab
    new_token = best_pair[0] + best_pair[1]  # e.g., "h" + "e" → "he"
    vocab.add(new_token)
    merge_rules.append(best_pair)

    # 4d. Update word_repr (replace pair with merged token)
    for word in word_repr:
        chars = word_repr[word]
        new_chars = []
        i = 0
        while i < len(chars):
            if i < len(chars) - 1 and (chars[i], chars[i+1]) == best_pair:
                new_chars.append(new_token)
                i += 2
            else:
                new_chars.append(chars[i])
                i += 1
        word_repr[word] = new_chars

return vocab, merge_rules

Adım analizi#

• Her iter: 4a + 4b + 4c + 4d
• 4a: O(N) — tüm word_repr scan
• 4b: O(P) — unique pair sayısı, max O(N)
• 4d: O(N) — corpus replace

5. Merge Rules — Nasıl Saklanır#

1. Vocabulary: token → ID mapping (örn.
   {"hello": 5, "the": 10}
   )
2. Merge rules: ordered list of pairs (örn.
   [("h","e"), ("he","l"), ("hel","lo")]
   )

File format (HuggingFace style)#

{
  "vocab": {
    "<unk>": 0,
    "<s>": 1,
    "</s>": 2,
    "a": 3,
    "b": 4,
    "ab": 5,
    "the": 6,
    ...
  },
  "merges": [
    "a b",
    "t h",
    "th e",
    ...
  ]
}

Sennrich format (orig.)#

• vocab.txt
  : bir token per line
• merges.txt
  : bir pair per line, sıralı

Modern (tiktoken)#

<binary blob>

Encoding consistency#

1. Pre-tokenization deterministic
2. Merge rules sıralı uygulanır
3. Tie-breaking deterministic (first match wins)

6. BPE Encoding Pseudo-code#

Algorithm: BPE Encoding
Input: text, vocab, merge_rules
Output: token_ids

# Adım 1: Pre-tokenize
words = pre_tokenize(text)

# Adım 2: Her kelime için
result = []
for word in words:
    # 2a. Split into characters
    tokens = list(word)

    # 2b. Apply merge rules in order
    for rule in merge_rules:
        i = 0
        new_tokens = []
        while i < len(tokens):
            if i < len(tokens) - 1 and (tokens[i], tokens[i+1]) == rule:
                new_tokens.append(tokens[i] + tokens[i+1])
                i += 2
            else:
                new_tokens.append(tokens[i])
                i += 1
        tokens = new_tokens

    # 2c. Convert to IDs
    ids = [vocab[t] for t in tokens]
    result.extend(ids)

return result

Walkthrough#

Optimization: priority queue#

Use a priority queue of pairs in word.
Find highest-priority pair (first in merge_rules).
Merge it.
Update queue.
Repeat.

Türkçe encoding örnek#

• Initial: ['y', 'ü', 'r', 'ü', 'y', 'o', 'r', 'u', 'm']
• Apply rules → ['yü', 'rü', 'yor', 'um'] → ['yürü', 'yorum']

7. Complexity Analysis#

Training complexity#

• N = corpus size (bytes or characters)
• V = target vocabulary size
• W = unique word count

• Pair counting: O(N) — scan corpus
• Find max: O(P) where P is unique pairs (≤ N)
• Update: O(N) — scan + replace

• N = 10 GB Turkish corpus = 10^10 bytes
• V = 64K
• 10^10 × 64K = 6.4 × 10^14 operations

Encoding complexity#

• Apply rules: O(L × R) naive, O(L log L) optimized

Memory complexity#

• Corpus representation: O(N)
• Word_freq: O(W)
• Pair counts: O(P) — up to O(N) but usually much less

Production patterns#

• Pre-compiled C/Rust binary
• Memory-mapped file (no full load)
• Multi-threaded encoding
• BPE algorithm with priority queue

8. Edge Cases#

1. Unicode normalization#

import unicodedata
text = unicodedata.normalize("NFC", text)

2. Whitespace handling#

3. Special tokens#

vocab = {
    "<s>": 0,
    "</s>": 1,
    "<pad>": 2,
    # BPE-learned tokens
    "a": 3, "the": 4, ...
}

4. Numbers#

5. Multilingual tokenization#

6. Code tokenization#

def hello():
    print("Hello")

7. Emoji + symbol#

8. Whitespace-only sequences#

Pratik#

9. Byte-level BPE Ön Bakış#

Klasik BPE (Sennrich)#

• Initial vocab: unique characters (Unicode codepoints)
• Sub-character merges yok
• Multilingual: tüm dilleri kapsayacak vocab gerek

Byte-level BPE (GPT-2)#

• Initial vocab: 256 bytes (UTF-8 alphabet)
• Sub-byte merges yok
• Tüm input encodable (any Unicode)

Avantajlar#

1. No OOV ever
2. Smaller initial vocab (256 vs 100K+)
3. Robust to typos / new chars / unseen scripts
4. Compact representation byte-level

Dezavantajlar#

1. More tokens per Turkish/Chinese char (UTF-8 2-4 bytes)
2. Initial sequence longer

Pratik fark#

10. Modül 6.3'e Köprü#

• Sıfırdan implement (200 satır Python)
• Training + encoding + decoding hepsi
• Türkçe corpus üzerinde deneme
• Performance: pure Python vs optimized Rust comparison
• Visual: vocab + merge rules export

Ön hazırlık#

• Yukarıdaki training pseudo-code'u kavradım mı?
• Encoding pseudo-code'u nasıl çalışıyor anladım mı?
• Edge case'leri öğrendim mi?
• Karpathy "minbpe" repo'su açık (referans için)

Karpathy minbpe#

11. Mini Egzersizler#

1. Manual BPE trace: "ab ab cd cd cd" corpus'unda 3 merge'den sonra vocab?
2. Complexity: V=128K, N=10GB. CPU vs GPU vs Rust training süresi tahmini?
3. Encoding trace: "the cat" — merge rules: [("t","h"), ("th","e"), (" ","c"), ("c","a")]. Token sequence?
4. Edge case: "İstanbul'da" tokenization'ı GPT-4 (cl100k) regex pattern ile nasıl handle eder?
5. Multilingual corpus: %80 İngilizce + %20 Türkçe corpus üzerinde BPE training. Sonuç fair Türkçe coverage var mı?

Bu Derste Neler Öğrendik?#

Sıradaki Ders#