---
tags: [AI, tokenizer, bpe]
阶段: 05-Transformer与LLM原理
难度: ★★☆
created: 2026-10-18
related: "[[预备知识-token与嵌入]], [[GPT系列架构]], [[从零实现小型GPT指南]]"
---

# Tokenizer与BPE

## 定义

**分词器**（tokenizer）是把字符串确定性地映射为有限词表 $\mathcal{V}$ 上的 token 序列、并提供逆映射（解码）的程序；**字节对编码**（Byte Pair Encoding，BPE）是一类子词分词算法，它从基础符号集合出发，反复统计语料中相邻符号对的加权频次、合并频次最高的符号对，并把合并顺序记录为一组有序重写规则，词表由基础符号与合并产生的新符号共同构成。

本篇符号约定如下。

| 符号 | 含义 |
|---|---|
| $\Sigma$ | 基础符号集合，字符级为字符集，字节级为 256 个字节值 |
| $\mathcal{V}$、$V$ | 词表与词表大小，$V=\lvert\mathcal{V}\rvert$ |
| $\mathcal{D}$、$c(w)$ | 训练语料与词 $w$ 的出现次数 |
| $\mathrm{freq}(a,b)$ | 相邻符号对 $(a,b)$ 在语料中的加权频次 |
| $M=(m_1,\dots,m_{K})$ | 合并规则序列，$m_k=(a_k,b_k)\to a_kb_k$ |
| $K$ | 合并次数，即训练时执行的合并步数 |
| $T$ | 编码后 token 序列长度 |
| $B$ | 原始文本的字节数 |
| $\kappa=B/T$ | 压缩率，每个 token 平均承载的字节数 |
| `</w>` | 词尾标记，区分词尾与非词尾的相同符号序列 |
| `▁` | SentencePiece 的空格元符号，代表一个前导空格 |
| `##` | WordPiece 的词中续接前缀 |

其余术语在正文首次出现处定义：**未登录词**（out-of-vocabulary，OOV）指词表中不存在、无法直接映射为单个 id 的字符串；**子词**（subword）是介于字符与词之间的切分单元；**字节级 BPE**（byte-level BPE）指以 256 个字节值为基础符号的 BPE；**特殊 token** 指不参与频次统计、由字面量匹配直接识别的控制符号；**填充**（padding）指把同一批次内的序列补齐到等长。

## 为什么重要

分词器同时决定两个量，而这两个量分别进入模型的两项主要开销。词表大小 $V$ 决定嵌入参数 $Vd$ 与输出投影的每 token 计算量 $dV$；序列长度 $T$ 决定注意力的 $O(T^{2})$ 计算量与 KV Cache 的显存，见 [[KV缓存]]。因此分词方案不是预处理细节，而是与层数、维度同级的架构决策。

具体后果可以量化。字符级分词下 $V$ 只有几十到几百，嵌入层很小，但 1 MB 英文文本约产生 $10^{6}$ 个 token，注意力计算量按 $T^{2}$ 增长，相对每 token 约 4 字节的 BPE 切分高出约 16 倍。词级分词下 $T$ 缩短到 $1.8\times10^{5}$ 量级，但开放词表的 $V$ 可达 $10^{6}$，嵌入参数膨胀到无法训练，且任何未登录词都只能映射为 `[UNK]`。子词方案把两端折中：$V$ 取 $3\times10^{4}$ 至 $2\times10^{5}$，未登录词被分解为若干已知子词，$T$ 与 $V$ 同时可控。

多语言场景下差异更直接。UTF-8 中一个常用汉字占 3 字节，GPT-2 的 byte-level 词表以英文语料训练，中文文本的平均压缩率约为每 token 1 至 1.5 个汉字，同一段内容占用的上下文是英文的 2 至 3 倍；改用覆盖中文的现代词表后该比值可降到约 1 token 每 1 至 1.5 字。这直接改变可用的上下文长度、推理成本与按 token 计费的账单。

在本库中的位置：[[预备知识-token与嵌入]] 说明 token 如何变成向量，本篇说明 token 如何从文本产生；[[GPT系列架构]] 与 [[Llama-2架构复盘]] 的词表规模与切分行为由本篇解释；[[从零实现小型GPT指南]] 要求先实现一个可训练、可复现的 tokenizer，否则损失曲线无法与基线比较。对应学习目标中的「能复现」与「会评估」：能实现 BPE 训练与编码，能根据 $V$、$\kappa$ 估算参数与计算量。

## 原理与推导

### 1 三种粒度的形式化对比

