跳到主要内容

数据截至 (上游 commit 1acefe89412b)

01 · BPE 算法本体

这一章讲什么: 整个 minbpe 的心脏——base.py 的两个自由函数和 basic.py 的 74 行。读完你会能徒手讲清:BPE 训练在干什么、编码为什么不是查词典而是「重演」、一个词表文件里真正需要存的只有什么。

1. 它要解决的小问题​

LLM 不吃字符串,吃整数序列。怎么把任意文本切成整数序列?

两个朴素方案都有死穴:

  • 按字符切:英文尚可,但 Unicode 字符有十几万个,词表爆炸;且每个汉字、每个字母都各占一个 token,序列太长。
  • 按单词切:词表更爆炸,且任何拼写变体、任何新词都是 OOV(词表外),无法表示。

想要的性质是:常见片段(整个单词、常见词根)占一个 token,生僻片段能一路退回单个字节,任何文本都切得动。 BPE 用「数据压缩」的思路达成了这一点。

2. 直觉:从 256 个字节「长」出词表​

BPE 的训练过程可以想象成焊接:

  1. 把文本编码成 UTF-8 字节。任何文本——中文、emoji、控制符——都变成 0~255 的整数流。初始词表恒为 256 个单字节 token,永远不会有 OOV,这是 "byte-level" 的全部含义(minbpe/basic.py:25-26)。
  2. 数一数当前序列里哪对相邻 token 一起出现得最频繁。
  3. 把这最常见的一对「焊」成一个新 token,发一个新 id(256、257、258……),全序列里凡是出现这对的地方都换成新 id。
  4. 回到第 2 步,直到凑够想要的词表大小。

焊的次数越多,常见词根、整个单词就陆续变成单 token。训练的全部产出是一张合并表 merges:(左id, 右id) -> 新id,一共 vocab_size - 256 条(minbpe/basic.py:21-22)。

编码则是训练的逆用:拿到新文本,先退成字节流,然后反复找「当前序列里、在合并表中出现最早(优先级最高)的那对」,合并之,直到没有一对还在表里。优先级就是合并表里的「出生顺序」——越早被焊出来的对,越优先被合并。

3. 图示:三次合并的微观过程​

用 Wikipedia 的 BPE 词条例子 "aaabdaaabac"(也是仓库的对照测试,tests/test_tokenizer.py:80-107)。文本先变成字节 id 流(a=97, b=98, c=99, d=100),然后逐轮合并:

轮次当前序列最高频相邻对新 token
起点[97, 97, 97, 98, 100, 97, 97, 97, 98, 97, 99]——
1[256, 97, 98, 100, 256, 97, 98, 97, 99](97,97) = aa,4 次256
2[257, 98, 100, 257, 98, 97, 99](256,97) 与 (97,98) 并列 2 次257
3[258, 100, 258, 97, 99](257,98),2 次258

11 个字节被压成 5 个 token。注意第 2 轮的并列:两个对都是 2 次,max() 取迭代序中先遇到的那个——这个细节会在 §6 回来咬人。

4. 原理演示:两个函数 + 两个循环(示意代码)​

