从零实现 BPE Tokenizer

上一节我们知道，子词级 Tokenizer 在字符级和词级之间取得了最好的平衡——常见词整体保留，罕见词拆成已知片段。但具体按什么规则来切、词表是怎样从无到有构建出来的，还没有展开。

这一节，我们直接训练一个 BPE tokenizer，观察它的编码和解码效果，再和 GPT-2 的真实 tokenizer 对比。BPE 算法的逐步推导放在章末附录，读完正文如果对内部细节感兴趣，可以翻到后面细看。

BPE（Byte Pair Encoding）的核心操作只有两步：统计语料中哪些相邻字符对出现最频繁，然后把最频繁的那对合并成一个新的子词单元。反复执行这一过程，词表就从单个字符逐步扩展为更长的子词。

下面直接在 10 条英文句子上训练一个 BPE tokenizer，看看它能把文本切成什么样。

1. BPE 快速体验

class BPETokenizer:
    """
    BPE Tokenizer 完整实现
    
    三个核心功能：
    1. train()  — 从语料学习 merge rules
    2. encode() — 文本 → token ID 列表
    3. decode() — token ID 列表 → 文本
    """
    
    def __init__(self):
        # merge_rules: 按顺序记录每次合并的 pair
        # 这是 BPE 最核心的数据结构，encode 时按这个顺序贪心应用
        self.merge_rules = []
        # 最终词表：初始字符 + 每一步 merge 学到的新 token
        self.vocab = set()
        self.stoi = {}
        self.itos = {}
    
    def train(self, texts, num_merges=15, verbose=True):
        """
        BPE 训练
        
        参数:
            texts: 语料列表
            num_merges: 合并次数
            verbose: 是否打印每一步
        """
        # Step 0: 初始化为字符级
        token_lists = [list(text) for text in texts]
        
        # 收集语料中所有不重复的字符，作为初始词表
        base_vocab = set()
        for tokens in token_lists:
            for c in tokens:
                base_vocab.add(c)
        learned_vocab = set(base_vocab)
        
        if verbose:
            print(f"{'='*60}")
            print(f"BPE 训练开始！初始状态: 每条句子按字符拆分")
            print(f"{'='*60}")
            print(f"初始字符集大小: {len(base_vocab)}")
            print()
        
        for step in range(num_merges):
            # Step 1: 统计所有 pair 的频率
            pairs = {}
            for tokens in token_lists:
                for i in range(len(tokens) - 1):
                    pair = (tokens[i], tokens[i + 1])
                    if pair not in pairs:
                        pairs[pair] = 0
                    pairs[pair] += 1
            
            if not pairs:
                break
            
            # Step 2: 找最高频 pair
            best_pair = max(pairs, key=pairs.get)
            best_count = pairs[best_pair]
            
            # Step 3: 记录 merge rule
            self.merge_rules.append(best_pair)
            
            # Step 4: 合并
            a, b = best_pair
            new_token = a + b
            
            new_token_lists = []
            for tokens in token_lists:
                new_tokens = []
                i = 0
                while i < len(tokens):
                    if i < len(tokens) - 1 and tokens[i] == a and tokens[i + 1] == b:
                        new_tokens.append(new_token)
                        i += 2
                    else:
                        new_tokens.append(tokens[i])
                        i += 1
                new_token_lists.append(new_tokens)
            
            token_lists = new_token_lists
            
            learned_vocab.add(new_token)
            
            if verbose:
                print(f"Step {step+1:2d}: merge {best_pair} → '{new_token}'  (出现 {best_count} 次) | 当前词表大小: {len(learned_vocab)}")
        
        # 建立最终词表
        # 注意：词表不能只保留最终语料里还出现的 token。
        # encode 遇到没见过的组合时，需要能退回到初始字符。
        self.vocab = learned_vocab
        sorted_vocab = sorted(list(self.vocab))
        self.stoi = {t: i for i, t in enumerate(sorted_vocab)}
        self.itos = {i: t for i, t in enumerate(sorted_vocab)}
        
        if verbose:
            print(f"\n{'='*60}")
            print(f"训练完成！")
            print(f"  - 合并次数: {len(self.merge_rules)}")
            print(f"  - 最终词表大小: {len(self.vocab)} 个 token")
            print(f"  - Merge rules: {self.merge_rules}")
            print(f"{'='*60}")
        
        return token_lists

# 实验语料
corpus = [
    "the cat sat on the mat",
    "the dog sat on the log",
    "the cat and the dog",
    "i love my cat",
    "i love my dog",
    "the cat is cute",
    "the dog is happy",
    "the mat is soft",
    "the log is hard",
    "cats and dogs are friends",
]

# 训练 BPE tokenizer（不打印每一步）
bpe = BPETokenizer()
final_tokens = bpe.train(corpus, num_merges=15, verbose=False)

print(f"训练完成！")
print(f"  初始字符数: {len(set(c for text in corpus for c in text))}")
print(f"  合并次数:   {len(bpe.merge_rules)}")
print(f"  最终词表:   {len(bpe.vocab)} 个 token")
print()
print("学到的 merge rules（前 8 条）:")
for i, (a, b) in enumerate(bpe.merge_rules[:8]):
    print(f"  {i+1}. '{a}' + '{b}' → '{a+b}'")

编码与解码

训练得到 merge rules 后，encode 就是按规则顺序把文本逐步合并成 token 序列，decode 则是把 token 拼接回原文。

# 给 BPETokenizer 加上 encode 方法
def bpe_encode(self, text):
    """
    BPE 编码：文本 → token ID 列表
    
    核心逻辑：按训练时的 merge rules 顺序，贪心地合并
    """
    # Step 1: 拆成字符
    tokens = list(text)
    
    # Step 2: 依次应用每条 merge rule
    for (a, b) in self.merge_rules:
        new_tokens = []
        i = 0
        while i < len(tokens):
            if i < len(tokens) - 1 and tokens[i] == a and tokens[i + 1] == b:
                new_tokens.append(a + b)
                i += 2
            else:
                new_tokens.append(tokens[i])
                i += 1
        tokens = new_tokens
    
    # Step 3: 每个 token 去词表查 ID。
    # 如果找不到，说明输入里有训练时没见过的字符；不能静默跳过。
    ids = []
    for token in tokens:
        if token not in self.stoi:
            raise KeyError(token)
        ids.append(self.stoi[token])
    return ids

# 把方法挂上去
BPETokenizer.encode = bpe_encode

print("encode 方法已添加！")

encode 方法已添加！

# 测试 encode
text = "the cat"
ids = bpe.encode(text)
print(f"原文: '{text}'")
print(f"Token IDs: {ids}")
print(f"Token 数量: {len(ids)}")
print(f"逐个解释:")
for i, tid in enumerate(ids):
    print(f"  ID {tid} → '{bpe.itos[tid]}'")
print(f"原文字符数 = {len(text)}，BPE token 数 = {len(ids)}，压缩比 = {len(text)/len(ids):.1f}x")

print()