设原始文本为字节串，长度 $B$。分词器输出 $(t_1,\dots,t_T)$，每个 $t_p\in\mathcal{V}$，且解码满足 $\mathrm{decode}(\mathrm{encode}(s))=s$（字节级与 SentencePiece 满足严格可逆，词级不满足）。

- 字符级：$\Sigma$ 为字符集或字节集，$\mathcal{V}=\Sigma\cup\{\text{特殊 token}\}$，$T$ 等于字符数或字节数。
- 词级：以空白与标点预切分得到词，$\mathcal{V}$ 为词表，$T$ 等于词数，未登录词映射为 `[UNK]`。
- 子词级：$\mathcal{V}=\Sigma\cup\{ab:(a,b)\in M\}$，$T$ 由贪心合并规则决定，介于两者之间。

三种粒度的差异可以写成四个指标：$V$、$T$、OOV 率、以及每个 token 承载的信息量。下表取 1 MB 英文文本（约 $10^{6}$ 字节、$1.8\times10^{5}$ 词）作估算。

| 粒度 | $V$ | $T$ | OOV | 嵌入参数 $Vd$（$d=768$） | 注意力相对成本 |
|---|---|---|---|---|---|
| 字符级 | $10^{2}$ | $10^{6}$ | 无（覆盖全集时） | $7.7\times10^{4}$ | 16 |
| 词级 | $10^{6}$ | $1.8\times10^{5}$ | 有 | $7.7\times10^{8}$ | 0.52 |
| 子词级（$\kappa\approx4$） | $5\times10^{4}$ | $2.5\times10^{5}$ | 无 | $3.8\times10^{7}$ | 1 |

注意力相对成本以子词级为 1，按 $(T/T_{\text{sub}})^{2}$ 计算。字符级方案的嵌入只占 $7.7\times10^{4}$ 个参数，但注意力成本是子词级的 16 倍，且 $10^{6}$ 长度的依赖需要同样深的网络传播；词级方案的注意力最省，但 $7.7\times10^{8}$ 个嵌入参数在 $d=768$ 时已超过 GPT-2 small 全部参数的五倍，且 OOV 使稀有词与专有名词无法表示。子词方案在这两个约束之间取得可行点，这是当代语言模型统一采用子词分词的原因。

需要补充的是，词级分词的 OOV 并非只影响稀有词。以空格与标点切分时，大小写、屈折变化、连字符复合词都产生独立词条，英语中 "run/runs/running/ran" 占四个词表条目且彼此不共享参数；子词切分使它们共享 "run" 这一子词，从而共享嵌入行与预测信号。

### 2 BPE 训练算法

训练输入是语料与其词频。算法把每个词拆成基础符号序列，词尾追加 `</w>` 以区分词尾与非词尾的同一符号串（例如 "low" 与 "lower" 中的 "low"），然后重复 $K$ 次"统计相邻对、合并最高频对、改写全部词"。

```
TRAIN-BPE(D, K):
  vocab[w] ← split(w) + ["</w>"]       对每个词 w，split 为基础符号序列
  freq[w]  ← c(w)                      词频
  V ← Σ ∪ {"</w>"}
  M ← []
  repeat K times:
    cnt ← empty map
    for each w with freq[w] > 0:       统计相邻对，按词频加权
      for i ← 1 to |vocab[w]| - 1:
        cnt[(vocab[w][i], vocab[w][i+1])] += freq[w]
    if cnt is empty: break
    (a*, b*) ← argmax cnt，平局按确定规则打破
    M.append((a*, b*))
    V.add(a* + b*)
    for each w: vocab[w] ← MERGE(vocab[w], a*, b*)
  return M, V

MERGE(s, a, b):                        从左到右替换不重叠的相邻对
  out ← []
  i ← 1
  while i ≤ |s|:
    if i < |s| and s[i] == a and s[i+1] == b:
      out.append(a + b)
      i ← i + 2
    else:
      out.append(s[i])
      i ← i + 1
  return out
```

朴素实现的代价是每轮遍历全部语料，总时间 $O(K\cdot|D|\cdot\bar{L})$，其中 $\bar{L}$ 为平均词长；工程实现维护"符号对到出现位置"的倒排索引与优先队列，把每轮代价降到与该对出现次数成正比，总时间 $O(|D|\bar{L}\log(|D|\bar{L}))$。空间上需要为每个词保存当前符号序列与频次。

手工算例。语料为 $\{(\text{low},5),(\text{lower},2),(\text{newest},6),(\text{widest},3)\}$，初始符号序列与词频为

```
l o w </w>        : 5
l o w e r </w>    : 2
n e w e s t </w>  : 6
w i d e s t </w>  : 3
```

