Input:  "The quick brown fox"
→ Tokens: [464, 2069, 7586, 21831]
→ Model sees numbers, not text

Training corpus:
("hug", 10) ("ugg", 5) ("ggi", 3) ("gin", 3) ("ing", 3)

Step 1: Split into characters
h u g </w>   → 10
u g g </w>   → 5
...

Step 2: Count pairs
("h","u") → 10
("u","g") → 15
("g","g") → 5
...

Step 3: Merge most frequent → "hu"
Update: "hu g </w>" → 10

from collections import defaultdict
import re

class BPETokenizer:
    def __init__(self):
        self.vocab = {}
        self.merges = []
        self.word_freq = defaultdict(int)

    def get_stats(self, word_freqs):
        pairs = defaultdict(int)
        for word, freq in word_freqs.items():
            symbols = word.split()
            for i in range(len(symbols)-1):
                pairs[(symbols[i], symbols[i+1])] += freq
        return pairs

    def merge_vocab(self, pair, word_freqs):
        new_word_freqs = defaultdict(int)
        bigram = ' '.join(pair)
        replacement = ''.join(pair)
        for word, freq in word_freqs.items():
            new_word = word.replace(bigram, replacement)
            new_word_freqs[new_word] = freq
        return new_word_freqs

    def train(self, text, vocab_size=300, verbose=False):
        # Preprocess
        text = re.sub(r'\s+', ' ', text)
        words = text.split()

        # Count word frequency
        for word in words:
            self.word_freq[' '.join(list(word)) + ' </w>'] += 1

        num_merges = vocab_size - 256  # 256 bytes
        for i in range(num_merges):
            pairs = self.get_stats(self.word_freq)
            if not pairs: break
            best_pair = max(pairs, key=pairs.get)
            self.merges.append(best_pair)
            self.word_freq = self.merge_vocab(best_pair, self.word_freq)
            if verbose and i < 10:
                print(f"Merge {i+1}: {best_pair} → {' '.join(best_pair)}")

        # Build vocab
        self.vocab = self.build_vocab()

    def build_vocab(self):
        vocab = {i: bytes([i]) for i in range(256)}
        for (p0, p1), idx in self.get_merge_indices().items():
            vocab[256 + idx] = vocab[p0] + vocab[p1]
        vocab[256 + len(self.merges)] = b'</w>'
        return vocab

    def get_merge_indices(self):
        merge_to_idx = {}
        for i, pair in enumerate(self.merges):
            merge_to_idx[pair] = i
        return merge_to_idx

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False
        self.token_id = None

class BPEEncoder:
    def __init__(self, merges, vocab):
        self.merges = merges
        self.vocab = vocab
        self.trie = self.build_trie()

    def build_trie(self):
        root = TrieNode()
        for token_id, token_bytes in self.vocab.items():
            node = root
            for byte in token_bytes:
                if byte not in node.children:
                    node.children[byte] = TrieNode()
                node = node.children[byte]
            node.is_end = True
            node.token_id = token_id
        return root

    def encode(self, text):
        if not text: return []

        # Split into characters
        word = list(text) + ['</w>']
        ids = []

        while len(word) > 1:
            # Find best pair to merge
            pairs = [(i, self.get_rank(word, i)) for i in range(len(word)-1)]
            best_pair_idx = min(pairs, key=lambda x: x[1])[0]

            # Merge
            pair = (word[best_pair_idx], word[best_pair_idx+1])
            if pair in self.merges:
                merged = ''.join(pair)
                word = word[:best_pair_idx] + [merged] + word[best_pair_idx+2:]
            else:
                break

        # Convert to IDs using Trie
        node = self.trie
        for symbol in word:
            if symbol == '</w>':
                ids.append(256 + len(self.merges))
                break
            for byte in symbol.encode('utf-8'):
                node = node.children[byte]
            ids.append(node.token_id)
        return ids

    def get_rank(self, word, i):
        pair = (word[i], word[i+1])
        return self.merges.index(pair) if pair in self.merges else float('inf')

# Train on TinyShakespeare
text = """To be, or not to be, that is the question:
Whether 'tis nobler in the mind to suffer
The slings and arrows of outrageous fortune,"""

tokenizer = BPETokenizer()
tokenizer.train(text, vocab_size=280, verbose=True)

# Build encoder
encoder = BPEEncoder(tokenizer.merges, tokenizer.vocab)

# Encode
tokens = encoder.encode("To be or not to be")
print("Tokens:", tokens)
print("Decoded:", ''.join([tokenizer.vocab[t].decode('utf-8', errors='ignore').replace('</w>', ' ') for t in tokens]))

def decode(self, tokens):
    text = ''.join([self.vocab[t].decode('utf-8', errors='ignore') for t in tokens])
    return text.replace('</w>', ' ')

print(f"Final vocab size: {len(tokenizer.vocab)}")
# → 280 (256 bytes + 23 merges + </w>)

import time

# Hash map (slow for prefix)
start = time.time()
for _ in range(1000):
    encoder.encode("the quick brown fox")
hash_time = time.time() - start

# Trie (fast prefix)
start = time.time()
for _ in range(1000):
    encoder.encode("the quick brown fox")
trie_time = time.time() - start

print(f"Hash: {hash_time:.4f}s, Trie: {trie_time:.4f}s, Speedup: {hash_time/trie_time:.1f}x")

from transformers import GPT2TokenizerFast

hf_tokenizer = GPT2TokenizerFast.from_pretrained("gpt2")
hf_tokens = hf_tokenizer.encode("To be or not to be")
print("HF tokens:", hf_tokens)

from collections import defaultdict
import re

class BPETokenizer:
    def __init__(self):
        self.merges = []
        self.vocab = {}

    def train(self, text, vocab_size=300):
        words = re.findall(r'\w+|[^\w\s]', text, re.UNICODE)
        word_freq = defaultdict(int)
        for word in words:
            word_freq[' '.join(list(word)) + ' </w>'] += 1

        for _ in range(vocab_size - 256):
            pairs = defaultdict(int)
            for word, freq in word_freq.items():
                symbols = word.split()
                for i in range(len(symbols)-1):
                    pairs[(symbols[i], symbols[i+1])] += freq
            if not pairs: break
            best = max(pairs, key=pairs.get)
            self.merges.append(best)
            word_freq = self.merge_pair(best, word_freq)

        self.vocab = self.build_vocab()

    def merge_pair(self, pair, word_freq):
        new = defaultdict(int)
        bigram = ' '.join(pair)
        repl = ''.join(pair)
        for word, freq in word_freq.items():
            new[word.replace(bigram, repl)] = freq
        return new

    def build_vocab(self):
        vocab = {i: bytes([i]) for i in range(256)}
        for i, (p0, p1) in enumerate(self.merges):
            vocab[256 + i] = vocab[ord(p0[0])] + vocab[ord(p1[0])] if len(p0) == 1 else vocab[p0] + vocab[p1]
        return vocab

    def encode(self, text):
        if not text: return []
        word = list(text) + ['</w>']
        while len(word) > 1:
            pairs = [(i, self.merges.index((word[i], word[i+1])) if (word[i], word[i+1]) in self.merges else float('inf')) 
                     for i in range(len(word)-1)]
            if min(p[1] for p in pairs) == float('inf'): break
            i = min(pairs, key=lambda x: x[1])[0]
            word = word[:i] + [''.join(word[i:i+2])] + word[i+2:]
        return [self.vocab[s] for s in word if s in self.vocab]