编辑
2026-11-03
tokenizer
00

目录

基于 Byte Pair Encoding 实现简易 Tokenizer
前置内容回顾
1. Token 不是"字",而是"常见字节序列"
2. BPE 的核心思想:合并高频相邻对
3. 字节级保证:任意文本可编码,无 <unk>
4. 本实现的词表结构
5. 三个核心数据结构
6. 训练与编码的闭环
演示与准备
环境准备
字节基础词表——id 就是字节值
zip(seq, seq[1:]) 生成相邻对
applymerge 的替换效果
Counter.most_common 选出最高频对
b"".join(...) 拼接字节
训练语料长什么样
预估最终规模
训练 tokenizer
1、训练的整体流程
2、准备语料
3、初始化与循环控制
4、统计相邻对频率
5、提前终止:没有可合并的相邻对
6、选出最高频 pair
7、构造新字节串
8、注册新 token:三处登记
9、更新语料
10、递增 id,进入下一轮
11、完整跑一轮的示例
12、训练后能观察到什么
13、训练部分的设计要点小结
14、复杂度与优化空间
小结
编码与解码
1、encode:文本 → token id
2、decode:token id → 文本
3、端到端往返演示
演示 1:训练语料内的文本
演示 2:语料外的文本(含中文)
演示 3:往返一致性验证
演示 4:观察压缩效果
演示 5:查看某个 token 的字节内容
4、复杂度分析
进一步优化
教学实现的低效点
真实 tokenizer 的优化
encode 优化
训练优化
工程级
复杂度对比
教学版为什么"够用"
总结
实现回顾
核心概念清单
复杂度与优化
与真实 tokenizer 的差距
代码实现

从零实现一个字节级 BPE Tokenizer:训练合并规则、编码文本为 token id、解码还原。完成后你会得到一个 512 词表的 Tokenizer,能对任意 Unicode 文本无损编解码——包括中文、emoji、代码,永远不会出现 unk。

基于 Byte Pair Encoding 实现简易 Tokenizer

前置内容回顾

在动手实现之前,先把 BPE 的核心概念和本实现的设计约定梳理清楚。这部分是理解后续代码的地基。

1. Token 不是"字",而是"常见字节序列"

传统直觉里"一个 token 对应一个字符",但 BPE tokenizer 里 token 的粒度是字节序列:它可以是一个字节、半个汉字的 UTF-8 编码片段、一个英文词根、甚至一整个高频词。理解这一点,才能理解为什么 "the" 可能被编成一个 token,而某个生僻汉字却要拆成三个 token。

2. BPE 的核心思想:合并高频相邻对

BPE(Byte Pair Encoding)的算法非常朴素:

  1. 从"每个字节一个 token"开始
  2. 统计语料中所有相邻 token 对的出现频率
  3. 把最高频的一对合并成一个新 token
  4. 重复步骤 2~3,直到词表达到目标大小

每合并一次,词表多一个"更大的常见片段"。经过多轮,t+h→th、th+e→the 这样的链式合并会自然涌现,长词被压缩成少数 token。

3. 字节级保证:任意文本可编码,无 <unk>

基础词表覆盖 全部 256 个字节(id 0255 对应 b'\x00'b'\xff')。任何 Unicode 文本经 UTF-8 编码后,每个字节都落在 0~255 内,因此任何输入都能表示,不存在"未知字符"。这是字节级 BPE 相比字符级/词级分词器的关键优势。

4. 本实现的词表结构

token id 范围含义数量
0 ~ 255单字节 token(基础词表)256
256 ~ 511BPE 合并产生的多字节 token最多 256
合计最多 512

由两个类常量界定:

  • BASE_VOCAB_SIZE = 256:基础词表大小,也是新 token id 的起点
  • MERGE_COUNT = 256:最多合并次数(演示规模;真实模型通常 5 万+)

5. 三个核心数据结构

结构类型作用
vocabDict[int, bytes]id → 字节串,解码时用
_bytes_to_idDict[bytes, int]字节串 → id,反向查找(预留)
mergesDict[Tuple[int,int], int](左id, 右id) → 新id,编码时按顺序应用

关键理解:vocab 回答"token 是什么字节",merges 回答"token 怎么合出来"。merges 的插入顺序 = 合并优先级,是编码正确性的隐含前提。

6. 训练与编码的闭环

  • 训练(_train_merges):统计高频对 → 合并 → 更新语料 → 注册规则,循环直到词表达标或无法再合并
  • 编码(encode):文本 → UTF-8 字节 → 按 merges 顺序逐条应用规则
  • 解码(decode):id → 查 vocab 得字节 → 拼接 → UTF-8 解码