第一轮统计全部相邻对，按词频加权后得到 14 个不同的对：

| 对 | 频次 | 来源 |
|---|---|---|
| (e,s) | 9 | newest 6 + widest 3 |
| (s,t) | 9 | newest 6 + widest 3 |
| (t,`</w>`) | 9 | newest 6 + widest 3 |
| (w,e) | 8 | lower 2 + newest 6 |
| (l,o) | 7 | low 5 + lower 2 |
| (o,w) | 7 | low 5 + lower 2 |
| (e,w) | 6 | newest 6 |
| (n,e) | 6 | newest 6 |
| (w,`</w>`) | 5 | low 5 |
| (d,e)、(i,d)、(w,i) | 3 | widest 3 |
| (e,r)、(r,`</w>`) | 2 | lower 2 |

最高频有三个并列 9。此时必须有一条确定性规则，本篇取"频次降序，其次拼接字符串字典序升序"，故选择 (e,s)，因为 "es" 小于 "st" 与 "t`</w>`"。规则记入 $M$，词表中加入 "es"，四行分别改写为 `l o w </w>`、`l o w e r </w>`、`n e w es t </w>`、`w i d es t </w>`。后续四轮如下。

| 轮次 | 选中合并 | 频次 | 次高频对 | 合并后受影响的行 |
|---|---|---|---|---|
| 1 | (e,s) | 9 | (s,t)=9、(t,`</w>`)=9 | `n e w es t </w>`、`w i d es t </w>` |
| 2 | (es,t) | 9 | (t,`</w>`)=9 | `n e w est </w>`、`w i d est </w>` |
| 3 | (est,`</w>`) | 9 | (l,o)=7 | `n e w est</w>`、`w i d est</w>` |
| 4 | (l,o) | 7 | (o,w)=7 | `lo w </w>`、`lo w e r </w>` |
| 5 | (lo,w) | 7 | (e,w)=6 | `low </w>`、`low e r </w>` |

五轮后 $M=[(e,s),(es,t),(est,\texttt{</w>}),(l,o),(lo,w)]$，基础符号为 $\{l,o,w,e,r,n,s,t,i,d,\texttt{</w>}\}$ 共 11 个，词表大小 $V=11+5=16$。

该算例给出三个可检验的结论。第一，平局规则影响结果：若平局取"先出现者优先"，第一轮可能选择 (s,t)，后续合并序列完全不同，但两种结果都是合法 BPE，因此不同实现的词表不可逐项比较，只能按整体压缩率与下游损失比较。第二，"newest" 最终被切为 `n e w est</w>` 而非整词，原因是其内部对 (n,e)、(e,w)、(w,est`</w>`) 的频次均为 6，低于 (l,o) 的 7；BPE 只按频次，不识别词素边界，因此同一词根在不同词频下会得到不同切分，例如 "low" 被整体合并而 "lower" 仍为 `low e r </w>`。第三，词表大小由基础符号数与合并次数相加得到，这一关系在字节级下变为 $V=256+K+|\text{特殊 token}|$。

### 3 编码算法

编码是训练规则的顺序应用：把待编码词拆为基础符号，然后按 $M$ 的顺序逐条重写，每条规则只合并当前序列中从左到右不重叠的出现。

以第 2 节学到的规则编码 "lowest"：初始为 `l o w e s t </w>`；规则 (e,s) 得 `l o w es t </w>`；规则 (es,t) 得 `l o w est </w>`；规则 (est,`</w>`) 得 `l o w est</w>`；规则 (l,o) 得 `lo w est</w>`；规则 (lo,w) 得 `low est</w>`。最终切分为 `low | est</w>`，两步合并得到词表中存在的两个子词。

编码顺序不可交换。若先应用 (lo,w) 再应用 (e,s)，在 "lowest" 上结果相同，但在跨规则重叠的场景会不同：设规则为 (a,b) 与 (b,c)，输入 `a b c`，先应用前者得 `ab c`，后者不再匹配；先应用后者得 `a bc`。BPE 的定义固定为先学到的规则先应用，因此编码必须按 $M$ 的顺序执行，或等价地给每条规则赋予序号并要求每次合并当前序号最小的可行对。tiktoken 采用后一种实现：把合并规则存为"字节对到 rank"的映射，循环取出 rank 最小的相邻对合并，直到没有可合并对为止。

编码复杂度为每词 $O(K\cdot L)$ 的朴素上界，使用优先队列可降到 $O(L\log L)$。需要注意，该贪心过程不保证在某个概率模型下是最优切分；Unigram 分词显式地用 Viterbi 算法求最大概率切分，两者的区别见第 7 节。

