从字节对统计到可逆 BPE

任务与先修：只从训练文本学习表示

基础字节编码固定且覆盖完整，却让一个汉字通常占多个位置，有限窗口因此能容纳的可见文本较短。本章实现一个容易逐项核验的字节对编码。读者需掌握上一章的字节编号、列表扫描与频数统计。这里 BPE 指反复合并当前序列中常见相邻编号的算法，不是一个预训练模型。本项目不使用正则预切词，不设置词边界，不复制任何现成 tokenizer 的完整行为；合并可以穿过空格或标点，但绝不能穿过文档边界。这个范围足以研究压缩、覆盖与实验口径。

从二百五十六种字节和两个边界符开始。第 $r$ 条规则从零计数，新编号为 $258+r$，规则保存二元组 $(a_r,b_r)$。它的字节片段定义为两个已有片段的顺序连接。特殊符号不出现在训练合并序列中，因此不会被合并；某条规则只能引用原始字节或更早生成的编号，不能引用自己、未来编号或边界编号。实际词表大小是二百五十八加实际规则条数，不是用户请求上限。项目请求三十二次合并，若最大 pair 频数小于二便提前停止。

每轮算法的四个确定选择

首先把每篇训练文档单独编码成正文 bytes 列表。第二步计数所有当前相邻 pair，每篇内部累加，但不把上一篇末尾与下一篇开头配对。第三步选择频数最大的 pair；若并列，选编号二元组字典序最小者。第四步在每篇序列从左至右扫描，遇到该 pair 就输出新编号并前进两格，否则输出原编号并前进一格。扫描在旧序列上进行，一轮新生成的 token 不在同轮再次参与匹配。然后才开始下一轮重新计数。

“计数包含重叠，替换不重叠”很容易混淆。序列 [a,a,a] 有两个相邻 (a,a)，但一次合法替换只能用掉前两个 a，得到 [new,a]，不能同时消耗两次中间元素而得到 [new,new]。因此最高 pair 计数不是本轮序列长度减少量的普遍等式。我们的朴素实现每轮重数全部邻接并重扫全部序列，时间约为合并次数乘当前总长度；它清晰但不适合大语料，不能称为工业 tokenizer 训练器。

算例一：含并列与多轮的完整手算

训练文档是“abab”和“acac”，字节 a、b、c 分别为九十七、九十八、九十九。第一篇 pair 计数 ab 两次、ba 一次；第二篇 ac 两次、ca 一次。最高频 ab 与 ac 都为二，按字典序选择 (97,98)，新编号二百五十八代表 bytes ab。替换后两篇变成 [258,258] 与 [97,99,97,99]。新的计数为 (258,258) 一次、ac 两次、ca 一次，第二轮选择 ac，新编号二百五十九。现在两篇为 [258,258] 与 [259,259]。

下一轮每个 pair 只出现一次，项目停止，哪怕请求上限为三十二。因此实际词表为二百六十，八个原始正文 bytes 变成四个正文 token，平均每 token 两字节。重新编码“abac”时依次应用两条有序规则，得到 [258,259]，加边界后为 [256,258,259,257]。两个 token 的 bytes 顺序连接恢复 abac。独立检查一是手算规则顺序与实现完全一致，独立检查二是对训练之外的新组合做往返，避免只验证训练串的记忆映射。

算例二：一个看似更短但不可逆的替换

对“aaa”，若把重叠 pair 都输出为新 token aa，会得到 [258,258]，解码后是“aaaa”，凭空多一个 a。正确扫描输出 [258,97]，长度由三变二，解码仍是“aaa”。还有一种错误是在一轮替换后立即拿新 token 与下一字节继续做未登记合并，这会使编码依赖控制流程而非已保存规则。若训练与推理实现不同，tokenizer 摘要即使相同也救不了它；摘要验证的是规则对象，还需要代码版本和往返测试约束规则的解释方式。

可逆性可用归纳法说明。初始每个编号代表一个原始字节，拼接就是原始文档。假设某轮前拼接结果正确；替换两个相邻片段为它们的连接，不改变拼接内容，也不改变其他片段顺序，所以该轮后仍正确。有限轮重复得到相同 bytes，再由 UTF-8 可逆性恢复文本。这个证明不需要合并是最高频；最高频只是学习策略。反向也不成立：能解码的 token 序列不一定是本分词器 encode 选出的规范序列。

from collections import Counter

def merge(seq,pair,new):
    out=[]; i=0
    while i<len(seq):
        if i+1<len(seq) and tuple(seq[i:i+2])==pair:
            out.append(new); i+=2
        else: out.append(seq[i]); i+=1
    return out
seqs=[list(b'abab'),list(b'acac')]; pieces={i:bytes([i]) for i in range(256)}; rules=[]
for rank in range(32):
    counts=Counter(p for s in seqs for p in zip(s,s[1:]))
    pair=min(counts,key=lambda p:(-counts[p],p))
    if counts[pair]<2: break
    new=258+rank; rules.append(pair); pieces[new]=pieces[pair[0]]+pieces[pair[1]]
    seqs=[merge(s,pair,new) for s in seqs]
assert rules==[(97,98),(97,99)]
assert seqs==[[258,258],[259,259]]
correct=merge([97,97,97],(97,97),258)
assert correct==[258,97]
assert b''.join((b'aa' if i==258 else bytes([i])) for i in correct)==b'aaa'
print('rules',rules,'encoded training',seqs,'overlap example',correct)

为什么规则只看训练集合

词表学习没有显式预测标签，仍然属于拟合。假设训练只有 ab 重复，测试只有 xy 重复；把测试加入 pair 计数会让 tokenizer 预先为 xy 分配一个短编号，改变测试长度、参数量和上下文覆盖。即使权重随机初始化，这个系统也已利用测试分布。本项目 build 只把 split[train] 交给 fit，保存有序规则与摘要；验证和测试调用 encode，不更新统计。所谓“没有使用测试训练模型”必须包含 tokenizer，而不只是 optimizer.step 没看测试 loss。