# 解码：把 token ID 拼回文本
def bpe_decode(self, ids):
    """BPE 解码：token ID 列表 → 文本"""
    return "".join([self.itos[i] for i in ids])

BPETokenizer.decode = bpe_decode

# 测试完整编解码
for test_text in ["the cat", "my dog is happy", "i love cats"]:
    ids = bpe.encode(test_text)
    recovered = bpe.decode(ids)
    status = "OK" if test_text == recovered else "FAIL"
    print(f"[{status}] '{test_text}' → {ids} → '{recovered}'")

为什么 BPE 不怕大多数生词

BPE 的 encode 过程从字符开始，按 merge rules 逐步合并。这里有一个关键推论：只要输入文本中的每个字符都在初始词表里，就不会出现未知 token。

举个例子。假设训练语料里见过 "play" 和 "ing"，但没见过 "playing"。encode 处理 "playing" 时，会先把文本拆成字符 ['p','l','a','y','i','n','g']，然后逐条应用 merge rules。如果 rules 里有 ('p','l')→'pl'、('a','y')→'ay' 等合并，最终可能得到 ['play', 'ing']。即使 "playing" 从没作为整体出现过，它也能被拆成两个已知子词。

这个特性来自 encode 的设计：它不是重新统计频率再合并，而是严格按训练时学到的规则照做。每条 merge rule 的两端——合并前的两个 token 和合并后的新 token——都在词表里，所以合并产物一定查得到 ID。回头看 encode 的最后一步：

# Step 3: 每个 token 去词表查 ID
ids = []
for token in tokens:
    if token not in self.stoi:
        raise KeyError(token)
    ids.append(self.stoi[token])

这里没有"把未知 token 拆回字符"的兜底逻辑。不是偷懒，而是不需要：encode 从字符出发，只做合并不做拆分，所以只要字符在词表里，最终得到的 token 就一定在词表里。

不过要注意前提条件：输入文本中的所有字符都必须在训练语料中出现过。如果遇到训练时从没见过的字符——比如数字 3、换行符、或者 emoji 👽——查表时就会直接报错。正确做法就是明确报错，而不是把未知字符静默丢掉。

这也是为什么工业级 tokenizer 通常不从字符开始，而是采用 Byte-Level BPE（字节级 BPE）。256 个基础 byte 可以组合出世界上任何文字与符号，从表示层面避免了 OOV（Out-Of-Vocabulary）问题。同样是面对从未见过的 👽，Byte-Level BPE 不会将其视为无法识别的新字符，而是先转化为 UTF-8 编码下的 4 个字节：[240, 159, 145, 189]。哪怕系统从未学过要把它们合并成外星人 emoji，查表时依然能在 0-255 的基础词表中稳稳查到这 4 个独立字节的 ID。

# 演示：编码一个语料中不存在的句子
unseen = "a cat runs fast"

# 先验证：这个句子确实不在训练语料中
print(f"测试句子: '{unseen}'")
in_corpus = any(unseen == s for s in corpus)
print(f"是否出现在训练语料中: {in_corpus}")

# 但它的所有字符都在词表里
unseen_chars = set(unseen)
vocab_chars = bpe.vocab
missing = [c for c in unseen_chars if c not in vocab_chars]
print(f"句子中的字符: {sorted(unseen_chars)}")
print(f"不在词表中的字符: {missing if missing else '无'}")
print()

ids = bpe.encode(unseen)
recovered = bpe.decode(ids)

print(f"Token IDs: {ids}")
print(f"解码回来: '{recovered}'")
print(f"状态: {'OK' if unseen == recovered else 'FAIL'}")

# 看看 BPE 把它拆成了什么
print(f"\n逐个 token:")
for tid in ids:
    print(f"  '{bpe.itos[tid]}'", end="")
print()

2. 对比 GPT-2 的真实 Tokenizer

# 加载真实 GPT-2 tokenizer（byte-level BPE）
try:
    import tiktoken

    real_tokenizer_name = "gpt2"
    real_tokenizer = tiktoken.get_encoding(real_tokenizer_name)
    print(f"真实 tokenizer: {real_tokenizer_name}")
    print(f"词表大小: {real_tokenizer.n_vocab}")
except Exception as e:
    real_tokenizer = None
    print("未能加载 tiktoken 的 GPT-2 tokenizer")
    print(f"原因: {e}")
    print("安装并缓存 tiktoken 后，这个 cell 会打印真实 tokenizer 结果。")


def show_real_tokenization(text):
    """打印真实 tokenizer 如何把文本切成 token 和 ID"""
    ids = real_tokenizer.encode(text)
    tokens = [real_tokenizer.decode([tok_id]) for tok_id in ids]

    print(f"文本: {text!r}")
    print(f"token 数: {len(ids)}")
    for i, (tok_id, token) in enumerate(zip(ids, tokens)):
        visible = token.replace("\n", "\\n").replace("\t", "\\t")
        token_bytes = list(real_tokenizer.decode_single_token_bytes(tok_id))
        print(f"  {i:02d} | id={tok_id:<6} | token={visible!r} | bytes={token_bytes}")
    return ids, tokens


if real_tokenizer is not None:
    show_real_tokenization("the cat sat on the mat")

真实 tokenizer: gpt2
词表大小: 50257
文本: 'the cat sat on the mat'
token 数: 6
  00 | id=1169   | token='the' | bytes=[116, 104, 101]
  01 | id=3797   | token=' cat' | bytes=[32, 99, 97, 116]
  02 | id=3332   | token=' sat' | bytes=[32, 115, 97, 116]
  03 | id=319    | token=' on' | bytes=[32, 111, 110]
  04 | id=262    | token=' the' | bytes=[32, 116, 104, 101]
  05 | id=2603   | token=' mat' | bytes=[32, 109, 97, 116]

def try_mini_bpe(text):
    """用我们的 mini BPE 编码；失败时返回错误原因"""
    try:
        ids = bpe.encode(text)
        tokens = [bpe.itos[i] for i in ids]
        return ids, tokens, None
    except KeyError as e:
        return None, None, e.args[0]


compare_texts = [
    "the cat sat on the mat",
    " the cat",
    "the  cat",
    "327 + 1 = 328",
    "def f():\n    return x",
    "你好，世界🙂",
]

if real_tokenizer is not None:
    for text in compare_texts:
        print("=" * 68)
        print(f"文本: {text!r}")

        mini_ids, mini_tokens, error = try_mini_bpe(text)
        if error is None:
            print(f"mini BPE: {len(mini_ids)} tokens")
            print(f"  tokens: {mini_tokens}")
            print(f"  ids:    {mini_ids}")
        else:
            print("mini BPE: 无法编码")
            print(f"  原因: 小语料词表里没有字符 {error!r}")

        real_ids = real_tokenizer.encode(text)
        real_tokens = [real_tokenizer.decode([tok_id]) for tok_id in real_ids]
        real_tokens = [t.replace("\n", "\\n") for t in real_tokens]
        print(f"真实 GPT-2 BPE: {len(real_ids)} tokens")
        print(f"  tokens: {real_tokens}")
        print(f"  ids:    {real_ids}")

    print("=" * 68)
    print("关键观察：真实 tokenizer 不只是更大，还处理了 bytes、空格、换行和 Unicode。")
    print("我们的 mini BPE 用来理解 merge rules；工业版解决覆盖率、速度和边界情况。")