### 4 字节级 BPE 与 UTF-8

字符级 BPE 的基础符号是 Unicode 字符，这要求词表覆盖全部可能出现的字符。Unicode 已分配码点超过 14 万个，且仍在扩展，直接以码点为基础符号会使 $V$ 的下界过高，并让新字符成为未登录项。字节级 BPE 把基础符号改为 256 个字节值，任何文本先按 UTF-8 编码为字节串，再由 BPE 合并。

UTF-8 的编码长度由码点范围决定：

| 码点范围 | 字节数 | 典型内容 |
|---|---|---|
| U+0000–U+007F | 1 | ASCII 字母、数字、英文标点 |
| U+0080–U+07FF | 2 | 拉丁扩展、希腊、西里尔字母 |
| U+0800–U+FFFF | 3 | 中日韩常用汉字、多数标点 |
| U+10000–U+10FFFF | 4 | 扩展区汉字、部分 emoji |

由于 256 个基础符号覆盖全部字节值，任何字节串都可编码，**字节级 BPE 不存在未登录词**，解码只需把 token 对应的字节串拼接后按 UTF-8 解码，是无损的。代价是非 ASCII 文本的 $T$ 增大：一个常用汉字占 3 字节，若合并规则未覆盖该汉字对应的字节三元组，它至少占 3 个 token。

GPT-2 的实现在字节与可打印 Unicode 码点之间建立双射 `bytes_to_unicode`：把 256 个字节值映射到 256 个可打印码点，例如空格 0x20 映射为 "Ġ"（U+0120），换行 0x0A 映射为 "Ċ"（U+010A），其余可打印 ASCII 保持原样。该映射只是显示层约定，使 token 字符串可打印、可放入 JSON 与词表文件；解码时先做逆映射得到字节串，再按 UTF-8 解码。它不是压缩，也不改变 token 数。

GPT-2 的词表构成为

$$
V=256+50000+1=50257,
$$

其中 256 个基础字节、50000 条合并规则、1 个特殊 token `<|endoftext|>`。50000 这个数量的直接约束是参数与计算：在 $d=768$、总参数 $1.24\times10^{8}$ 的模型上，$50257\times768=3.86\times10^{7}$ 已占 31%，再扩大词表会挤压注意力与前馈的容量，并使每个 token 的输出投影成本线性上升。后续词表规模的选择遵循同一权衡：r50k_base 为 50257，p50k_base 为 50281，cl100k_base 约为 10 万，o200k_base 约为 20 万，扩大词表的目的主要是提高非英语与代码的压缩率。

压缩率的实际含义由 $\kappa=B/T$ 给出。英文文本在 GPT-2 词表下约 $\kappa\approx4$ 字节每 token；中文文本的每个汉字占 3 字节，在英文主导的合并规则下 $\kappa$ 约为 1 至 1.5，即每字约 2 至 3 个 token；在覆盖中文的现代词表下 $\kappa$ 提高到约 3，即每字约 1 个 token。同一段中文的 $T$ 因此可相差 2 至 3 倍，直接影响上下文占用与推理成本。

### 5 特殊 token、padding 与三类掩码

特殊 token 是不参与频次统计、由字面量匹配直接识别的控制符号。常见的有文档分隔 `<|endoftext|>`、序列起始 BOS、序列终止 EOS、填充 PAD、未登录 UNK，以及对话模型中的角色标记。实现上必须在 BPE 之前用字面量切分把特殊 token 单独取出，否则 `<|endoftext|>` 会被拆成 `<`、`|`、`e` 等普通符号，失去控制语义。这也是分词器接口通常提供 `allowed_special` 参数的原因。

`padding` 用于把同一批次的序列补齐到等长 $T_{\max}$。它牵涉三处独立处理。嵌入层用 `padding_idx` 把该行初始化为零并屏蔽其梯度，使填充位置不产生参数更新。注意力层需要 padding mask，把键侧的填充位置的打分置为 $-\infty$（实现中常取 $-10^{9}$ 这类足够小的有限值，避免 $-\infty$ 与 0 相乘产生 `nan`），否则 softmax 会把概率分配给无意义的填充位。损失层需要 ignore 索引，把填充位置的交叉熵排除在求和之外，否则模型会被训练去预测填充符。

三类掩码容易混淆，其作用位置与形状不同：

| 掩码 | 作用位置 | 形状 | 作用 |
|---|---|---|---|
| padding mask | 注意力的打分矩阵 | $(B,1,1,T)$ 或 $(B,1,T,T)$ | 屏蔽键侧的填充位置 |
| causal mask | 注意力的打分矩阵 | $(1,1,T,T)$ 下三角 | 屏蔽未来位置 |
| loss mask | 交叉熵 | $(B,T)$ | 排除填充位置与不参与训练的位置 |

