从零实现一个字节级 BPE Tokenizer:训练合并规则、编码文本为 token id、解码还原。完成后你会得到一个 512 词表的 Tokenizer,能对任意 Unicode 文本无损编解码——包括中文、emoji、代码,永远不会出现 unk。
在动手实现之前,先把 BPE 的核心概念和本实现的设计约定梳理清楚。这部分是理解后续代码的地基。
传统直觉里"一个 token 对应一个字符",但 BPE tokenizer 里 token 的粒度是字节序列:它可以是一个字节、半个汉字的 UTF-8 编码片段、一个英文词根、甚至一整个高频词。理解这一点,才能理解为什么 "the" 可能被编成一个 token,而某个生僻汉字却要拆成三个 token。
BPE(Byte Pair Encoding)的算法非常朴素:
每合并一次,词表多一个"更大的常见片段"。经过多轮,t+h→th、th+e→the 这样的链式合并会自然涌现,长词被压缩成少数 token。
<unk>基础词表覆盖 全部 256 个字节(id 0255 对应 b'\x00'b'\xff')。任何 Unicode 文本经 UTF-8 编码后,每个字节都落在 0~255 内,因此任何输入都能表示,不存在"未知字符"。这是字节级 BPE 相比字符级/词级分词器的关键优势。
| token id 范围 | 含义 | 数量 |
|---|---|---|
| 0 ~ 255 | 单字节 token(基础词表) | 256 |
| 256 ~ 511 | BPE 合并产生的多字节 token | 最多 256 |
| 合计 | 最多 512 |
由两个类常量界定:
BASE_VOCAB_SIZE = 256:基础词表大小,也是新 token id 的起点MERGE_COUNT = 256:最多合并次数(演示规模;真实模型通常 5 万+)| 结构 | 类型 | 作用 |
|---|---|---|
vocab | Dict[int, bytes] | id → 字节串,解码时用 |
_bytes_to_id | Dict[bytes, int] | 字节串 → id,反向查找(预留) |
merges | Dict[Tuple[int,int], int] | (左id, 右id) → 新id,编码时按顺序应用 |
关键理解:vocab 回答"token 是什么字节",merges 回答"token 怎么合出来"。merges 的插入顺序 = 合并优先级,是编码正确性的隐含前提。
_train_merges):统计高频对 → 合并 → 更新语料 → 注册规则,循环直到词表达标或无法再合并encode):文本 → UTF-8 字节 → 按 merges 顺序逐条应用规则decode):id → 查 vocab 得字节 → 拼接 → UTF-8 解码只需 Python 3.7+(依赖 dict 保持插入顺序)和标准库,无需第三方包:
pythonfrom collections import Counter
from typing import Dict, List, Tuple
pythonvocab = {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 个字节:
pythonprint(list("中".encode("utf-8"))) # [228, 184, 173]
即它会先被表示成 3 个基础 token:228、184、173。单个 228 单独解码不是合法字符,三个拼起来才是 "中"。
zip(seq, seq[1:]) 生成相邻对统计相邻对是 BPE 的核心操作:
pythonseq = [10, 20, 30, 40]
print(list(zip(seq, seq[1:])))
# [(10, 20), (20, 30), (30, 40)]
seq[1:] 比 seq 短一个,zip 自动截断到最短,天然处理了最后一个元素的边界,无需手动判断越界。
_apply_merge 的替换效果pythondef _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 选出最高频对pythonfrom 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,解码时要无损拼接:
pythonparts = [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 句固定文本训练:
pythontrain_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。
pythonprint(256 + 256) # 512 词表上限
但实际可能小于 512——若语料提前"压干"(所有句子只剩 1 个 token),训练会在 if not pair_counts: break 处提前结束。训练后可用 len(tok.merges) 查看实际合并了几轮。
训练是 BPE 的"学习"阶段:从原始文本中统计规律,把高频相邻字节对逐步合并成新 token,最终构建出词表和合并规则。这部分对应 _train_merges() 方法,是理解整个 tokenizer 的核心。
准备语料(文本 → 字节序列) ↓ 循环最多 MERGE_COUNT 次 1. 边界检查(达到词表上限就停) 2. 统计所有相邻 token 对的出现频率 3. 没有相邻对 → 提前结束 4. 选出最高频的 pair 5. 把 pair 的字节拼接成新字节串 6. 注册新 token(vocab / 反向映射 / merges) 7. 在语料中把该 pair 全部替换成新 id 8. next_id += 1
一句话概括:每轮找出全语料最高频的相邻对,把它合并成一个新 token,然后用新 token 改写语料,进入下一轮。
pythontrain_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 编码成字节列表,得到"句子的列表,每句是字节列表":
pythoncorpus = [
[116, 104, 101, 32, 113, ...], # "the quick brown fox..."
[104, 101, 108, 108, 111, ...], # "hello world..."
...
]
此时每个字节就是一个基础 token(id = 字节值)。corpus 是可变的、会随合并不断被改写的工作数据——这是训练的关键:BPE 不是一次性扫描原文,而是每轮都在"压缩后的语料"上继续统计。
pythonnext_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 的相邻对。
pythonpair_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(语料总长) 的操作。真实实现会用增量统计只更新受影响位置,后文会讨论。
pythonif not pair_counts:
break
如果所有句子都只剩 1 个 token,zip(seq, seq[1:]) 对每个序列都产出空,Counter 为空(布尔值为 False),训练无法继续,提前退出。
这是"语料被压干"的正常终止。教学语料只有 4 句,很可能远不到 256 轮就触发。比如每句都合成了少数片段后再也找不到频率 ≥1 的相邻对。
pythonbest_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。这保证训练是确定性的——同样输入总得到同样结果。
pythonnew_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'。这就是链式叠加在训练侧的体现。
pythonself.vocab[next_id] = new_bytes # ① id → 字节串
self._bytes_to_id[new_bytes] = next_id # ② 字节串 → id
self.merges[best_pair] = next_id # ③ 合并规则
三处各司其职:
| 结构 | 键 → 值 | 用途 | 用在哪 |
|---|---|---|---|
vocab | id → 字节串 | 解码时查表拼字节 | 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,顺序不能反。
pythoncorpus = [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' 等片段。如果不更新语料,每轮都会重复统计原始相邻对,链式合并就不可能发生。
pythonnext_id += 1
为下一个新 token 准备编号,循环回到顶部。
假设某一轮语料是 [[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_bytes | b'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_id | 257 |
下一轮在 [[256, 256, 99]] 上统计,可能合并 (256, 256) → b'abab',如此层层推进。
pythontok = 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) 就是实际训练了几轮:
vocab[i](i ≥ 256)的字节串越长,通常说明它叠加了越多层合并。
| 设计点 | 说明 |
|---|---|
| 每轮只合并一个 pair,但全局替换 | 标准 BPE 做法:一次合并产生一个 token,作用到整个语料 |
| 语料逐轮压缩 | 是链式合并能发生的前提;不更新语料则规则无法叠加 |
| 两个终止条件 | range 耗尽 + pair_counts 为空,后者在小语料下更常见 |
merges 插入顺序 = 优先级 | 编码正确性的隐含前提,依赖 Python 3.7+ dict 保序 |
Counter 自动初始化 | 新键 += 从 0 开始,避免 KeyError |
| 复杂度 | 每轮 O(语料总长),共 O(M · 语料总长),教学规模足够 |
训练的核心开销在两处全量操作:
共 M 轮,总复杂度 O(M · 语料总长)。真实 tokenizer 的优化方向包括:
most_common 排序这些优化不改变 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"的双向链路,跑一个端到端往返示例,并讨论复杂度与真实实现的优化。
pythondef 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 编码成字节序列
pythonids = 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 步:按合并顺序逐条应用规则
pythonfor pair, new_id in self.merges.items():
ids = self._apply_merge(ids, pair, new_id)
self.merges 是训练时按产生顺序插入的 dict,遍历顺序 = 合并优先级。每轮用 _apply_merge 把序列中所有匹配的 pair 替换成 new_id。
关键:规则可以链式叠加。 后一条规则能作用在前一条规则的产物上,因为每轮都更新了 ids。假设训练学到:
pythonmerges = {
(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 次或多次合并:
"th"→256,若后续没有规则再把 256 合进去257、259pythondef 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 步:查表拼字节
pythonb"".join(self.vocab[i] for i in ids)
每个 id 查 vocab 得到对应字节串,用空字节串 b"" 拼接成完整字节流。b"" 是 bytes 字面量(不是 ""),因为 vocab 的值都是 bytes,bytes.join 要求元素全是 bytes。
pythonids = [228, 184, 173] # "中" 的三个基础 token
parts = [b'\xe4', b'\xb8', b'\xad']
b"".join(parts) # b'\xe4\xb8\xad'
第 2 步:UTF-8 解码
pythonraw_bytes.decode("utf-8", errors="replace")
把字节流按 UTF-8 还原成文本。errors="replace" 是容错:若传入不完整/非法字节序列,用替换符 � 代替而非抛异常。
decode 不需要 merges
注意 decode 完全不用 merges:每个 id 的最终字节已经完整存在 vocab 里。合并规则只在"压缩"(encode)时需要,解压直接查最终字节即可。
| 方法 | 依赖 | 方向 |
|---|---|---|
encode | merges(按顺序应用) | 文本 → id,压缩 |
decode | vocab(查表拼接) | id → 文本,解压 |
这体现一个设计原则:vocab 是信息的最终形态,merges 是达成它的过程记录。
训练后跑一遍完整链路,验证"编码再解码能还原原文"。
pythontok = 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。解码后与原文完全一致。
pythontext = "你好,世界"
ids = tok.encode(text)
print(ids) # 大多是 228~233 等原始字节 id
print(tok.decode(ids)) # "你好,世界"
由于训练语料没有中文,BPE 学不到中文的合并片段,编码结果接近"逐字节"。但依然能正确编解码——字节级覆盖保证任何文本都不丢信息,只是压缩率低(token 数多)。
pythonfor 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 的无损保证。
pythonfor 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。
换句话说:"出现一次"降低的是"被优先选中的概率",但不会阻止它在后续轮次被合并。当语料小、轮数多时,低频对最终也会被合并掉。
pythonfor i in range(256, min(tok.vocab_size, 266)):
print(i, tok.vocab[i]) # 如 256 b'th'、257 b'the'、...
字节串越长,通常说明叠加了越多层合并(不严格等于次数,因为每层左右长度可能不等)。
设:
n = 输入文本字节长度(初始 token 数)M = 合并规则数(≤ MERGE_COUNT = 256)encode:O(M · n)
pythonfor 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"的信息 |
核心思想:不改变 BPE 语义,只压常量和渐进复杂度。
1. rank + 优先队列:O(n log n)
真实 BPE(GPT-2、tiktoken)给每条 merge 规则分配 rank(优先级序号)。编码时不再"逐条规则扫全文",而是反复找当前序列中 rank 最小(优先级最高)的相邻对并合并。用优先队列维护所有相邻对的 (rank, 位置):
对比 O(M·n):n=1000、M=256 时,25.6 万 vs 约 1 万,n、M 越大优势越明显。
2. 预分词(pre-tokenization)
GPT-2 先按正则把文本切成词块("Hello world" → ["Hello", " world"]),每块独立做 BPE。好处:
3. 缓存
pythonif text in cache:
return cache[text]
自然语言重复度高,常见片段命中率极高,摊还接近 O(1)。tiktoken 更进一步,把常见"词块 → token 序列"做成预计算缓存表。
4. 紧凑数据结构
(左id, 右id) 编码成单个 32 位整数,方便哈希1. 增量统计
初始统计一次所有 pair 频率;合并后只更新受影响位置的相邻对计数(被合并位置的左右邻居),而非全量重扫。
2. 优先队列维护最高频 pair
避免每轮 most_common 全排序,用堆 O(log m) 取最大。
3. 预分词 + 并行
语料先切成词块,块内独立统计,减少跨块无意义配对;统计阶段按语料分片多线程/多进程并行,再合并计数器。
4. 低频过滤 / 近似结构
低频 pair 几乎不会被选中,可用阈值过滤;超大规模语料用 count-min sketch 等近似频率统计。
| 阶段 | 教学实现 | 真实优化后 |
|---|---|---|
| encode | O(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 顺序逐条应用 |
decode | id → 文本 | 查 vocab 拼字节 + UTF-8 解码 |
vocab_size | 词表大小 | @property 实时 len(vocab) |
<unk>:256 基础字节覆盖一切 Unicodevocab 说"是什么",merges 说"怎么合":decode 只用前者,encode 依赖后者merges 插入顺序 = 合并优先级:依赖 dict 保序,是正确性前提| 维度 | 教学版 | 真实(GPT-2/tiktoken) |
|---|---|---|
| 预分词 | 无 | 正则切词块 |
| 规则来源 | 4 句固定文本 | 海量语料 |
| 词表大小 | 512 | 5 万~10 万 |
| 编码策略 | 逐条规则全量扫 | rank + 堆 / 缓存 |
| 实现语言 | Python | Rust/C++ |
| 速度 | 教学够用 | 生产级 |
这段实现用最少的代码讲清了 BPE 的全貌:字节基础词表 → 统计高频相邻对 → 合并成新 token → 按合并顺序贪心编码 → 拼接字节解码。它的灵魂是"字节级无损 + 高频片段压缩",它的骨架是
vocab/merges/_apply_merge三件套。理解了它,就理解了 GPT 类模型分词器的核心原理;而真实实现的优化(rank、预切分、缓存、增量统计)都是在同一语义上的工程加速。
pyfrom 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 许可协议。转载请注明出处!