====================================================================
文本: 'the cat sat on the mat'
mini BPE: 6 tokens
  tokens: ['the cat ', 'sat o', 'n', ' the ', 'm', 'at']
  ids:    [31, 26, 17, 1, 16, 3]
真实 GPT-2 BPE: 6 tokens
  tokens: ['the', ' cat', ' sat', ' on', ' the', ' mat']
  ids:    [1169, 3797, 3332, 319, 262, 2603]
====================================================================
文本: ' the cat'
mini BPE: 3 tokens
  tokens: [' ', 'the c', 'at']
  ids:    [0, 30, 3]
真实 GPT-2 BPE: 2 tokens
  tokens: [' the', ' cat']
  ids:    [262, 3797]
====================================================================
文本: 'the  cat'
mini BPE: 4 tokens
  tokens: ['the ', ' ', 'c', 'at']
  ids:    [29, 0, 5, 3]
真实 GPT-2 BPE: 3 tokens
  tokens: ['the', ' ', ' cat']
  ids:    [1169, 220, 3797]
====================================================================
文本: '327 + 1 = 328'
mini BPE: 无法编码
  原因: 小语料词表里没有字符 '3'
真实 GPT-2 BPE: 5 tokens
  tokens: ['327', ' +', ' 1', ' =', ' 328']
  ids:    [34159, 1343, 352, 796, 39093]
====================================================================
文本: 'def f():\n    return x'
mini BPE: 无法编码
  原因: 小语料词表里没有字符 '('
真实 GPT-2 BPE: 9 tokens
  tokens: ['def', ' f', '():', '\\n', ' ', ' ', ' ', ' return', ' x']
  ids:    [4299, 277, 33529, 198, 220, 220, 220, 1441, 2124]
====================================================================
文本: '你好，世界🙂'
mini BPE: 无法编码
  原因: 小语料词表里没有字符 '你'