训练时的文档边界同样依赖特殊 token。若把多条短文档直接拼接到 $T_{\max}$ 而不插入 EOS 或不隔离注意力，模型会把后一篇文档的开头当作前一篇的续写，学会跨文档的虚假依赖；常见做法是每条文档末尾加 EOS，并在拼接时使用文档级注意力隔离，或退化为逐条填充。

### 6 词表大小与序列长度的定量影响

设嵌入维度 $d$、层数 $L$、序列长度 $T$、词表大小 $V$，忽略偏置。嵌入参数为 $Vd$（权重绑定）或 $2Vd$（输入与输出不共享）；输出投影每个 token 需要 $dV$ 次乘加。注意力中随 $T$ 增长的两项是打分 $\mathbf{Q}\mathbf{K}^{\top}$ 与加权 $\mathbf{A}\mathbf{V}$，每 token 每层各需 $Td$ 次乘加，$L$ 层合计 $2LTd$。这里只比较这两项，是因为每 token 每层还有 $4d^{2}$ 的 Q/K/V/O 投影，它与 $T$ 无关、与词表成本同为 $O(d^{2})$ 项，需单独核算。两者之比为

$$
R=\frac{dV}{2LTd}=\frac{V}{2LT},
$$

与 $d$ 无关。$R$ 说明词表成本与序列长度成本是一对此消彼长的量：$T$ 较小时输出投影占主导，$T$ 较大时注意力占主导。取 $L=32$、$T=2048$，则 $2LT=131072$，$V=32000$、$50257$、$100000$、$128000$ 分别给出 $R=0.244$、$0.383$、0.763、0.977；取 $T=8192$ 时同样四个词表的 $R$ 降为 $0.061$、$0.096$、0.191、0.244。

代入具体配置可以看清投影项的地位。取 $V=50257$、$d=768$、$L=12$、$T=1024$，打分与加权两项合计 $1.89\times10^{7}$，投影项合计 $12\times4\times768^{2}=2.83\times10^{7}$，二者相加为 $4.72\times10^{7}$，与输出投影的 $3.86\times10^{7}$ 同量级；$T$ 增至 4096 时投影项不变而两项增至 $7.55\times10^{7}$，投影占注意力总量的 27%。因此"输出投影主导"这一判断只在只计两项且 $T$ 较小时成立，做硬件核算时必须把投影项计入。

压缩率则通过 $T=B/\kappa$ 进入注意力成本。单条序列的注意力乘加量为 $2LT^{2}d$，代入 $T=B/\kappa$ 得

$$
2Ld\left(\frac{B}{\kappa}\right)^{2},
$$

即压缩率提高一倍，注意力成本降为四分之一。这解释了长上下文模型倾向于更大词表的原因；代价是嵌入矩阵与输出投影线性增大，且低频 token 的嵌入行获得更新的次数减少。词表从 $5\times10^{4}$ 扩到 $2\times10^{5}$ 时，嵌入参数增加 $1.5\times10^{5}\times d$，在 $d=4096$ 时为 $6.1\times10^{8}$ 个参数，已与若干层同量级，因此扩大词表通常伴随对嵌入层的单独处理，例如更大的学习率或低秩分解。

词表大小的经验区间由此确定：单语英文模型 $3\times10^{4}$ 至 $5\times10^{4}$，多语言模型 $1\times10^{5}$ 至 $2.5\times10^{5}$，代码模型偏向覆盖缩进与常见符号组合。判断一个词表是否合适，可同时看三个量：在目标语料上的 $\kappa$、$Vd$ 占总参数的比例 $r$、以及每个词表条目平均分到的训练 token 数 $N_{\text{tok}}/V$；第三项过小意味着大量嵌入行的估计方差过大。

### 7 WordPiece 与 SentencePiece

WordPiece 与 BPE 的差别在合并准则。BPE 选择频次最高的对，WordPiece 选择使训练语料似然增益最大的对，其打分常写为

$$
\mathrm{score}(a,b)=\frac{\mathrm{freq}(ab)}{\mathrm{freq}(a)\,\mathrm{freq}(b)},
$$

即点互信息形式：分子要求该对常见，分母惩罚两个符号各自过于常见，从而偏向结合紧密的对。编码时 WordPiece 采用最长匹配优先：从当前位置开始尝试最长的词表前缀，匹配失败则回退到更短的前缀，仍未匹配则该位置输出 UNK；词中续接的片段加 `##` 前缀。BERT 使用 30000 词的 WordPiece 词表，并引入 `[CLS]`、`[SEP]`、`[MASK]`、`[PAD]`、`[UNK]` 五个特殊 token。

