CS336（一）：Tokenizer 与 BPE

最近在整理 Stanford CS336《Language Modeling from Scratch》的学习笔记，也顺便把其中一些值得单独记下来的内容重新梳理一下。

如果从一个语言模型真正接收输入的地方开始看，首先遇到的并不是 Transformer，而是 Tokenizer。我们输入的是自然语言，但模型实际处理的是一串 token ID，因此文本进入模型之前，先要经过一次从自然语言到 token 序列的转换。

问题也就落到了分词上：什么样的文本片段应该被看作一个 token？字符、字节，还是更长的文本片段？不同选择会直接影响词表大小和序列长度。字符分词、UTF-8 字节分词、正则分词以及 BPE，基本都在处理这个问题。

1. 字符分词

最直接的做法是给每个字符分配一个 token。例如：

hello
→ h | e | l | l | o

这种方法的问题主要在词表。不同字符在训练语料中的出现频率差异很大。数字、字母等字符会频繁出现，而一些生僻字符、特殊符号或者 Emoji 可能很少出现。如果每个字符都占据一个独立的词表 slot，就会存在大量利用率很低的词表项。

所以这里真正的问题不是字符编号本身，而是需要覆盖的字符种类多，而且很多字符非常低频。

2. UTF-8 字节分词

另一种方式是先把字符串编码成 UTF-8，再按字节进行切分。一个字节只有 256 种可能，因此基础词表固定为：

这样不再需要为不同字符单独维护词表项。无论输入是英文、中文还是特殊符号，只要能编码成 UTF-8，就都能继续拆成字节表示。但这样做的代价是序列会明显变长，英文字符通常只占一个字节，而中文字符通常需要多个 UTF-8 字节。原来一个字符对应一个 token，现在可能对应多个 token。

可以用下面这个值表示分词后的压缩程度：

字节分词中一个字节对应一个 token，因此压缩比为 1。

也就是说，字节分词虽然把词表固定在 256，但并没有压缩原始字节序列。序列变长后，标准 Attention 的 $O(n^2)$ 计算也会跟着增加。

3. 正则分词

还可以直接用正则表达式对文本进行切分，例如分离连续字母、数字和其他字符。相比逐字符或逐字节处理，这种方式可以一次保留更长的文本片段，同一段文本需要的 token 数量会下降。

问题是，如果把不同文本片段都作为独立 token，词表会随着语料不断增长，很难提前限定上限。同时，训练阶段没有出现过的新词也无法直接映射到已有 token。所以这类方案虽然能缩短序列，但会把压力重新转移到 Vocabulary 上。

4. BPE

BPE（Byte Pair Encoding）不再提前规定最终应该按字符还是按单词切分，而是直接从训练语料里学习哪些片段值得组合。

核心算法很简单：

1. 统计当前语料中所有相邻 token pair；

2. 找出出现频率最高的一对；

3. 将它们合并成一个新的 token；

4. 把新 token 加入 Vocabulary；

5. 在新的 token 序列上继续统计；

6. 重复执行，直到达到设定的最大词表大小。

例如当前序列为：

a | b | a | b | a | b

相邻 pair 的频率为：

(a, b) → 3
(b, a) → 2

如果 (a, b) 是当前最高频的组合，就加入：

a + b → ab

原来的序列变为：

ab | ab | ab

新生成的 ab 还可以继续参与下一轮合并。

因此，随着 Merge 不断进行，常见文本片段更容易逐渐组合成一个较长的 token，而低频片段会保持更细的切分。

BPE 的训练过程本质上就是不断学习 Merge Rule，直到词表达到目标大小。

相比直接规定一个 token 必须对应字符或单词，BPE 的分割粒度由训练语料本身决定。