真实 GPT-2 BPE: 13 tokens
  tokens: ['�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '�', '��']
  ids:    [19526, 254, 25001, 121, 171, 120, 234, 10310, 244, 45911, 234, 8582, 25081]
====================================================================
关键观察：真实 tokenizer 不只是更大，还处理了 bytes、空格、换行和 Unicode。
我们的 mini BPE 用来理解 merge rules；工业版解决覆盖率、速度和边界情况。

数字、空格、缩进和中文

真实 tokenizer 的很多"怪现象"，都和训练语料及工程处理有关。这些细节直接影响模型做数学、写代码、处理中英文混合时的表现。

special_cases = [
    ("数字", "327 + 1 = 328"),
    ("词首空格", "cat"),
    ("同一个词，前面带空格", " cat"),
    ("多个空格", "the    cat"),
    ("换行和缩进", "def f():\n    return x"),
    ("中文和 emoji", "你好，世界🙂"),
]

if real_tokenizer is not None:
    for label, text in special_cases:
        print("=" * 68)
        print(f"特殊情况: {label}")
        show_real_tokenization(text)

    print("=" * 68)
    print("Special token: <|endoftext|>")
    text = "hello<|endoftext|>world"

    try:
        real_tokenizer.encode(text)
    except ValueError as e:
        print("默认 encode 会拒绝把 special token 当普通文本吞掉。")
        print(f"错误摘要: {str(e).splitlines()[0]}")

    ids = real_tokenizer.encode(text, allowed_special={"<|endoftext|>"})
    tokens = [real_tokenizer.decode([tok_id]) for tok_id in ids]
    print("允许 special token 后:")
    print(f"  ids:    {ids}")
    print(f"  tokens: {tokens}")
    print("关键：special token 是额外控制符，不是普通 merge rule 自己学出来的。")

====================================================================
特殊情况: 数字
文本: '327 + 1 = 328'
token 数: 5
  00 | id=34159  | token='327' | bytes=[51, 50, 55]
  01 | id=1343   | token=' +' | bytes=[32, 43]
  02 | id=352    | token=' 1' | bytes=[32, 49]
  03 | id=796    | token=' =' | bytes=[32, 61]
  04 | id=39093  | token=' 328' | bytes=[32, 51, 50, 56]
====================================================================
特殊情况: 词首空格
文本: 'cat'
token 数: 1
  00 | id=9246   | token='cat' | bytes=[99, 97, 116]
====================================================================
特殊情况: 同一个词，前面带空格
文本: ' cat'
token 数: 1
  00 | id=3797   | token=' cat' | bytes=[32, 99, 97, 116]
====================================================================
特殊情况: 多个空格
文本: 'the    cat'
token 数: 5
  00 | id=1169   | token='the' | bytes=[116, 104, 101]
  01 | id=220    | token=' ' | bytes=[32]
  02 | id=220    | token=' ' | bytes=[32]
  03 | id=220    | token=' ' | bytes=[32]
  04 | id=3797   | token=' cat' | bytes=[32, 99, 97, 116]
====================================================================
特殊情况: 换行和缩进
文本: 'def f():\n    return x'
token 数: 9
  00 | id=4299   | token='def' | bytes=[100, 101, 102]
  01 | id=277    | token=' f' | bytes=[32, 102]
  02 | id=33529  | token='():' | bytes=[40, 41, 58]
  03 | id=198    | token='\\n' | bytes=[10]
  04 | id=220    | token=' ' | bytes=[32]
  05 | id=220    | token=' ' | bytes=[32]
  06 | id=220    | token=' ' | bytes=[32]
  07 | id=1441   | token=' return' | bytes=[32, 114, 101, 116, 117, 114, 110]
  08 | id=2124   | token=' x' | bytes=[32, 120]
====================================================================
特殊情况: 中文和 emoji
文本: '你好，世界🙂'
token 数: 13
  00 | id=19526  | token='�' | bytes=[228, 189]
  01 | id=254    | token='�' | bytes=[160]
  02 | id=25001  | token='�' | bytes=[229, 165]
  03 | id=121    | token='�' | bytes=[189]
  04 | id=171    | token='�' | bytes=[239]
  05 | id=120    | token='�' | bytes=[188]
  06 | id=234    | token='�' | bytes=[140]
  07 | id=10310  | token='�' | bytes=[228, 184]
  08 | id=244    | token='�' | bytes=[150]
  09 | id=45911  | token='�' | bytes=[231, 149]
  10 | id=234    | token='�' | bytes=[140]
  11 | id=8582   | token='�' | bytes=[240, 159]
  12 | id=25081  | token='��' | bytes=[153, 130]
====================================================================
Special token: <|endoftext|>
默认 encode 会拒绝把 special token 当普通文本吞掉。
错误摘要: Encountered text corresponding to disallowed special token '<|endoftext|>'.
允许 special token 后:
  ids:    [31373, 50256, 6894]
  tokens: ['hello', '<|endoftext|>', 'world']
关键：special token 是额外控制符，不是普通 merge rule 自己学出来的。

趣味问题：为什么模型有时会觉得 1.11 比 1.9 大

先别急着看答案，自己先猜一下：

1.11 和 1.9，谁更大？

数学上当然是 1.9 更大。但 LLM 不会一上来就把 1.11 当成"小数对象"。它最先看到的是 tokenizer 切出来的 token ID。如果切法长这样：

"1.11" → ["1", ".", "11"]
"1.9"  → ["1", ".", "9"]

模型可能会被表面模式带偏：11 看起来比 9 大，于是误以为 1.11 > 1.9。这不是说模型完全不会做小数比较，而是说：它要先从 token 序列里学会"小数位对齐"这个规则。

# 趣味观察：真实 tokenizer 怎么切 1.11 和 1.9
number_texts = ["1.11", "1.9"]

if real_tokenizer is not None:
    for text in number_texts:
        ids = real_tokenizer.encode(text)
        tokens = [real_tokenizer.decode([tok_id]) for tok_id in ids]
        print(f"{text!r} -> tokens={tokens}, ids={ids}")

    print()
    print("数学比较：")
    print(f"  1.11 > 1.9  ? {1.11 > 1.9}")
    print(f"  1.90 > 1.11 ? {1.90 > 1.11}")
    print()
    print("关键观察：模型看到的不是 float，而是 token 序列。")
    print("要比较小数，它必须学会把小数位补齐，而不是直接比较 token '11' 和 '9'。")

'1.11' -> tokens=['1', '.', '11'], ids=[16, 13, 1157]
'1.9' -> tokens=['1', '.', '9'], ids=[16, 13, 24]

数学比较：
  1.11 > 1.9  ? False
  1.90 > 1.11 ? True

关键观察：模型看到的不是 float，而是 token 序列。
要比较小数，它必须学会把小数位补齐，而不是直接比较 token '11' 和 '9'。

3. 工业级 BPE 的关键设计

词表大小的影响

merge 次数越多，词表越大，token 越"整"。但这不是越大越好——词表太小，序列会很长；词表太大，很多 token 很少出现，学习也不划算。用同一个句子，在不同 merge 次数下看看切分结果：

# 用不同 merge 次数训练多个 tokenizer
for n_merges in [5, 15, 30]:
    t = BPETokenizer()
    t.train(corpus, num_merges=n_merges, verbose=False)
    
    test = "the cat sat on the mat"
    ids = t.encode(test)
    
    print(f"merge={n_merges:2d} | 词表={len(t.vocab):2d} | token数={len(ids):2d} | tokens: {[t.itos[i] for i in ids]}")

print()
print("观察：merge 次数越多，常见片段越可能作为整体保留，token 数越少。")

merge= 5 | 词表=25 | token数=13 | tokens: ['the ', 'c', 'at', ' ', 's', 'at', ' ', 'o', 'n', ' ', 'the ', 'm', 'at']
merge=15 | 词表=35 | token数= 6 | tokens: ['the cat ', 'sat o', 'n', ' the ', 'm', 'at']
merge=30 | 词表=50 | token数= 4 | tokens: ['the cat ', 'sat on the ', 'm', 'at']

观察：merge 次数越多，常见片段越可能作为整体保留，token 数越少。

Pre-tokenization：先切词，再做 BPE

我们的 mini BPE 把整句话连在一起统计 pair。结果就是 BPE 可能会跨词合并——比如 e 和空格先合并成 e ，把一个词的结尾和空格粘在一起。GPT-2 的做法是：先用正则把文本切分成独立片段（大致是"单词"级别），然后对每个片段分别做 BPE。这样合并发生在 pre-tokenizer 切出的片段内部，不会跨这些片段继续合并。注意 GPT-2 byte-level BPE 的 token 里常带有前导空格，所以“词边界”不是肉眼看到的空格那么简单。

import re

# GPT-2 的 pre-tokenization 正则
# 把文本按"单词 + 缩写 + 标点 + 数字"切分成独立片段
gpt2_pattern = re.compile(
    r"""'s|'t|'re|'ve|'m|'ll|'d| ?\w+| ?\d+| ?[^\s\w]+|\s+(?!\S)|\s+"""
)

text = "Hello, I'm learning BPE! It's really cool."

chunks = gpt2_pattern.findall(text)

print(f"原文: '{text}'")
print(f"Pre-tokenization 结果:")
for i, chunk in enumerate(chunks):
    print(f"  [{i}] '{chunk}'")

print()
print("关键观察：每个片段要么是一个单词（可能带前导空格），要么是标点，要么是缩写。")
print("BPE 只在每个片段内部统计和合并，不会跨片段。")
print()
print("对比我们的 mini 版:")
print("  mini 版: 'the cat' → ['t','h','e',' ','c','a','t']  ← 空格是普通字符，可以跨词合并")
print("  工业版: 'the cat' → ['the', ' cat']                  ← 先切词，BPE 在词内操作")

Byte 级起点

字符级起点看起来已经很稳了，但 Unicode 世界太大。比如"你"用 UTF-8 存储时其实是 3 个 byte：E4 BD A0；"😊"是 4 个 byte：F0 9F 98 8A。如果 tokenizer 从字符开始，它需要提前认识各种中文、emoji、特殊符号。但如果从 byte 开始，起点永远只有 256 种可能，无论输入什么文本，至少都能先拆成 bytes，不会直接 OOV。

	我们的版本	工业版
起点	从字符开始	从 bytes 开始，能覆盖所有 Unicode
空格	空格当普通字符	专门处理词首空格、换行、缩进
统计	全量统计频率	用更高效的数据结构加速
语料	小语料	海量语料

核心思想没有变：统计 pair → 合并最高频 → 重复 → 得到有序 merge rules。

Special Tokens

BPE 从语料里学出来的 token 是一类——the、ing、tion——因为经常出现，所以被合并出来。词表里还有另一类 token，不是从统计 pair 来的，而是训练 tokenizer 时手动加入的。这类 token 称为 special tokens。

token 字符串	功能名	含义
<unk>	Unknown	遇到无法表示的字符时，用它占位
<s>	BOS（Beginning of Sequence）	标记一段输入序列的开始
</s>	EOS（End of Sequence）	标记一段输入序列的结束

LLaMA / LLaMA 2 使用上面三种。现代 chat 模型需要更细粒度的控制——Qwen 用 <|im_start|> / <|im_end|> 标记每轮消息边界，LLaMA 3 用 <|begin_of_text|> / <|eot_id|> 区分整篇文本和单轮对话。

Special token 加入词表只是让它拥有固定 ID。真正把它们放进样本开头和结尾，通常由数据处理代码或 chat template 完成，tokenizer 在 encode 时不会自动插入。

4. 训练真实 Tokenizer

# 准备训练语料
# 用 Tiny Shakespeare 语料（公共领域，约 1MB 纯文本）
import urllib.request

url = "https://raw.githubusercontent.com/karpathy/char-rnn/master/data/tinyshakespeare/input.txt"
print("正在下载 Tiny Shakespeare 语料...")
raw_text = urllib.request.urlopen(url).read().decode("utf-8")
train_lines = [line for line in raw_text.split("\n") if line.strip()]

# 语料基本统计
total_chars = len(raw_text)
unique_chars = len(set(raw_text))
avg_line_len = total_chars // len(train_lines)

print(f"下载完成。语料统计:")
print(f"  总行数:       {len(train_lines):,}")
print(f"  总字符数:     {total_chars:,}")
print(f"  不重复字符:   {unique_chars}")
print(f"  平均行长:     {avg_line_len} 字符")
print()
print(f"前 5 行:")
for i, line in enumerate(train_lines[:5]):
    print(f"  [{i}] {line}")

配置并训练

训练真实 tokenizer 时，要同时决定词表大小、pre-tokenizer、special tokens，以及遇到未知字符时用什么策略。下面用 tokenizers 库训练一个词表大小为 4000 的 BPE tokenizer。

# 配置参数并训练
from tokenizers import Tokenizer
from tokenizers.models import BPE
from tokenizers.trainers import BpeTrainer
from tokenizers.pre_tokenizers import Whitespace

VOCAB_SIZE = 4000

my_tokenizer = Tokenizer(BPE(unk_token="<unk>"))
my_tokenizer.pre_tokenizer = Whitespace()

trainer = BpeTrainer(
    vocab_size=VOCAB_SIZE,
    special_tokens=["<unk>", "<s>", "</s>"],
    show_progress=True,
)

print(f"训练配置: 词表={VOCAB_SIZE}, pre-tokenizer=Whitespace, special_tokens=['<unk>','<s>','</s>']")
print("开始训练...")
my_tokenizer.train_from_iterator(train_lines, trainer=trainer)
print(f"训练完成! 词表大小: {my_tokenizer.get_vocab_size()} 个 token")

# 演示 special token 不会自动插入
sample_text = "To be, or not to be"
plain = my_tokenizer.encode(sample_text)
bos_id = my_tokenizer.token_to_id("<s>")
eos_id = my_tokenizer.token_to_id("</s>")
print(f"\n原文: {sample_text!r}")
print(f"普通 encode: {plain.tokens}")
print(f"包装 BOS/EOS: {['<s>'] + plain.tokens + ['</s>']}")
print(f"关键: <s> 和 </s> 已有固定 ID，但 encode 不会自动加它们")

检查 tokenizer 学到了什么

训练完成后，不要只看一个词表大小数字。我们还要看 token 长度分布、单字符覆盖、常见子词和长 token。

# 检查 tokenizer 学到了什么
vocab = my_tokenizer.get_vocab()

# token 长度分布
length_dist = {}
for token in vocab:
    length = len(token)
    if length not in length_dist:
        length_dist[length] = 0
    length_dist[length] += 1

print("=== 词表中的 token 长度分布 ===")
for length in sorted(length_dist):
    bar = "#" * (length_dist[length] // 5)
    print(f"  长度 {length:2d}: {length_dist[length]:>4} 个  {bar}")

# 较长的 token
long_tokens = sorted([t for t in vocab if len(t) >= 5], key=len, reverse=True)
print(f"\n长度 >= 5 的 token（共 {len(long_tokens)} 个，展示前 15 个）:")
for t in long_tokens[:15]:
    print(f"  '{t}' (id={vocab[t]})")

怎么判断一个 tokenizer 好不好

训练完 tokenizer 后，需要从几个角度检查质量：

1. 压缩比：平均每个 token 覆盖几个字符。压缩比越高，序列越短。GPT-2 在英文上约 3.5 字符/token，中文只有 1.5 左右。
2. 解码一致性：encode 之后再 decode，希望能恢复原文。如果已经用了 <unk>，原始字符丢失，无法恢复。
3. 覆盖率：遇到训练时没见过的文本，不应该直接报错。byte 级 tokenizer 覆盖率最高，256 个 byte 能表示任何 Unicode 文本。
4. token 语义质量：切出来的 token 应该是合理的语言单元。"the" 整体保留比切成 "th" + "e" 好。

# 用四个标准逐一检验我们的 tokenizer

# ---- 指标 1 & 4：压缩比 + token 语义质量 ----
# 对同一个句子，看 token 切得是否合理、压缩比是多少
test_cases = [
    "To be, or not to be, that is the question",
    "The king is dead",
    "Hello world",
    "327 + 1 = 328",
    "xyz",  # 训练语料中没出现过的词
]

print("=== 1. 压缩比 & token 质量 ===")
print("好的 tokenizer：常见词整体保留，生词拆成已知子词，不跨词边界")
print()

for text in test_cases:
    encoding = my_tokenizer.encode(text)
    ratio = len(text) / len(encoding.ids) if len(encoding.ids) > 0 else 0
    print(f"'{text}'")
    print(f"  {len(encoding.ids)} tokens, 压缩比 {ratio:.1f}x")
    print(f"  {encoding.tokens}")
    print()

# ---- 指标 2：解码一致性 ----
print("=== 2. 解码一致性 ===")
print("encode → decode 通常希望恢复原文；如果有 <unk>，信息已经丢失，就恢复不了。")
print("另外，不同 pre-tokenizer / decoder 组合也会影响空格和标点的还原。")
print()
for text in test_cases:
    encoding = my_tokenizer.encode(text)
    decoded = my_tokenizer.decode(encoding.ids)
    ok = "OK" if decoded == text else "FAIL"
    print(f"  [{ok}] '{text}' -> '{decoded}'")

# ---- 指标 3：覆盖率 ----
print()
print("=== 3. 覆盖率 ===")
print("遇到语料中没见过的字符时，字符级 tokenizer 会用 <unk> 替代。")
print("byte 级 tokenizer（如 GPT-2）不会遇到这个问题。")
coverage_tests = ["Hello world", "xyz", "中文"]
for text in coverage_tests:
    encoding = my_tokenizer.encode(text)
    has_unk = "<unk>" in encoding.tokens
    status = "有 <unk>（字符不在训练语料中）" if has_unk else "全部 token 都在词表中"
    print(f"  '{text}' → {status}")

# ---- 整体压缩效果 ----
print()
print("=== 整体压缩效果 ===")
# 取前 10000 字符做一个简单抽样统计，真实项目会在 held-out 验证集上测
sample = raw_text[:10000]
enc = my_tokenizer.encode(sample)
ratio = len(sample) / len(enc.ids)
print(f"  前 10000 字符: {len(enc.ids):,} tokens, 压缩比 {ratio:.2f}x")
print(f"  解码一致性: {'OK' if my_tokenizer.decode(enc.ids) == sample else 'FAIL'}")
print()
print(f"对比参考：GPT-2 在英文上的压缩比大约 3.5x")
print(f"我们的 tokenizer 在 Tiny Shakespeare 上拿到 {ratio:.1f}x，")
print(f"差距主要来自词表大小（4000 vs 50257）和缺少 byte 级起点")

词表大小如何影响压缩效果

最后再把 vocab_size 单独拎出来看：词表变大时，常见片段会被合并得更完整，但收益不会一直线性增长。

还要注意：vocab_size 通常是目标值或上限，不是数学保证。如果语料太小、可合并 pair 不够，最终词表可能更小；如果初始 alphabet 和 special tokens 已经超过它，最终词表也不会被硬裁到更小。

# 第五步：对比不同词表大小对压缩效果的影响
# 用同一句话，在不同词表大小下训练并测试

test_text = "To be, or not to be, that is the question"

print(f"对比文本: '{test_text}'")
print(f"原文字符数: {len(test_text)}")
print()
print(f"{'词表大小':>8} | {'token 数':>8} | {'压缩比':>6} | 切分结果")
print("-" * 72)

for vs in [500, 1000, 2000, 4000]:
    t = Tokenizer(BPE(unk_token="<unk>"))
    t.pre_tokenizer = Whitespace()
    trainer = BpeTrainer(
        vocab_size=vs,
        special_tokens=["<unk>", "<s>", "</s>"],
    )
    t.train_from_iterator(train_lines, trainer=trainer)
    
    enc = t.encode(test_text)
    ratio = len(test_text) / len(enc.ids) if len(enc.ids) > 0 else 0
    actual = t.get_vocab_size()
    
    print(f"{actual:>8} | {len(enc.ids):>8} | {ratio:>5.1f}x | {enc.tokens}")

print()
print("观察：")
print("  - 词表从 500 → 1000，压缩比提升明显（token 数明显减少）")
print("  - 词表从 2000 → 4000，提升变小（常见词已经合并完了，新合并的是低频组合）")
print("  - 现代 LLM 的词表没有统一标准：Mistral 使用约 32K，Llama 3 使用约 128K，Qwen2.5 使用约 151K，Gemma 系列约 256K。词表大小取决于语料语言、byte fallback/special tokens、压缩率和 embedding 成本。参考：[Mistral 7B](https://arxiv.org/abs/2310.06825)、[Llama 3 model card](https://github.com/meta-llama/llama3/blob/main/MODEL_CARD.md)、[Qwen2.5](https://huggingface.co/Qwen/Qwen2.5-7B)、[Gemma tokenizer](https://ai.google.dev/gemma/docs/core/tokenizer)。")

工业界的词表大小

我们的 mini BPE 词表只有 35 个 token。工业界的选择要大得多：

工具/库	代表模型	词表大小	起点
tiktoken	GPT-2	50,257	Bytes
tiktoken	GPT-4 常用 cl100k_base	100,256 mergeable ranks；完整编码还包含 special tokens	Bytes
SentencePiece	LLaMA	32,000	Bytes

词表太小（几千）：序列太长，Self-Attention 计算量跟序列长度的平方成正比。词表太大（几百万）：Embedding 层参数膨胀——词表 × 维度就是 Embedding 矩阵大小。同时很多 token 只出现几次，模型学不好。

现代 LLM 词表大小差异很大，常见范围可以从 32K 到 200K+。更大的词表通常能缩短多语言文本的 token 序列，但也会增加 embedding / lm head 成本；是否值得要看具体语料和模型设计。cl100k_base 的 100,256 指的是 mergeable ranks，不等于包含所有 special tokens 的完整词表。参考：OpenAI tiktoken。

小结

这一节所学的内容：

• BPE 从字符开始，反复执行"统计 pair → 合并最高频 → 记录 rule"的循环
• merge rules 是有顺序的，编码新文本时按顺序重放
• BPE 不怕大多数生词——只要字符已知，新词就可以自然退回到子词或字符
• 工业级 BPE 加了 pre-tokenization（避免跨词合并）和 byte 级起点（覆盖所有 Unicode）
• 词表大小在压缩率和参数量之间权衡，常见 32K 到 200K+，没有统一标准
• Special tokens（BOS / EOS / UNK）不靠 BPE 学出来，是手动加入词表的控制信号
• BPE 算法的逐步推导见章末附录

下一节进入 Embedding——token ID 只是编号，神经网络需要把它变成向量才能计算。

作业

三道题覆盖两类内容：

1. BPE 反复统计相邻 pair，并合并最高频 pair。
2. 真实 tokenizer 常从 bytes 开始，并按有序 merge rules 编码。

关于 AI 辅助：可以让 AI 提示思路、拆解步骤，但不建议直接让 AI 完成题目。BPE 的重点是亲眼看到 token 怎么一步步长出来。

作业 1：统计 pair

BPE 的第一步是统计相邻 token pair 的频率。

小提示：pair 是 (tokens[i], tokens[i + 1])。

# 作业 1：统计相邻 pair 填空

tokens = list("banana")
pair_counts = {}

for i in range(len(tokens) - 1):
    pair = (tokens[i], tokens[i + 1])
    # TODO：把下面三引号里的内容替换成你的代码
    """在这里更新 pair_counts[pair] 的计数"""

assert pair_counts[("a", "n")] == 2, dict(pair_counts)
assert pair_counts[("n", "a")] == 2, dict(pair_counts)
assert pair_counts[("b", "a")] == 1, dict(pair_counts)
print("✅ 作业 1 通过：你记住了 BPE 的第一步是统计相邻 pair")

作业 2：合并 pair

找到高频 pair 后，要把它们合并成一个新 token。

小提示：命中 pair 时，一次消耗两个 token；没命中时，只消耗当前 token。

# 作业 2：合并 pair 填空
def merge_pair(tokens, pair):
    """把 tokens 中等于 pair 的相邻 token 合并成一个新 token"""
    merged = []
    i = 0
    while i < len(tokens):
        # TODO：把下面三引号里的内容替换成你的代码
        """在这里判断是否命中 pair，并更新 merged 和 i"""
    return merged

result = merge_pair(list("banana"), ("a", "n"))

assert result == ["b", "an", "an", "a"], result
print("✅ 作业 2 通过：你记住了 BPE 的核心动作是 merge")

作业 3：byte 级起点

现代 tokenizer 常从 bytes 开始，这样任何 Unicode 字符都能被处理。

小提示：Python 里可以用 text.encode("utf-8") 查看一个字符串对应的 bytes。

# 作业 3：UTF-8 bytes 填空
text = "你😊"

# TODO：把下面三引号里的内容替换成你的代码
byte_values = """在这里把 text 编码成 UTF-8 byte 数值列表"""

assert not isinstance(byte_values, str), "请先替换三引号里的占位内容"
assert byte_values == [228, 189, 160, 240, 159, 152, 138], byte_values
print("✅ 作业 3 通过：你理解了为什么现代 tokenizer 常从 bytes 开始")

附录：一步步还原 BPE 原理

以下附录适合想理解 BPE 内部每一步的同学。我们从字符级起点出发，手动统计 pair、合并、训练，逐步完成一个 mini BPE tokenizer。

正文里已经定义过 BPETokenizer 类和 corpus 变量。附录里的代码可以直接使用它们。

A.1 起点：字符级切分

BPE 的起点是字符级：先把文本拆成字符，每个字符都是一个 token。之所以从字符开始，是因为字符虽然碎，但很稳定——只要字符在词表里，新词就还能被拆开表示。

还有一个细节：空格怎么处理？真实 GPT tokenizer 会对空格做更精细的处理。这个 mini 版先把空格也当普通字符，这样能清楚看到 BPE 不只会合并字母，也可能把 e 和空格这样的组合合起来。

# 把所有句子拆成字符列表
def text_to_tokens(text):
    """把一段文本拆成字符级 token 列表"""
    return list(text)

# 看第一条句子
sentence = corpus[0]
chars = text_to_tokens(sentence)
print(f"原文:   '{sentence}'")
print(f"拆成字符: {chars}")
print(f"共 {len(chars)} 个 token")

# 把整条语料的每条句子都拆成字符列表
corpus_tokens = [text_to_tokens(s) for s in corpus]
print(f"\n语料中每条句子的字符数: {[len(t) for t in corpus_tokens]}")

A.2 统计相邻 pair

接下来统计整个语料中所有相邻 token pair 的出现频率。谁出现最多，谁就最值得先合并。

以一个短序列为例：

['t', 'h', 'e', ' ', 'c', 'a', 't']
  ↑──↑   ↑──↑   ↑──↑   ↑──↑   ↑──↑
 ('t','h') ('h','e') ('e',' ') (' ','c') ('c','a') ('a','t')

单个句子里看不出太多规律，所以要统计整个语料。

def count_pairs(token_lists):
    """
    统计整个语料中所有相邻 token pair 的出现频率

    参数:
        token_lists: List[List[str]]，每条句子是一个字符列表
    返回:
        dict: {(token_a, token_b): 出现次数}
    """
    pairs = {}
    for tokens in token_lists:
        for i in range(len(tokens) - 1):
            pair = (tokens[i], tokens[i + 1])
            if pair not in pairs:
                pairs[pair] = 0
            pairs[pair] += 1
    return pairs

# 统计初始状态（全字符级）的 pair 频率
initial_pairs = count_pairs(corpus_tokens)

print("=== 初始状态下所有相邻 pair 的频率 ===")
for pair, count in sorted(initial_pairs.items(), key=lambda x: -x[1]):
    print(f"  {pair}: {count} 次")

print(f"\n最高频 pair: {max(initial_pairs, key=initial_pairs.get)}")
print(f"出现了 {initial_pairs[max(initial_pairs, key=initial_pairs.get)]} 次")

A.3 合并最高频 pair

找到最高频 pair 后，BPE 会把语料里所有出现这个 pair 的地方都合并掉：

合并前: ['t', 'h', 'e', ' ', 'c', 'a', 't']
假设要合并: ('t', 'h')
合并后: ['th', 'e', ' ', 'c', 'a', 't']
            ↑  't' 和 'h' 变成一个 token 'th'

合并之后，th 会作为一个整体参与后续的统计。下次统计 pair 时，可能会出现 ('th', 'e') 这样的新组合。

def merge_pair(token_lists, pair_to_merge):
    """
    把语料中所有出现的指定 pair 合并成一个 token

    参数:
        token_lists: List[List[str]]，当前语料的 token 表示
        pair_to_merge: (str, str)，要合并的 pair
    返回:
        合并后的新 token_lists, 新 token
    """
    a, b = pair_to_merge
    new_token = a + b

    new_token_lists = []
    for tokens in token_lists:
        new_tokens = []
        i = 0
        while i < len(tokens):
            if i < len(tokens) - 1 and tokens[i] == a and tokens[i + 1] == b:
                new_tokens.append(new_token)
                i += 2
            else:
                new_tokens.append(tokens[i])
                i += 1
        new_token_lists.append(new_tokens)

    return new_token_lists, new_token

# 演示：做一次合并
best_pair = max(initial_pairs, key=initial_pairs.get)
print(f"要合并的 pair: {best_pair}")

merged_tokens, new_token = merge_pair(corpus_tokens, best_pair)
print(f"新 token: '{new_token}'")
print(f"\n合并后第 0 条的 token 序列：")
print(f"  {merged_tokens[0]}")

A.4 合并之后，统计对象也变了

合并不仅改了词表，也改变了后续统计的基础。BPE 的训练循环只有 4 步：

1. 统计 pair 频率
2. 找最高频 pair
3. 合并这个 pair
4. 记录这条合并规则（merge rule）

然后回到第 1 步。每次合并都会制造新的相邻关系——比如先得到 th，后面就可能继续得到 the。所以 BPE 不是一次性识别出一个词，而是一步步长出来的。

A.5 词表怎样增长：只新增，不删除

这里特别容易误会：merge 之后，旧 token 会不会从 vocab 里消失？答案是不会。

真正变化的是两件事：

1. 当前训练语料里的 token 序列会被合并，比如 ['a', 'n'] 变成 ['an']
2. vocab 会追加一个新 token，比如新增 'an'

原来的 'a' 和 'n' 还会留在 vocab 里。为什么？因为以后遇到别的新词时，可能还要退回到这些更小的单位。下面用一个极小的例子观察。

# 观察 vocab 如何一步步增长
toy_token_lists = [list("banana")]
toy_vocab = set(toy_token_lists[0])


def print_vocab_state(step, token_lists, vocab, new_token=None):
    """打印当前语料 token 序列和当前词表"""
    title = f"Step {step}"
    if new_token is not None:
        title += f" | 新增 token: {new_token!r}"
    print(title)
    print(f"  当前语料 tokens: {token_lists[0]}")
    print(f"  当前 vocab({len(vocab)}): {sorted(vocab)}")
    print()


print_vocab_state(0, toy_token_lists, toy_vocab)

for step in range(1, 4):
    pair_counts = count_pairs(toy_token_lists)
    best_pair = max(pair_counts, key=pair_counts.get)
    best_count = pair_counts[best_pair]

    toy_token_lists, new_token = merge_pair(toy_token_lists, best_pair)
    toy_vocab.add(new_token)

    print(f"本轮最高频 pair: {best_pair}，出现 {best_count} 次")
    print_vocab_state(step, toy_token_lists, toy_vocab, new_token)

print("关键观察：vocab 只追加新 token；旧字符仍然留在词表里。")

A.6 完整训练循环

现在把上面的循环跑起来。有一个重要参数：num_merges——合并次数。合并次数决定了词表大小：做几次 merge，就新增几个 token。设 num_merges=15，打开 verbose 观察每一步。

# 用正文中已定义的 BPETokenizer 类，打开 verbose 重新训练
bpe_verbose = BPETokenizer()
_ = bpe_verbose.train(corpus, num_merges=15, verbose=True)

A.7 训练日志解读

回头看上面的训练日志，它是一个逐步生长的过程：

Step 1: ('e', ' ')   → 'e '     ← e 后面接空格很常见
Step 2: ('t', 'h')   → 'th'     ← the 出现多，所以 th 先出现
Step 3: ('th', 'e ') → 'the '   ← th 和 e 空格继续合成
Step 4: ('a', 't')   → 'at'     ← cat / sat / mat 让 at 很常见
Step 5: ('o', 'g')   → 'og'     ← dog / log 里的 og 也被合并

BPE 不是"认识英文单词"的程序。它只是做统计：谁经常挨在一起，谁就先合并。这也解释了为什么词表大小可控：做 15 次合并，就只新增 15 个 token。

merge rules 怎样一步步长出来

常见组合会先出现，然后更长的组合在它们上面继续生长。下面打印完整的 merge rules 列表，注意观察 the 是怎么一步步被拼出来的。

print("Merge Rules 完整列表（按训练顺序）:")
print("注意看 'the' 是怎么诞生的：")
print()

for i, (a, b) in enumerate(bpe_verbose.merge_rules):
    arrow = ""
    merged = a + b
    if merged in ['th', 'the ', 'the c', 'the cat ']:
        arrow = "  ← 'the' 的诞生过程！"
    if a in ['th', 'the ', 'the c'] or b in ['e ', 'c', 'at ']:
        arrow = "  ← 'the' 的诞生过程！"
    print(f"  Rule {i+1:2d}: '{a}' + '{b}' → '{merged}'{arrow}")

print()
print("关键观察：'the ' 不是一次性识别出来的。")
print("是 't'+'h'→'th'，再和 'e ' 合并，逐渐形成的。")

A.8 encode 的贪心合并

训练结束后，我们已经有了一串 merge rules。现在来了新文本，怎么编码？

流程很简单：

1. 先把新文本拆成字符
2. 按训练时的 merge rules 顺序，一条一条尝试合并
3. 最后把剩下的 token 查成 ID

"the cat"
  → ['t','h','e',' ','c','a','t']
  → 应用 rule 1: ('e',' ') → 'e '
  → ['t','h','e ','c','a','t']
  → 应用 rule 2: ('t','h') → 'th'
  → ['th','e ','c','a','t']
  → 应用 rule 3: ('th','e ') → 'the '
  → ['the ','c','a','t']
  → 应用 rule 4: ('a','t') → 'at'
  → ['the ','c','at']

这里最关键的一点：顺序不能乱。 因为先合并什么，会影响后面还能不能合并。encode 不是重新统计频率，而是按训练时学到的规则照着做。

A.9 从字符级到 byte 级：GPT-2 风格的 BPE

GPT-2 的 Tokenizer 本质上是一个 byte-level BPE tokenizer。相比我们的 mini 版，它有三个升级：

1. 起点从字符换成 byte：256 个 byte 构成基础词表，覆盖所有 Unicode
2. 加入 pre-tokenization：用正则先把文本切成独立片段，防止跨词合并
3. 训练 merge rules：在 pre-tokenized 片段上做 BPE，合并 byte 对

GPT-2 的最终词表大小 = 256（基础 byte）+ 50,000（学到的 merge）+ 1（special token）= 50,257。下面用 tokenizers 库在小语料上演示 vocab 如何从 256 个 byte 逐步增长。

# 复现 GPT-2 Tokenizer：byte-level BPE
# 步骤：256 个基础 byte → pre-tokenization → BPE 训练 → 观察 vocab 增长
try:
    from tokenizers import Tokenizer
    from tokenizers.models import BPE
    from tokenizers.pre_tokenizers import ByteLevel
    from tokenizers.trainers import BpeTrainer

    # GPT-2 的训练语料（这里用小语料演示，真实 GPT-2 用了海量网页文本）
    gpt2_style_corpus = [
        "the cat sat on the mat",
        "the dog sat on the log",
        "the cat and the dog",
        "hello GPT-2 style BPE",
        "numbers: 327 + 1 = 328",
        "unicode: 你好 😊",
    ]

    # Step 1: 基础词表 = 256 个 byte
    # ByteLevel.alphabet() 返回的就是这 256 个 byte 对应的 token
    base_byte_tokens = set(ByteLevel.alphabet())
    special_tokens = ["HUMAN>"]  # GPT-2 只有一个 special token

    print(f"Step 1: 基础词表 = {len(base_byte_tokens)} 个 byte")
    print(f"Special token: {special_tokens}")
    print(f"提示：输出里的 'Ġ' 表示词首空格，这是 ByteLevel 编码的结果。")
    print()

    # Step 2: 逐轮增大 vocab_size，观察 BPE 学到了什么新 token
    previous_learned_tokens = set()

    for target_vocab_size in [260, 268, 276]:
        # 创建空的 BPE 模型（不指定 unk_token，因为 byte 级不会遇到未知字符）
        tokenizer = Tokenizer(BPE())
        
        # 加入 ByteLevel pre-tokenizer：处理空格和 Unicode
        # 这是 GPT-2 的核心之一：先把文本转成 byte 序列，再做 BPE
        tokenizer.pre_tokenizer = ByteLevel(add_prefix_space=False)

        # 配置训练器
        # initial_alphabet: 256 个 byte 作为起点
        # vocab_size: 目标词表大小 = 256 + merge 数量
        trainer = BpeTrainer(
            vocab_size=target_vocab_size,
            initial_alphabet=ByteLevel.alphabet(),
            special_tokens=special_tokens,
            show_progress=False,
        )
        tokenizer.train_from_iterator(gpt2_style_corpus, trainer=trainer)

        # 统计本轮新学到的 token
        vocab = tokenizer.get_vocab()
        learned_tokens = set(vocab) - base_byte_tokens - set(special_tokens)
        new_tokens = learned_tokens - previous_learned_tokens

        learned_sorted = sorted(learned_tokens, key=lambda token: vocab[token])
        new_sorted = sorted(new_tokens, key=lambda token: vocab[token])

        print(f"target vocab_size={target_vocab_size}，实际大小={len(vocab)}")
        print(f"  BPE 新增 token 数: {len(learned_sorted)}")
        print(f"  本轮新学到: {new_sorted[:12]}")
        print(f"  累计新增（前 12 个）: {learned_sorted[:12]}")
        print()

        previous_learned_tokens = learned_tokens

    print("观察：")
    print("  - 初始 256 个 byte + 每轮新增的 merge token = 最终 vocab")
    print("  - 'Ġ' 开头的 token 表示带词首空格的子词（如 'Ġthe' = ' the'）")
    print("  - GPT-2 真实训练时做了 50,000 次 merge，最终 vocab = 50,257")

except Exception as e:
    print("未能运行 byte-level BPE 演示。")
    print(f"原因: {e}")
    print("请安装 tokenizers: pip install tokenizers")

A.10 工业界的词表大小

工具/库	代表模型	词表大小	起点
tiktoken	GPT-2	50,257	Bytes
tiktoken	GPT-4 常用 cl100k_base	100,256 mergeable ranks；完整编码还包含 special tokens	Bytes
SentencePiece	LLaMA	32,000	Bytes

词表太小（几千）：序列太长，Self-Attention 计算量跟序列长度的平方成正比。词表太大（几百万）：Embedding 层参数膨胀，同时很多 token 只出现几次，模型学不好。现代 LLM 词表常见从 32K 到 200K+ 不等，没有统一平衡点；具体取决于语料、语言覆盖、special tokens 和工程取舍。