SentencePiece 的差别在输入表示与切分模型。它直接在原始文本上训练，不要求预先按空格切分，把空格替换为元符号 `▁` 并纳入词表，因此解码时把 `▁` 还原为空格即可严格可逆，对中文、日文等无空格语言不需要额外预分词。它支持两种切分模型：BPE 模式与 Unigram 模式。Unigram 从一个大候选词表出发，用期望最大化估计每种切分的概率，再按对语料似然的损失剪枝词表；编码时用 Viterbi 算法求概率最大的切分，因此其结果可能不同于 BPE 的贪心合并。

三种方案的对比：

| 维度 | BPE | WordPiece | Unigram（SentencePiece） |
|---|---|---|---|
| 训练目标 | 最高频相邻对 | 似然增益最大的对 | 词表剪枝后语料似然最大 |
| 编码方式 | 按合并顺序贪心重写 | 最长匹配优先 | Viterbi 最大概率切分 |
| 词表规模 | $256+K$（字节级） | $3\times10^{4}$ 量级 | $3\times10^{4}$ 至 $10^{5}$ |
| 空格处理 | 作为普通符号或预切分 | 预切分后丢弃 | 元符号 `▁`，可逆 |
| 未登录词 | 无（字节级） | 有（UNK） | 无（字符回退） |
| 典型使用者 | GPT 系列、Llama | BERT | T5、多语言模型 |

Llama 系列使用 SentencePiece 的 BPE 模式，词表 32000，因此其空格以 `▁` 形式进入词表；这与 GPT-2 的 `Ġ` 表示在语义上等价，都是把前导空格编码为可见字符，区别在于 SentencePiece 把它作为切分单元的一部分参与训练。

## 关键直觉

> [!tip] BPE 的词表是一组有序重写规则的集合：训练阶段按频次选择规则，编码阶段按规则被学到的顺序应用。词表大小等于基础符号数与合并次数之和，因此"词表大小"与"序列长度"是同一个压缩率参数的两个侧面：提高压缩率会缩短 $T$、降低注意力成本，同时增大 $V$、提高嵌入与输出投影成本。该表述对应第 2 节的 $V=|\Sigma|+K$、第 3 节的顺序应用规则与第 6 节的 $R=V/(2LT)$。

## 例子与代码

以下代码在 Python 3.13 下运行，输出为实际打印结果。

### 例 1：mini BPE 的训练与编码（核心函数约 30 行）

该实现与第 2 节的伪代码一一对应，语料即第 2 节的手算语料，可直接核对每一轮的合并与词表改写。

```python
from collections import Counter

def merge_symbols(symbols, a, b):          # 从左到右替换不重叠的相邻对
    out, i = [], 0
    while i < len(symbols):
        if i + 1 < len(symbols) and symbols[i] == a and symbols[i + 1] == b:
            out.append(a + b); i += 2
        else:
            out.append(symbols[i]); i += 1
    return tuple(out)

def train_bpe(corpus, num_merges):
    vocab = {tuple(w.split()): c for w, c in corpus.items()}   # 词 -> 符号序列
    merges = []
    for _ in range(num_merges):
        pairs = Counter()
        for syms, c in vocab.items():
            for p in zip(syms, syms[1:]):
                pairs[p] += c                                   # 按词频加权
        if not pairs:
            break
        (a, b), cnt = sorted(pairs.items(), key=lambda kv: (-kv[1], "".join(kv[0])))[0]
        vocab = {merge_symbols(s, a, b): c for s, c in vocab.items()}
        merges.append((a, b))
        print(f"merge {a!r}+{b!r} freq {cnt}")
        print("   words:", {(" ".join(s)): c for s, c in vocab.items()})
    return merges

def encode(word, merges):                  # 按学习顺序应用规则
    symbols = tuple(word) + ("</w>",)
    for a, b in merges:
        symbols = merge_symbols(symbols, a, b)
    return symbols

CORPUS = {"l o w </w>": 5, "l o w e r </w>": 2,
          "n e w e s t </w>": 6, "w i d e s t </w>": 3}
MERGES = train_bpe(CORPUS, num_merges=5)
print("merges:", MERGES)
for w in ["low", "lowest", "newest", "slow"]:
    print(w, "->", " | ".join(encode(w, MERGES)))
```