如果训练时学到的某个合并在测试没有出现，它也不能被删除，因为编号、输出矩阵列和 checkpoint 已绑定。如果需要新的分词器，应视为新实验，重新初始化或明确设计映射迁移；本课不实现迁移。所有基础字节仍保留，所以未见字符不会变成未知符号，只是可能需要更多 token。同一数据的压缩率可以作为表示统计量，但不能凭压缩率高就宣布预测更容易：它也可能产生较多低频的大块类别，让有限数据难以估计其条件概率。

规范路径不等于文本所有编码的概率

BPE 词表保留 a、b，也增加 ab。模型可能生成 token [a,b]，也可能生成 [ab]，两者解码为同一个 bytes 串。训练与评估只对 encode 所选的规范路径计算概率。若文本 ab 的规范编码为 [ab]，该路径概率乘上 EOS 概率并不自动包含 [a,b,EOS] 的概率。若要得到解码文本的边缘概率，需要对所有可解码成该文本的合法 token 路径求和，通常代价很大。我们没有实现这个求和。

因此第七章的跨编码指标正式称“含 EOS 的规范路径位数每原始字节”。它是固定协议下有用的实验量，但不能不加条件地叫真实压缩文件大小，还没有计 tokenizer、模型、元数据和具体编码器成本。这个命名并非文字谨慎而已：若两个路径都给同一文本较高概率，边缘概率会大于单一路径概率，负对数也会不同。评估对象的定义决定结论的有效范围，后续图表必须保留这个限定。

本章项目增量是可序列化的 ByteBPE：有序规则、片段表、确定 tie 规则、encode/decode 和摘要。训练中使用三十二条合并，实际本地语料恰好达到上限，词表二百九十。下一章将用这些真实长度制造窗口；同一篇短文可能因姓名不同而有不同 token 数，所以“每篇差不多长”不能作为丢弃尾窗或等权平均 batch 的理由。

规则顺序不是可有可无的附件。设先学到ab，再学到“ab与c”的合并abc。编码abc时第一条先把a、b变成中间编号，第二条才能识别它与c。若反过来执行规则，第二条看不到那个中间编号，最终只得到ab和c。decode仍可恢复原文，所以单独往返不能发现规范编码漂移；应同时断言指定样例的精确编号序列。项目将规则按生成顺序保存，恢复不按片段长度排序，也不采用“当前最长字符串优先”的另一种算法。

片段表中某个token可能只含一个UTF-8字符的前半段，因为pair统计以字节而非码点为单位。例如合并两个连续字节可以得到一个本身无法严格解码的片段，但它与后续片段连接后完全合法。因此调试词表时不能要求每个piece都能独立decode为汉字；应该先看十六进制bytes，再在完整文档层验证。若为了打印方便用替代字符解码piece，不能用替代后的字符串重新构建bytes，否则可逆性被破坏。

序列缩短还会改变模型的有效文本视野。固定二十四个位置，基础字节模式最多看二十四正文bytes附近的历史；BPE合并后同样位置数可覆盖更多bytes，但覆盖量依内容而变，不能直接称为固定二十四个汉字。比较分词器时，模型得到的原始文本上下文也在变化。为隔离纯表示因素，需额外匹配字节上下文或明确把扩展视野当作分词收益的一部分；当前小项目只固定token窗口，并在报告中承认这个混杂。

合并预算也会影响模型参数。每增加一个token，未共享的输入表与输出头共多两行宽度d的参数，所以新增参数为二倍d。若比较两种合并数而固定d，实际参数预算不同。项目不把三十二次合并的结果解释为“分词算法在严格同参数条件下更优”；这里只证明训练规则可复现、编码可逆、接口可以接完整模型。可重建的表示实验先于性能结论。

频率统计的样本单位也影响规则。两篇完全相同文档若在训练中被重复登记，会让其中所有pair权重翻倍；BPE不会自行知道它们是否应被去重。第一章的读取器只禁止跨集合精确重复，并没有删除同一训练集合内部重复，因此扩展语料时必须主动定义内部去重政策。当前原创语料每条文本不同、分组明确，足够验证算法；不能把“训练只看train”误读成统计输入已经具有合理来源权重。

python -m unittest -v tests.test_pipeline.PipelineTests.test_bpe_exact_rules_and_tie tests.test_pipeline.PipelineTests.test_train_only_and_digest

# merge_pair
def merge_pair(ids,pair,new_id):
    raise NotImplementedError('bpe')

# fit_merges
def fit_merges(documents,max_merges):
    raise NotImplementedError('bpe')

# merge_pair
def merge_pair(ids,pair,new_id):
 out=[];i=0
 while i<len(ids):
  if i+1<len(ids) and tuple(ids[i:i+2])==tuple(pair):out.append(new_id);i+=2
  else:out.append(ids[i]);i+=1
 return out

# fit_merges
def fit_merges(documents,max_merges):
 if type(max_merges)is not int or max_merges<0:raise ValueError('nonnegative integer max_merges')
 rows=[list(text.encode('utf-8'))for text in documents];merges=[]
 for rank in range(max_merges):
  counts={}
  for row in rows:
   for i in range(len(row)-1):
    pair=tuple(row[i:i+2]);counts[pair]=counts.get(pair,0)+1
  if not counts or max(counts.values())<2:break
  pair=min(counts,key=lambda p:(-counts[p],p));new_id=258+rank;merges.append((pair,new_id));rows=[merge_pair(row,pair,new_id)for row in rows]
 return merges