下面这段就是 BPE 的全部,与真实实现一一对应,只是去掉了注释和边界处理(# 示意,非源码):

def get_stats(ids):            # 数相邻对频次:{(97,97): 4, ...}
    counts = {}
    for pair in zip(ids, ids[1:]):
        counts[pair] = counts.get(pair, 0) + 1
    return counts

def merge(ids, pair, idx):     # 把序列里所有 pair 替换成新 id
    out, i = [], 0
    while i < len(ids):
        if i < len(ids) - 1 and (ids[i], ids[i+1]) == pair:
            out.append(idx); i += 2        # 命中:写新 id,跳两格
        else:
            out.append(ids[i]); i += 1     # 未命中:照抄
    return out

def train(ids, num_merges):    # 训练:自底向上造表
    merges = {}
    for i in range(num_merges):
        pair = max(get_stats(ids), key=get_stats(ids).get)  # 最高频对
        ids = merge(ids, pair, 256 + i)
        merges[pair] = 256 + i
    return merges

def encode(ids, merges):       # 编码:按表里优先级重演
    while len(ids) >= 2:
        stats = get_stats(ids)
        pair = min(stats, key=lambda p: merges.get(p, float("inf")))
        if pair not in merges:
            break              # 没有一对还在表里,收工
        ids = merge(ids, pair, merges[pair])
    return ids

重点看 encode 里的 min 那一行:训练用 max 找「频次最高」,编码用 min 找「rank 最小(出生最早)」——同一对数据结构,方向相反的两个极值,这就是「训练与编码是同一枚硬币两面」的代码形态。

5. 真实实现​

5.1 两个原子操作:get_stats 与 merge​

minbpe/base.py:13-22 的 get_stats(ids, counts=None):一趟 zip(ids, ids[1:]) 滑窗数对,可选传入已有 dict 就地累加——这个可选参数是给 02 章的多块文本统计准备的。

minbpe/base.py:25-41 的 merge(ids, pair, idx):单趟 while 循环,命中对就写 idx 并 i += 2,否则照抄并 i += 1。注意末尾保护:最后一个位置没有「下一个」,条件里 i < len(ids) - 1 挡住了越界(minbpe/base.py:35)。

5.2 训练:BasicTokenizer.train​

minbpe/basic.py:20-49,就是 §4 示意循环的直译,加三处实在的东西:

  • assert vocab_size >= 256(minbpe/basic.py:21)——256 个字节是地基,不可裁。
  • 每轮顺手把 vocab 也拼出来:vocab[idx] = vocab[pair[0]] + vocab[pair[1]](minbpe/basic.py:42),新 token 的字节串 = 左右两子 token 字节串的拼接。
  • verbose=True 时每轮打印一条合并日志(minbpe/basic.py:44-45),train.py:21 用它演示学习过程。

5.3 编码:BasicTokenizer.encode​

minbpe/basic.py:57-74。UTF-8 编码成字节流后进入 while len(ids) >= 2 循环:每轮全量数对,取合并表里 rank 最小的对合并,查不到任何可合并的对就 break(minbpe/basic.py:69-70)。

5.4 解码:BasicTokenizer.decode​

minbpe/basic.py:51-55,三步走:逐 id 查 vocab 拿字节串 → b"".join 拼起来 → .decode("utf-8", errors="replace")。解码不需要 merges——vocab 里每个 id 已经对应完整的字节串,拼接即还原。

5.5 vocab 是 merges 的推论:Tokenizer._build_vocab​

minbpe/base.py:88-95。基类构造时:

  1. vocab = {idx: bytes([idx]) for idx in range(256)} —— 256 个单字节打底;
  2. 按插入序遍历 merges,逐条拼出每个新 token 的字节串;
  3. 最后把 special tokens 以 UTF-8 编码塞进 vocab(03 章细讲)。

因为 merges 的插入序就是训练时的发放序,子 token 一定先于父 token 存在,所以 vocab[p0] + vocab[p1] 永远查得到。词表因此完全不必存储——这是 §5.6 模型文件能做到极小的原因。

5.6 存取:Tokenizer.save / Tokenizer.load​

save(minbpe/base.py:97-138)写两个文件:

  • .model(给机器):版本行 "minbpe v1"、pattern 一行、special tokens 数量加逐条、merges 逐行一对(minbpe/base.py:104-116)。注意 merges 只写对的两个 id,不写新 id。
  • .vocab(给人看):逐 token 打印,合并得来的 token 显示成 [子0][子1] -> [合并结果] id 的形式(minbpe/base.py:129-138)。

load(minbpe/base.py:140-165)是逆操作,最巧的一处在 minbpe/base.py:158-162:读 merges 时新 id 不来自文件,而是 idx 从 256 起逐行自增——行号即发放序,与训练时的 256 + i 严丝合缝。读完再调 _build_vocab() 重建词表。

6. 关键细节与坑​

  1. encode 的 inf 技巧与终止检测。 min(stats, key=lambda p: self.merges.get(p, float("inf")))(minbpe/basic.py:64):不在表里的对一律得无穷大,自然沉底。当连 min 选出的对都不在表里时,说明无对可合,用一次成员检查 if pair not in self.merges: break 收尾(minbpe/basic.py:69-70)——源码注释专门解释了为什么不能用「key 全是 inf」直接判断(minbpe/basic.py:65-68)。
  2. 并列时合并谁?max() 取「先遇到的」。 §3 的第 2 轮里 (256,97) 与 (97,98) 同为 2 次;max(stats, key=stats.get) 按 dict 插入序返回首个最大者,实际选中 (256,97)——与 Wikipedia 词条选择的 (97,98) 不同。但由于本例结构对称,两条合并路径最终都得到 [258, 100, 258, 97, 99],测试断言照常通过(tests/test_tokenizer.py:100-106)。所以测试注释里 "X=ZY, Y=ab, Z=aa" 的叙述与 minbpe 真实的中间合并表并不一致——这是读这份代码时最容易被带偏的一处(依据:minbpe/basic.py:35 的 max + Python dict 插入序语义)。
  3. 解码对坏数据静默。 errors="replace"(minbpe/basic.py:54)意味着非法字节序列会变成 � 而不抛错——round-trip 只保证「encode 再 decode 还原原文」,不保证「任意 id 序列都能解出有意义文本」。而 BasicTokenizer.decode 遇到未知 id 会直接 KeyError(vocab 查表,minbpe/basic.py:53),与 03 章 RegexTokenizer.decode 的显式 ValueError 行为不同。
  4. .vocab 文件是有损的,不能拿去 load。 很多 token 是半个 UTF-8 序列(比如某个汉字的前两个字节),打印时 errors='replace' 会替换成 �——源码注释明确警告「this also means that we couldn't possibly use .vocab in load()」(minbpe/base.py:122-126)。两个文件一个给机器一个给人,别混用。
  5. 复杂度是实打实的 O(文本长 × 合并数)。 每轮合并都重新全量 get_stats + 全量 merge(minbpe/basic.py:31-39)。教学上这是优点(没有增量统计的心智负担),工程上就是 README.md:143 那条 todo 存在的原因。
  6. merges 的顺序就是语义。 训练按 256 + i 发 id(minbpe/basic.py:37),编码按 min rank 用表(minbpe/basic.py:64),load 按行号重建(minbpe/base.py:158-162)——三处共同依赖「合并表有序」这一件事。任何想给 minbpe 换存储格式的人,都必须保住这个序。

下一章: 02 · regex 预切分与 GPT-4 模式——为什么真实分词器绝不让 BPE 跨过「字母 / 数字 / 标点 / 空白」的边界,以及 GPT-4 那把 regex 刀逐段在切什么。