```text
merge 'e'+'s' freq 9
   words: {'l o w </w>': 5, 'l o w e r </w>': 2, 'n e w es t </w>': 6, 'w i d es t </w>': 3}
merge 'es'+'t' freq 9
   words: {'l o w </w>': 5, 'l o w e r </w>': 2, 'n e w est </w>': 6, 'w i d est </w>': 3}
merge 'est'+'</w>' freq 9
   words: {'l o w </w>': 5, 'l o w e r </w>': 2, 'n e w est</w>': 6, 'w i d est</w>': 3}
merge 'l'+'o' freq 7
   words: {'lo w </w>': 5, 'lo w e r </w>': 2, 'n e w est</w>': 6, 'w i d est</w>': 3}
merge 'lo'+'w' freq 7
   words: {'low </w>': 5, 'low e r </w>': 2, 'n e w est</w>': 6, 'w i d est</w>': 3}
merges: [('e', 's'), ('es', 't'), ('est', '</w>'), ('l', 'o'), ('lo', 'w')]
low -> low | </w>
lowest -> low | est</w>
newest -> n | e | w | est</w>
slow -> s | low | </w>
```

`train_bpe` 每轮做三件事：用 `Counter` 加权统计相邻对、按"频次降序、拼接字典序升序"选对、用 `merge_symbols` 改写全部词。`encode` 先把词拆成字符并追加词尾标记，再按 `merges` 的顺序逐条重写，因此对训练中未出现的词 "slow" 也能给出 `s | low | </w>` 的切分。若把 `encode` 中的循环改为逆序，本语料上结果不变，但规则存在跨词重叠时会产生不同切分，这是第 3 节所述顺序依赖的直接体现。若把 `sorted` 的平局键去掉，`max` 在并列时的选择依赖字典插入顺序，同一语料在不同 Python 版本或不同遍历顺序下可能得到不同合并序列。

### 例 2：词表与计算量的核算

用第 6 节的公式核对 GPT-2 small 规模下的两项开销，单位为乘加次数，换算为浮点运算量时乘 2。

```python
V, d, L, T = 50257, 768, 12, 1024
head_mac = d * V            # 输出投影：每 token 的乘加次数
attn_mac = 2 * L * T * d    # 注意力：QK^T 与 AV，每 token 每层 2*T*d
print(head_mac, attn_mac, round(head_mac / attn_mac, 3))
emb = V * d                 # 权重绑定下的嵌入参数
print(emb, round(4 * emb * 4 / 2**20, 1))   # 参数、梯度、两个 Adam 状态
```

```text
38597376 18874368 2.045
38597376 588.9
```

第一行给出输出投影每 token 约 $3.86\times10^{7}$ 次乘加，注意力的打分与加权两项约 $1.89\times10^{7}$ 次，比值 2.045，与 $R=V/(2LT)=50257/24576$ 一致；若把每层 $4d^{2}$ 的投影项计入，注意力合计 $4.72\times10^{7}$，与输出投影同量级。第二行说明单个嵌入矩阵在 fp32 下连同梯度与两个 Adam 状态共占约 589 MiB，这是小显存设备上词表大小成为硬约束的直接原因。若把 $T$ 从 1024 提到 4096，$R$ 降为 0.51，注意力成为主导项；若把 $V$ 扩到 200000，$R$ 升为 8.1，输出投影成为主导项。

### 例 3：tiktoken 的使用方式

tiktoken 是 OpenAI 开源的分词库，其词表以"字节对到 rank"的映射存储，编码即反复合并 rank 最小的可行对。以下代码展示接口用法，实际 id 序列随库版本变化，不作固定值断言。

```python
import tiktoken

enc = tiktoken.get_encoding("cl100k_base")     # GPT-4 系列使用的编码
text = "Byte-level BPE 不产生未登录词。"
ids = enc.encode_ordinary(text)                # 普通文本，不解析特殊 token
print(enc.n_vocab, len(ids), ids)
print(enc.decode(ids) == text)                 # 字节级编码应严格可逆
print([enc.decode_single_token_bytes(i) for i in ids[:5]])  # 每个 token 的字节串

enc2 = tiktoken.encoding_for_model("gpt-4o")   # 按模型名取编码，此处为 o200k_base
print(enc2.name, len(enc2.encode_ordinary("tokenization")))
```

`get_encoding` 首次调用需要读取本地的 rank 文件，若未缓存则由网络下载，之后离线可用；`encode_ordinary` 把特殊 token 当作普通文本处理，`encode` 则允许用 `allowed_special` 指定需要识别为控制符的字面量。`n_vocab` 包含特殊 token，因此大于合并规则数加 256。`decode_single_token_bytes` 返回该 token 对应的原始字节，可用于确认中文被切成几个字节级 token。若把 `encode_ordinary` 换成 `encode` 而不传 `allowed_special`，遇到 `<|endoftext|>` 这类字面量会抛出异常，这是该库防止特殊 token 被误注入的默认行为。