演示与准备

环境准备

只需 Python 3.7+(依赖 dict 保持插入顺序)和标准库,无需第三方包:

python
from collections import Counter from typing import Dict, List, Tuple

字节基础词表——id 就是字节值

python
vocab = {i: bytes([i]) for i in range(256)} print(vocab[0]) # b'\x00' print(vocab[65]) # b'A' ← 65 是 'A' 的 ASCII print(vocab[97]) # b'a' print(vocab[255]) # b'\xff'

一个汉字 "中" 的 UTF-8 编码是 3 个字节:

python
print(list("中".encode("utf-8"))) # [228, 184, 173]

即它会先被表示成 3 个基础 token:228、184、173。单个 228 单独解码不是合法字符,三个拼起来才是 "中"。

zip(seq, seq[1:]) 生成相邻对

统计相邻对是 BPE 的核心操作:

python
seq = [10, 20, 30, 40] print(list(zip(seq, seq[1:]))) # [(10, 20), (20, 30), (30, 40)]

seq[1:] 比 seq 短一个,zip 自动截断到最短,天然处理了最后一个元素的边界,无需手动判断越界。

_apply_merge 的替换效果

python
def _apply_merge(seq, pair, new_id): result, i = [], 0 while i < len(seq): if i + 1 < len(seq) and seq[i] == pair[0] and seq[i + 1] == pair[1]: result.append(new_id) i += 2 # 命中:吃掉两个元素 else: result.append(seq[i]) i += 1 # 未命中:前进一步 return result print(_apply_merge([97, 98, 97, 98, 99], (97, 98), 256)) # [256, 256, 99]

注意它是从左到右、不重叠的贪心替换,且不修改原列表,返回新列表。

Counter.most_common 选出最高频对

python
from collections import Counter c = Counter() for seq in [[116,104,101], [116,104,101], [116,104]]: for a, b in zip(seq, seq[1:]): c[(a, b)] += 1 print(c.most_common(1)) # [((116, 104), 3)] print(c.most_common(1)[0][0]) # (116, 104)

most_common(1)[0][0] 就是"取最高频那一项的键(pair 本身)"的标准写法。

b"".join(...) 拼接字节

vocab 里的值都是 bytes,解码时要无损拼接:

python
parts = [b'\xe4', b'\xb8', b'\xad'] raw = b"".join(parts) # b'\xe4\xb8\xad' print(raw.decode("utf-8")) # '中'

b"" 是空字节串(不是空字符串 ""),bytes.join 要求元素全是 bytes,所以必须用 b""。

训练语料长什么样

本实现用 4 句固定文本训练:

python
train_texts = [ "the quick brown fox jumps over the lazy dog ", "hello world hello world hello world ", "Python is great for machine learning ", "large language model inference engine ", ] corpus = [list(t.encode("utf-8")) for t in train_texts] print(corpus[0][:10]) # [116, 104, 101, 32, 113, 117, 105, 99, 107, 32]

这个语料里 "the"、"hello world" 等片段高频重复,正好能演示 BPE 如何把它们逐步压成更少的 token。

预估最终规模

python
print(256 + 256) # 512 词表上限

但实际可能小于 512——若语料提前"压干"(所有句子只剩 1 个 token),训练会在 if not pair_counts: break 处提前结束。训练后可用 len(tok.merges) 查看实际合并了几轮。


训练 tokenizer

训练是 BPE 的"学习"阶段:从原始文本中统计规律,把高频相邻字节对逐步合并成新 token,最终构建出词表和合并规则。这部分对应 _train_merges() 方法,是理解整个 tokenizer 的核心。

1、训练的整体流程

准备语料(文本 → 字节序列) ↓ 循环最多 MERGE_COUNT 次 1. 边界检查(达到词表上限就停) 2. 统计所有相邻 token 对的出现频率 3. 没有相邻对 → 提前结束 4. 选出最高频的 pair 5. 把 pair 的字节拼接成新字节串 6. 注册新 token(vocab / 反向映射 / merges) 7. 在语料中把该 pair 全部替换成新 id 8. next_id += 1

一句话概括:每轮找出全语料最高频的相邻对,把它合并成一个新 token,然后用新 token 改写语料,进入下一轮。

2、准备语料

python
train_texts = [ "the quick brown fox jumps over the lazy dog ", "hello world hello world hello world ", "Python is great for machine learning ", "large language model inference engine ", ] corpus: List[List[int]] = [ list(text.encode("utf-8")) for text in train_texts ]

每句文本 UTF-8 编码成字节列表,得到"句子的列表,每句是字节列表":