## 易错点

> [!warning] 以下六条均可在实现或核算中直接检验。
> 1. 认为 BPE 编码给出"最优切分"：它只是按训练顺序复现贪心合并规则，不保证在任何概率模型下概率最大；求最大概率切分需用 Unigram 的 Viterbi。
> 2. 把 50257 当作合并次数：它等于 256 个基础字节、50000 条合并规则与 1 个特殊 token 之和，任意一项改变都会改变词表大小。
> 3. 训练与推理的预切分不一致，例如训练时保留大小写、推理时统一转小写，或对空白做不同的归一化，导致同一文本的切分与训练分布不符。
> 4. 拼接多条短文档时只做 padding 而不插入 EOS 或不做注意力隔离，使模型学到跨文档的虚假依赖；padding 本身也不会阻止注意力关注填充位，必须另加 padding mask。
> 5. 用字符数估算 token 数：UTF-8 下中文每字 3 字节，token 数与字数之比取决于词表覆盖程度，可直接相差 2 至 3 倍。
> 6. 扩大词表后只扩展嵌入矩阵而不训练新行，或扩展后未同步调整输出投影与特殊 token 的 id 分配，导致新 token 的嵌入停留在初始化值。

## 关联笔记

- 前置 [[预备知识-token与嵌入]]：本篇输出的 token id 是嵌入矩阵的行索引，词表大小 $V$ 直接决定嵌入参数量。
- 后续 [[GPT系列架构]]：GPT-1/2/3 的词表规模、byte-level 方案与上下文长度选择均以本篇的压缩率与成本公式为约束。
- 后续 [[从零实现小型GPT指南]]：复现流程的第一步是训练或加载 tokenizer，并要求报告 $V$、$\kappa$ 与平均序列长度。
- 对照 [[BERT与双向编码模型]]：BERT 使用 30000 词的 WordPiece 与 `##` 续接标记，与 byte-level BPE 在 OOV 与可逆性上形成直接对照。
- 后续 [[KV缓存]]：$T$ 既决定注意力的 $O(T^{2})$ 计算，也决定 KV Cache 的线性显存占用，分词压缩率因此同时影响两者。

## 达标检测

- [ ] 对第 2 节的四词语料，独立手算第一轮的 14 个相邻对频次，写出选中的合并与平局规则，并说明换一条平局规则后合并序列如何变化。
- [ ] 写出 $V$、$d$、$L$、$T$ 下输出投影与注意力的每 token 乘加次数，计算 $V=50257$、$d=768$、$L=12$、$T=1024$ 时的比值，误差不超过 0.01。
- [ ] 解释 byte-level BPE 为何不需要 UNK，并推导 $50257=256+50000+1$ 中每一项的来源。
- [ ] 写出 BPE 编码与 WordPiece 编码的算法差异，说明为何 BPE 的切分依赖合并规则的顺序。
- [ ] 用 30 行以内实现 mini BPE，在自造语料上输出合并规则，并正确切分一个训练中未出现的词。
- [ ] 说明特殊 token 与 padding 在嵌入层、注意力掩码、损失函数三处的处理差异，各给出一个遗漏后的具体后果。
- [ ] 指出"词表越大越好"在两个指标上的反例，并给出在固定参数预算下选择 $V$ 的核算步骤。

## 参考来源

- Sennrich et al., "Neural Machine Translation of Rare Words with Subword Units", arXiv:1508.07909 —— 对应本篇第 2 节的 BPE 训练与合并算法、第 3 节的编码流程。
- Radford et al., "Language Models are Unsupervised Multitask Learners", 2019 —— 对应第 4 节的 byte-level BPE、`bytes_to_unicode` 映射与 50257 词表构成。
- tiktoken 官方仓库与文档 —— 对应第 3 节的 rank 合并实现、第 4 节的词表规模，以及例 3 的接口用法。
- Raschka, *Build a Large Language Model (From Scratch)*, 2024, 第 2 章 —— 对应特殊 token、滑动窗口与 batch 构造中 padding 与 mask 的处理。
- d2l.ai《动手学深度学习》子词嵌入章节 —— 对应第 7 节 BPE、WordPiece 与 Unigram 的对比。
- Vaswani et al., "Attention Is All You Need", arXiv:1706.03762 —— 对应第 6 节词表规模与输出投影、注意力计算量的关系。