python
corpus = [ [116, 104, 101, 32, 113, ...], # "the quick brown fox..." [104, 101, 108, 108, 111, ...], # "hello world..." ... ]

此时每个字节就是一个基础 token(id = 字节值)。corpus 是可变的、会随合并不断被改写的工作数据——这是训练的关键:BPE 不是一次性扫描原文,而是每轮都在"压缩后的语料"上继续统计。

3、初始化与循环控制

python
next_id = self.BASE_VOCAB_SIZE # 从 256 开始 for _ in range(self.MERGE_COUNT): # 最多 256 次 if next_id >= self.BASE_VOCAB_SIZE + self.MERGE_COUNT: # 256+256=512 break
  • next_id:下一个要分配的新 token id,从 256 起。
  • range(self.MERGE_COUNT):硬上限 256 次迭代。
  • 边界检查 next_id >= 512:防御性兜底。正常流程下 range(256) 只让 next_id 到 511,不会触发,但子类改动常量关系时能保护。

实际迭代次数由两个终止条件共同决定:

终止条件触发时机常见程度
range 耗尽跑满 256 轮语料丰富时
pair_counts 为空语料无法再合并教学小语料下最常见

所以实际迭代次数 = min(MERGE_COUNT, 语料能被合并的次数),最终词表大小可能小于 512。

如果语料足够丰富,256 次都没触发前面两个 break,那么 range(256) 跑完自然结束。

当所有句子都只剩 1 个 token(或语料为空)时,统计不到任何相邻对,pair_counts 为空,循环提前结束。这才是实际中最常见的提前终止原因。教学语料只有 4 句,能被合并的次数有限,很可能远不到 256 次就把语料"压榨干"了——比如每句都合成了少数几个片段后,再也找不到频率 ≥1 的相邻对。

4、统计相邻对频率

python
pair_counts: Counter = Counter() for seq in corpus: for a, b in zip(seq, seq[1:]): pair_counts[(a, b)] += 1

对每一句 seq:

  • zip(seq, seq[1:]) 生成所有相邻对 (seq[i], seq[i+1])
  • 用 (a, b) 元组作键,计数 +1

统计的是整个语料中所有相邻对的全局频率。例如 (116, 104)("th")在 4 句里共出现 8 次,则 pair_counts[(116, 104)] = 8。

这里用 Counter 而非普通 dict 的原因是:新键做 += 自动从 0 开始,不会 KeyError。

一个实现细节:这里每轮都全量重扫语料,是 O(语料总长) 的操作。真实实现会用增量统计只更新受影响位置,后文会讨论。

5、提前终止:没有可合并的相邻对

python
if not pair_counts: break

如果所有句子都只剩 1 个 token,zip(seq, seq[1:]) 对每个序列都产出空,Counter 为空(布尔值为 False),训练无法继续,提前退出。

这是"语料被压干"的正常终止。教学语料只有 4 句,很可能远不到 256 轮就触发。比如每句都合成了少数片段后再也找不到频率 ≥1 的相邻对。

6、选出最高频 pair

python
best_pair = pair_counts.most_common(1)[0][0]

逐层拆解:

  • most_common(1) → [((a, b), count)]:列表,含最高频的一项
  • [0] → ((a, b), count):取出这个 (键, 次数) 元组
  • [0] → (a, b):取出 pair 本身,丢掉次数

例如得到 best_pair = (116, 104)。

并列时的行为:most_common 在次数相同时按插入顺序返回,即选先出现的那个 pair。这保证训练是确定性的——同样输入总得到同样结果。

7、构造新字节串

python
new_bytes = self.vocab[best_pair[0]] + self.vocab[best_pair[1]]
  • self.vocab[best_pair[0]]:左 token 对应的字节串
  • self.vocab[best_pair[1]]:右 token 对应的字节串
  • +:字节串拼接

例如 best_pair = (116, 104),vocab[116] = b't'、vocab[104] = b'h',则 new_bytes = b'th'。

关键点:token 对应的字节串可能是多字节的(之前合并产生的),所以这里能拼出更长的片段。例如第二轮合并 (256, 101) 时,vocab[256] = b'th'、vocab[101] = b'e',得到 b'the'。这就是链式叠加在训练侧的体现。

8、注册新 token:三处登记

python
self.vocab[next_id] = new_bytes # ① id → 字节串 self._bytes_to_id[new_bytes] = next_id # ② 字节串 → id self.merges[best_pair] = next_id # ③ 合并规则

三处各司其职:

结构键 → 值用途用在哪
vocabid → 字节串解码时查表拼字节decode
_bytes_to_id字节串 → id反向查找(预留加速)当前未实际使用
merges(左id, 右id) → 新id记录"如何合并"encode

merges 的插入顺序至关重要:它是 dict,Python 3.7+ 保持插入顺序,encode 里 for pair, new_id in self.merges.items() 就按"训练产生的先后"应用规则——这正是 BPE 编码的正确优先级。先学 t+h→th,再学 th+e→the,顺序不能反。

9、更新语料

python
corpus = [self._apply_merge(seq, best_pair, next_id) for seq in corpus]

把每一句里的 best_pair 都替换成 next_id,得到新语料(重新赋值,不原地修改)。

为什么必须更新语料?因为下一轮的频率统计要基于"合并后"的序列。举例:

原句: [116, 104, 101] ("the" 的字节) 合并 (116,104)→256 后: [256, 101] 下一轮统计的就是 (256, 101),而不是 (104, 101)

语料被逐轮"压缩",合并规则层层叠加,最终能合出 b'the'、b'hello' 等片段。如果不更新语料,每轮都会重复统计原始相邻对,链式合并就不可能发生。

10、递增 id,进入下一轮

python
next_id += 1

为下一个新 token 准备编号,循环回到顶部。

11、完整跑一轮的示例

假设某一轮语料是 [[97, 98, 97, 98, 99]](字节 a b a b c),next_id = 256:

步骤内容
统计相邻对(97,98):2、(98,97):1、(98,99):1
best_pair(97, 98)(频率 2 最高)
new_bytesb'a' + b'b' = b'ab'
登记vocab[256]=b'ab'、_bytes_to_id[b'ab']=256、merges[(97,98)]=256
更新语料[97,98,97,98,99] → [256, 256, 99]
next_id257

下一轮在 [[256, 256, 99]] 上统计,可能合并 (256, 256) → b'abab',如此层层推进。

12、训练后能观察到什么

python
tok = SimpleBPETokenizer() print(tok.vocab_size) # 实际词表大小,如 436 print(len(tok.merges)) # 实际合并次数 = 实际迭代轮数 print(tok.vocab[256]) # 第一个合并 token 的字节,如 b'th' print(tok.vocab[300]) # 后面某个 token,可能已是较长片段

因为每轮恰好新增一条 merges 记录,len(tok.merges) 就是实际训练了几轮:

  • 等于 256:跑满上限
  • 小于 256:语料提前压干

vocab[i](i ≥ 256)的字节串越长,通常说明它叠加了越多层合并。

13、训练部分的设计要点小结

设计点说明
每轮只合并一个 pair,但全局替换标准 BPE 做法:一次合并产生一个 token,作用到整个语料
语料逐轮压缩是链式合并能发生的前提;不更新语料则规则无法叠加
两个终止条件range 耗尽 + pair_counts 为空,后者在小语料下更常见
merges 插入顺序 = 优先级编码正确性的隐含前提,依赖 Python 3.7+ dict 保序
Counter 自动初始化新键 += 从 0 开始,避免 KeyError
复杂度每轮 O(语料总长),共 O(M · 语料总长),教学规模足够

14、复杂度与优化空间

训练的核心开销在两处全量操作:

  • 每轮全量重扫语料统计相邻对:O(语料总长)
  • 每轮全量重写语料做替换:O(语料总长)

共 M 轮,总复杂度 O(M · 语料总长)。真实 tokenizer 的优化方向包括:

  • 增量统计:合并后只更新受影响位置的相邻对计数,而非全量重扫
  • 优先队列维护当前最高频 pair,避免每轮 most_common 排序
  • 预分词成词块,块内独立训练,减少跨块无意义配对,并支持并行
  • 低频过滤 / count-min sketch 处理超大规模语料

这些优化不改变 BPE 的语义,只压常量和渐进复杂度,将在后续"优化讨论"部分展开。

小结

训练部分是一个"统计 → 合并 → 改写语料"的循环:每轮用 Counter + zip(seq, seq[1:]) 统计全语料相邻对频率,most_common(1)[0][0] 选出最高频 pair,拼接字节得新 token,登记进 vocab / _bytes_to_id / merges 三处,再用 _apply_merge 把语料中所有该 pair 替换成新 id。语料随轮次被逐步压缩,链式合并因此得以发生;merges 的插入顺序承载了合并优先级。训练在跑满 256 轮或语料压干时结束,len(merges) 反映实际轮数,最终词表规模在 256~512 之间。


编码与解码

训练完成后,tokenizer 就有了可用的词表和合并规则。这一部分讲清楚"文本 ↔ token id"的双向链路,跑一个端到端往返示例,并讨论复杂度与真实实现的优化。

1、encode:文本 → token id

python
def encode(self, text: str) -> List[int]: ids = list(text.encode("utf-8")) for pair, new_id in self.merges.items(): ids = self._apply_merge(ids, pair, new_id) return ids

两步:

第 1 步:UTF-8 编码成字节序列

python
ids = list(text.encode("utf-8"))

text.encode("utf-8") 返回 bytes,list(...) 把每个字节转成 0~255 的整数——即基础 token id。例如 "the" → [116, 104, 101]。

这一步永远成功,因为任何 Unicode 文本都有 UTF-8 表示,且字节值必然在 0~255 内(基础词表全覆盖)。这是"字节级 BPE 无 <unk>"的直接体现。

第 2 步:按合并顺序逐条应用规则

python
for pair, new_id in self.merges.items(): ids = self._apply_merge(ids, pair, new_id)

self.merges 是训练时按产生顺序插入的 dict,遍历顺序 = 合并优先级。每轮用 _apply_merge 把序列中所有匹配的 pair 替换成 new_id。

关键:规则可以链式叠加。 后一条规则能作用在前一条规则的产物上,因为每轮都更新了 ids。假设训练学到:

python
merges = { (116, 104): 256, # t+h → th (256, 101): 257, # th+e → the }

编码 "the",初始 [116, 104, 101]:

轮次规则ids
初始—[116, 104, 101]
1(116,104)→256[256, 101]
2(256,101)→257[257]

最终 "the" 被编成一个 token [257],经历了两次合并叠加。token 257 的"血统"里有 3 个基础字节。

顺序为什么不能反

如果 (256,101)→257 排在前面执行,此时 ids 里还没有 256,匹配不到;等 256 产生后,这条规则已经用过了,链就断了:

python
# 顺序颠倒 merges = {(256,101): 257, (116,104): 256} # 编码 "the" 得到 [256, 101],而不是 [257]

所以 merges 的插入顺序本身承载算法语义,依赖 Python 3.7+ dict 保序。

不是所有 token 都经过多次合并

准确说,最终每个 token 可能经历 0 次、1 次或多次合并:

  • 0 次:未参与任何合并的基础字节 token(0~255)
  • 1 次:两个基础字节直接合成,如 "th"→256,若后续没有规则再把 256 合进去
  • 多次:链式叠加产物,如 257、259

2、decode:token id → 文本

python
def decode(self, ids: List[int]) -> str: raw_bytes = b"".join(self.vocab[i] for i in ids) return raw_bytes.decode("utf-8", errors="replace")

第 1 步:查表拼字节

python
b"".join(self.vocab[i] for i in ids)

每个 id 查 vocab 得到对应字节串,用空字节串 b"" 拼接成完整字节流。b"" 是 bytes 字面量(不是 ""),因为 vocab 的值都是 bytes,bytes.join 要求元素全是 bytes。

python
ids = [228, 184, 173] # "中" 的三个基础 token parts = [b'\xe4', b'\xb8', b'\xad'] b"".join(parts) # b'\xe4\xb8\xad'

第 2 步:UTF-8 解码

python
raw_bytes.decode("utf-8", errors="replace")

把字节流按 UTF-8 还原成文本。errors="replace" 是容错:若传入不完整/非法字节序列,用替换符 � 代替而非抛异常。

decode 不需要 merges

注意 decode 完全不用 merges:每个 id 的最终字节已经完整存在 vocab 里。合并规则只在"压缩"(encode)时需要,解压直接查最终字节即可。

方法依赖方向
encodemerges(按顺序应用)文本 → id,压缩
decodevocab(查表拼接)id → 文本,解压

这体现一个设计原则:vocab 是信息的最终形态,merges 是达成它的过程记录。

3、端到端往返演示

训练后跑一遍完整链路,验证"编码再解码能还原原文"。

演示 1:训练语料内的文本

python
tok = SimpleBPETokenizer() text = "the quick brown fox" ids = tok.encode(text) print(ids) # 例如 [257, 32, 113, 117, 105, 99, 107, ...] print(tok.decode(ids)) # "the quick brown fox"

"the" 很可能被压成一个 token(257),而较少见的片段仍是多个 token。解码后与原文完全一致。

演示 2:语料外的文本(含中文)

python
text = "你好,世界" ids = tok.encode(text) print(ids) # 大多是 228~233 等原始字节 id print(tok.decode(ids)) # "你好,世界"

由于训练语料没有中文,BPE 学不到中文的合并片段,编码结果接近"逐字节"。但依然能正确编解码——字节级覆盖保证任何文本都不丢信息,只是压缩率低(token 数多)。

演示 3:往返一致性验证

python
for text in ["the quick brown fox", "hello world", "你好,世界", "🙂 emoji"]: ids = tok.encode(text) restored = tok.decode(ids) print(repr(text), len(ids), restored == text) # 'the quick brown fox' ... True # 'hello world' ... True # '你好,世界' ... True # '🙂 emoji' ... True

所有文本都 restored == text,这就是字节级 BPE 的无损保证。

演示 4:观察压缩效果

python
for text in ["the quick brown fox", "hello world", "xyzxyzxyz"]: print(text, "→", len(tok.encode(text)), "tokens") the quick brown fox → 1 tokens hello world → 1 tokens xyzxyzxyz → 9 tokens

训练语料里高频的 "the"、"hello world" 相关片段 token 数明显少;语料外的 "xyzxyzxyz" 几乎逐字节,token 数接近字符数。这直观展示了 BPE 的"常见片段压缩"特性。

注意,quick brown fox这些对虽然全局可能只出现一次,但它们彼此之间会竞争——每轮选一个合并。合并后新 token 又和邻居形成新的对,继续被合并。只要训练轮数足够,整句会被逐步压成一个 token。

换句话说:"出现一次"降低的是"被优先选中的概率",但不会阻止它在后续轮次被合并。当语料小、轮数多时,低频对最终也会被合并掉。

演示 5:查看某个 token 的字节内容

python
for i in range(256, min(tok.vocab_size, 266)): print(i, tok.vocab[i]) # 如 256 b'th'、257 b'the'、...

字节串越长,通常说明叠加了越多层合并(不严格等于次数,因为每层左右长度可能不等)。


4、复杂度分析

设:

  • n = 输入文本字节长度(初始 token 数)
  • M = 合并规则数(≤ MERGE_COUNT = 256)

encode:O(M · n)

python
for pair, new_id in self.merges.items(): # M 条 ids = self._apply_merge(ids, pair, new_id) # 每条 O(len(ids)) ≤ O(n)

最坏情况(每条规则几乎不缩短序列,比如都不匹配)是 O(M · n)。序列在合并中会变短,但上界按 M·n 算。

以 M=256、文本 1000 字节计,约 25.6 万次操作——教学够用,但暴露低效点:每条规则都把整个 ids 重扫一遍,即使多数位置根本不匹配。

空间:O(n),每轮 _apply_merge 新建列表,旧列表丢弃,峰值 O(n)。

decode:O(n)

一次查表 + 一次 join + 一次 UTF-8 解码,线性。

训练:O(M · 语料总长)

每轮全量重扫语料统计 + 全量重写语料替换,共 M 轮。


进一步优化

教学实现的低效点

问题说明
每条规则全量重扫256 条 × 全文,多数规则对多数位置不匹配,纯浪费
每轮新建列表大量临时对象和 GC 压力
不考虑位置规则 (a,b) 只在有 a,b 相邻处才匹配,却仍扫全文
不利用索引从头线性找,没有"哪里出现过这个 pair"的信息

真实 tokenizer 的优化

核心思想:不改变 BPE 语义,只压常量和渐进复杂度。

encode 优化

1. rank + 优先队列:O(n log n)

真实 BPE(GPT-2、tiktoken)给每条 merge 规则分配 rank(优先级序号)。编码时不再"逐条规则扫全文",而是反复找当前序列中 rank 最小(优先级最高)的相邻对并合并。用优先队列维护所有相邻对的 (rank, 位置):

  • 取出 rank 最小的对,合并
  • 只更新受影响位置的相邻对(被合并处的左右邻居)
  • 总复杂度约 O(n log n)

对比 O(M·n):n=1000、M=256 时,25.6 万 vs 约 1 万,n、M 越大优势越明显。

2. 预分词(pre-tokenization)

GPT-2 先按正则把文本切成词块("Hello world" → ["Hello", " world"]),每块独立做 BPE。好处:

  • 每块很短,复杂度从"全文 × 规则"降到"Σ(块长 × 规则)"
  • 块可缓存:相同词块直接复用结果

3. 缓存

python
if text in cache: return cache[text]

自然语言重复度高,常见片段命中率极高,摊还接近 O(1)。tiktoken 更进一步,把常见"词块 → token 序列"做成预计算缓存表。

4. 紧凑数据结构

  • 数组 + 双向链表表示序列,合并 O(1) 改指针,避免每轮重建
  • 哈希表记录"pair → 出现位置集合",只处理真正出现处
  • 把 (左id, 右id) 编码成单个 32 位整数,方便哈希

训练优化

1. 增量统计

初始统计一次所有 pair 频率;合并后只更新受影响位置的相邻对计数(被合并位置的左右邻居),而非全量重扫。

2. 优先队列维护最高频 pair

避免每轮 most_common 全排序,用堆 O(log m) 取最大。

3. 预分词 + 并行

语料先切成词块,块内独立统计,减少跨块无意义配对;统计阶段按语料分片多线程/多进程并行,再合并计数器。

4. 低频过滤 / 近似结构

低频 pair 几乎不会被选中,可用阈值过滤;超大规模语料用 count-min sketch 等近似频率统计。

工程级

  • tiktoken 核心用 Rust,比纯 Python 快一个数量级以上
  • SIMD / 位运算加速字节处理
  • 分层算法改进:SentencePiece/Unigram(概率模型 + Viterbi)、WordPiece(似然增益 + 贪心最长匹配)

复杂度对比

阶段教学实现真实优化后
encodeO(M·n)O(n log n)(堆)或近 O(n)(缓存命中)
每轮训练统计O(语料总长)O(受影响位置)(增量)
每轮找最大O(m log m) 全排序O(log m) 堆
缓存无有,常见片段 O(1)

(m = 不同 pair 数,n = 序列长,M = 规则数)

教学版为什么"够用"

  • M 只有 256(真实 5 万+)
  • 输入短、语料小
  • 目的是演示算法逻辑

它把 BPE 的语义表达得很清楚:按优先级逐条应用、链式叠加、贪心不重叠。真实优化的核心——rank+堆、预切分、缓存、增量统计——都在不改变这个语义的前提下提速。


总结

实现回顾

这个 SimpleBPETokenizer 用约 130 行完成了 BPE 的完整闭环:

模块职责关键点
__init__建基础词表、训练0~255 字节 token
_train_merges学习合并规则统计→合并→改写语料,链式叠加
_apply_merge执行一次合并双指针贪心、不重叠、返回新列表
encode文本 → id按 merges 顺序逐条应用
decodeid → 文本查 vocab 拼字节 + UTF-8 解码
vocab_size词表大小@property 实时 len(vocab)

核心概念清单

  • Token 不是字,是字节序列:可长可短,由合并规则决定
  • BPE = 合并高频相邻对:反复统计、合并、改写语料
  • 字节级保证无 <unk>:256 基础字节覆盖一切 Unicode
  • vocab 说"是什么",merges 说"怎么合":decode 只用前者,encode 依赖后者
  • merges 插入顺序 = 合并优先级:依赖 dict 保序,是正确性前提
  • 链式叠加:一个 token 可经历 0/1/多次合并,取决于命中的依赖链

复杂度与优化

  • 教学版 encode O(M·n),训练 O(M·语料长),清晰但低效
  • 真实优化:rank + 优先队列(O(n log n))、预分词、缓存、增量统计、Rust 实现
  • 优化不改变 BPE 语义,只压常数和渐进复杂度

与真实 tokenizer 的差距

维度教学版真实(GPT-2/tiktoken)
预分词无正则切词块
规则来源4 句固定文本海量语料
词表大小5125 万~10 万
编码策略逐条规则全量扫rank + 堆 / 缓存
实现语言PythonRust/C++
速度教学够用生产级

这段实现用最少的代码讲清了 BPE 的全貌:字节基础词表 → 统计高频相邻对 → 合并成新 token → 按合并顺序贪心编码 → 拼接字节解码。它的灵魂是"字节级无损 + 高频片段压缩",它的骨架是 vocab / merges / _apply_merge 三件套。理解了它,就理解了 GPT 类模型分词器的核心原理;而真实实现的优化(rank、预切分、缓存、增量统计)都是在同一语义上的工程加速。

代码实现

py
from collections import Counter from typing import List,Dict, Tuple class SimpleBPETokenizer: BASE_VOCAB_SIZE = 256 # 因为一个字节有 8 位,取值 0~255 共 256 种,必须全部覆盖才能保证任意文本都能编码(无 <unk>)。这是字节级 BPE 的硬性要求,通常不可改。 MERGE_COUNT = 256 # 训练循环最多执行多少次 BPE 合并,即最多产生多少个"多字节 token"。 这里只用 4 句训练文本,256 次合并足够演示,再合并也没有足够的高频对可用 def __init__(self): # vocab:token_id → 字节串 的映射。初始时 id 0~255 分别对应字节 b'\x00' ~ b'\xff'。 # merges:记录合并规则,(左token_id, 右token_id) → 新token_id。 # _bytes_to_id:反向映射 字节串 → token_id,用于加速编码(注释说"加速",但当前 encode 实际没用到它,属于预留/教学展示)。 self.vocab: Dict[int, bytes] = {i: bytes([i]) for i in range(self.BASE_VOCAB_SIZE)} self.merges: Dict[Tuple[int, int], int] = {} self._bytes_to_id: Dict[bytes, int] = {v: k for k, v in self.vocab.items()} # 用少量样本训练合并规则 self._train_merges() @property def vocab_size(self) -> int: return len(self.vocab) def _train_merges(self): """ 用固定样本文本训练 BPE 合并规则。 流程: 1. 将训练文本转为字节序列 2. 统计相邻字节对的出现频率 3. 找到最高频的对,合并为新 token 4. 重复直到达到目标词表大小 :return: """ train_texts = [ "the quick brown fox jumps over the lazy dog ", "hello world hello world hello world ", "Python is great for machine learning ", "large language model inference engine ", ] """ 准备语料(转字节序列) 1. 边界检查(达到词表上限就停) 2. 统计所有相邻 token 对的出现频率 3. 没有相邻对 → 提前结束 4. 选出最高频的 pair 5. 把 pair 的字节拼接成新字节串 6. 注册新 token(vocab / 反向映射 / merges) 7. 在语料中把该 pair 全部替换成新 id 8. next_id += 1 """ # 把 4 句训练文本各自 UTF-8 编码成字节列表 corpus: List[List[int]] = [ list(text.encode("utf-8")) for text in train_texts ] next_id = self.BASE_VOCAB_SIZE for _ in range(self.MERGE_COUNT): if next_id >= self.BASE_VOCAB_SIZE + self.MERGE_COUNT: # 1. 边界检查(达到词表上限就停) break # 2. 统计所有相邻 token 对的出现频率 pair_counts: Counter = Counter() # 空计数器 for seq in corpus: for a, b in zip(seq, seq[1:]): pair_counts[(a, b)] += 1 if not pair_counts: # 当所有句子都只剩 1 个 token(或语料为空)时,统计不到任何相邻对,pair_counts 为空,循环提前结束。这才是实际中最常见的提前终止原因。 break best_pair = pair_counts.most_common(1)[0][0] # most_common(1) → [((a, b), count)],列表,取最高频的一项 # [0] → ((a, b), count),取出这个元组 # [0] → (a, b),取出 pair 本身,丢掉 count new_bytes = self.vocab[best_pair[0]] + self.vocab[best_pair[1]] self.vocab[next_id] = new_bytes self._bytes_to_id[new_bytes] = next_id self.merges[best_pair] = next_id corpus = [self._apply_merge(seq, best_pair, next_id) for seq in corpus] next_id += 1 @staticmethod def _apply_merge(seq: List[int], pair: Tuple[int, int], new_id: int) -> List[int]: """ 将 seq 中所有相邻的 pair 替换为 new_id。 """ result = [] i = 0 while i < len(seq): if i + 1 < len(seq) and pair[0] == seq[i] and pair[1] == seq[i + 1]: result.append(new_id) i += 2 else: result.append(seq[i]) i += 1 return result def encode(self, text: str) -> List[int]: """ 将文本编码为 token id 列表。 步骤: 1. UTF-8 编码 → 字节序列(每字节一个 base token) 2. 贪心地应用合并规则(按训练顺序) """ ids = list(text.encode("utf-8")) for pair, new_id in self.merges.items(): ids = self._apply_merge(ids, pair, new_id) return ids def decode(self, ids: List[int]) -> str: """ 将 token id 列表解码为文本。 直接查词表拼接字节,再 UTF-8 解码。 """ raw_bytes = b"".join([self.vocab[id] for id in ids]) # 每个 token id 查词表得到对应的字节串,把这些字节串拼成一个完整字节流 raw_bytes(类型 bytes) return raw_bytes.decode("utf-8", errors="replace") # 把字节流按 UTF-8 规则解码成文本 str if __name__ == '__main__': tok = SimpleBPETokenizer() text = "Hello World" ids = tok.encode(text) decoded = tok.decode(ids) print(f"原文: {text!r}") print(f"Token IDs: {ids}") print(f"词表大小: {tok.vocab_size}") print(f"解码还原: {decoded!r}") assert decoded == text, f"解码不一致: {decoded!r} != {text!r}" # 字节级覆盖 text2 = "你好世界" ids2 = tok.encode(text2) assert tok.decode(ids2) == text2, "中文 round-trip 失败" print(f"\n中文 round-trip OK: {text2!r} → {ids2} → {tok.decode(ids2)!r}") print("\n✅ step01_tokenizer 通过")

本文作者:Valkyr

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!