第 39 天：字节对编码 (BPE) — 合并机制与分词器边界

01 120 分钟

配对计数与合并循环

Agent 辅助工程检查

前置要求

完成第 38 天。如受阻，使用第 35 天的回退链接复习概率与 Python。

学习目标

追踪 BPE 训练循环 — 统计相邻配对、将最高频配对合并为新 ID、迭代推进 — 并通过手工推导完整复现经过验证的合并表（包含空字符串与 Unicode 字节边界）。

操作指引

从 'aaabdaaabac' 的字节 ID 序列出发：[97,97,97,98,100,97,97,97,98,97,99]。必做工作：在每一轮中统计所有相邻配对；最高频配对获得下一个可用空闲 ID（256，接着是 257，以此类推）；频次相同时按首次出现位置打破平局（与 Python 基于插入顺序字典的 max() 行为一致）。写出合并追踪过程，并用 Python 简短脚本验证。空字符串 '' 的配对循环直接返回空。Unicode 字符串会先分解为 UTF-8 字节，再走完全相同的合并循环。选做工作：继续推演第四次合并并写出新生成的词元名称。

自主演练与记录

手工追踪在 'aaabdaaabac' 上进行的 3 次合并：记录每轮的配对计数、选中的配对以及变换后的新序列。在核对答案前预估最终词元数与词汇表大小。

标记为已完成

独立掌握标准

手写推导在不查阅参考资料或使用 AI 的情况下，完整复现全部 3 次合并、先现平局打破规则、最终词元列表以及 259 的词汇表规模。

权威源资源与权利证明

linking MIT License (repository) / Standard YouTube License (video, subtitle rights unknown) Video subtitles have unknown distribution rights and are not imported

minbpe: Minimal Byte-Pair Encoding tokenizer (Let's build the GPT Tokenizer)

作者 / 机构: Andrej Karpathy | 原始出处链接 ↗

对应章节 / 范围: minbpe/base.py: get_stats pair counting and merge loop; minbpe/basic.py BasicTokenizer

验证版本与日期: commit 1acefe8 (Verified: 2026-10-30)

入选理由:

The reference minimal implementation whose pair-count and merge loop the lesson traces by hand.

来源前置条件:

Basic Python and Day 37 bytes/code points

安全回退方案（离线弹性）:

The lesson re-implements the merge loop locally and prints a verified merge trace.

对比候选资源与选型分析 (3)

OpenAI tiktoken ↗ compared_alternative [MIT]

Production BPE with Rust core and regex pre-tokenization; selected as the production contrast source rather than the primary teaching implementation.

Hugging Face tokenizers + NLP course chapter 6 ↗ compared_alternative [Apache-2.0 (library) / CC BY-NC-SA? (course text varies)]

High-quality BPE coverage but frames tokenization through library APIs; minbpe exposes the raw merge loop for hand tracing.

Google SentencePiece ↗ compared_alternative [Apache-2.0]

Industrial tokenizer trainer supporting BPE and unigram models; C++ core hides the teaching mechanics.

linking CC BY 4.0 (ACL Anthology, 2016 or later) Paper text is not reproduced; linking only

Neural Machine Translation of Rare Words with Subword Units

作者 / 机构: Rico Sennrich, Barry Haddow, Alexandra Birch | 原始出处链接 ↗

对应章节 / 范围: Section 3: byte-pair encoding adapted from compression to subword segmentation

验证版本与日期: ACL 2016 (Verified: 2026-10-30)

入选理由:

Primary source that introduced BPE as a subword segmentation algorithm for neural sequence models.

来源前置条件:

Basic probability and text processing

安全回退方案（离线弹性）:

The lesson teaches the complete merge algorithm with worked traces independent of the paper text.

对比候选资源与选型分析 (2)

Schuster & Nakajima: Japanese and Korean Voice Search (WordPiece) ↗ compared_alternative [IEEE copyright]

Related likelihood-scored variant used in BERT; paywalled and less aligned with frequency-greedy teaching merges.

Kudo & Richardson: SentencePiece (unigram language model) ↗ compared_alternative [CC BY 4.0 (paper, ACL Anthology) / Apache-2.0 (code)]

Strong probabilistic alternative segmentation; deferred because deterministic BPE merges are more hand-traceable at this stage.

02 120 分钟

编码、解码与未知输入策略

独立掌握检查（无 AI 辅助）

前置要求

完成上一活动；如受阻，使用列出的回退链接。

学习目标

按合并优先级（rank）贪心应用学习到的合并规则编码新文本，通过拼接词汇表字节串实现无损可逆解码，并说明为什么字节级输入永远不需要 <unk> 词元。

操作指引

编码过程反复扫描当前 ID 列表，并在相邻对中选择具有最低合并序号（即最先被学习）的已知对进行合并，直到不存在可合并对。必做工作：基于合并表 {(97,97)→256, (256,97)→257, (257,98)→258}，手算编码 'aab' 和 'baaa'，随后解码 [258,100,258,97,99]。选做工作：列举教学分词器尚缺少的两项工业生产级特性。

自主演练与记录

预测在上述合并表下 encode('aab') 和 encode('baaa') 的结果，然后解码 [258,100,258,97,99]。说明在字节级输入下 'é猫' 编码为何种形式，以及为什么它绝不会变成 'unknown'。

标记为已完成

独立掌握标准

给定合并表，能手工正确编码和解码新字符串，清晰说明字节级输入免除 <unk> 的数学与工程原理，并指出与工业分词器的两处具体差异。

权威源资源与权利证明

linking MIT License (repository) / Standard YouTube License (video, subtitle rights unknown) Video subtitles have unknown distribution rights and are not imported

minbpe: Minimal Byte-Pair Encoding tokenizer (Let's build the GPT Tokenizer)

作者 / 机构: Andrej Karpathy | 原始出处链接 ↗

对应章节 / 范围: minbpe/base.py: encode iterates merges by rank; decode concatenates vocab byte strings

验证版本与日期: commit 1acefe8 (Verified: 2026-10-30)

入选理由:

Reference for the rank-ordered encode loop and lossless decode invariant exercised in this activity.

来源前置条件:

Day 39 Activity 1 merge table

安全回退方案（离线弹性）:

The exercises use a fully printed merge table and verified expected token ids.

对比候选资源与选型分析 (3)

OpenAI tiktoken ↗ compared_alternative [MIT]

Production BPE with Rust core and regex pre-tokenization; selected as the production contrast source rather than the primary teaching implementation.

Hugging Face tokenizers + NLP course chapter 6 ↗ compared_alternative [Apache-2.0 (library) / CC BY-NC-SA? (course text varies)]

High-quality BPE coverage but frames tokenization through library APIs; minbpe exposes the raw merge loop for hand tracing.

Google SentencePiece ↗ compared_alternative [Apache-2.0]

Industrial tokenizer trainer supporting BPE and unigram models; C++ core hides the teaching mechanics.

linking MIT License

tiktoken: Fast byte-pair encoding tokenizer used by OpenAI models

作者 / 机构: OpenAI | 原始出处链接 ↗

对应章节 / 范围: README and tiktoken/core.py: byte-level coverage, regex pre-tokenization, and special-token handling

验证版本与日期: Verified 2026-10-30

入选理由:

Production contrast showing why a teaching tokenizer without regex pre-tokenization and special tokens is not model-compatible.

来源前置条件:

Basic Python

安全回退方案（离线弹性）:

All encode/decode exercises run on the local merge table with verified outputs.

对比候选资源与选型分析 (2)

Hugging Face tokenizers library ↗ compared_alternative [Apache-2.0]

Broad production tokenizer framework with training APIs; tiktoken is a cleaner contrast for GPT-style compatibility claims.

Google SentencePiece ↗ compared_alternative [Apache-2.0]

Widely used trainer/tokenizer for open models; treated as further production context rather than the contrast reference.

03 120 分钟

仅在训练集拟合合并；在验证集评估压缩比

Agent 辅助工程检查

前置要求

完成上一活动；如受阻，使用列出的回退链接。

学习目标

将合并表视为可学习参数：仅在确定性训练划分上拟合，在留出的验证集 val（绝非测试集 test）上测量字节/词元压缩比，并记录每个阶段消费的数据划分。

操作指引

必做工作：复用第 37 天的数据管线 — 运行 python3 projects/text_tools/cli.py --input data/names.txt --split --output-dir /tmp/lm-data（seed 42 → 25626/3203/3204）。仅在 train.txt 上训练合并规则，然后在 val 片段上编码并统计 len(utf8_bytes)/len(token_ids) 压缩比。使用不同的合并次数在 val 上调优选型，测试集 test.txt 保持严密封存。选做工作：在笔记中记录选定的合并数与两组压缩比。

自主演练与记录

预测在训练文本与留出文本上的压缩比孰高孰低，并说明原因。在玩具语料上验证：在 'aaabdaaabac' 上拟合的合并将其由 11 字节压缩为 5 词元；该表压缩留出的 'aab' 表现如何？

标记为已完成

独立掌握标准

清楚陈述每个阶段消费的数据划分，重现两组压缩比数据（拟合集 2.2× vs 留出集 1.5×），并阐明若在验证集上拟合合并表所导致的数据泄露危害。

权威源资源与权利证明

linking MIT License (repository) / Standard YouTube License (video, subtitle rights unknown) Video subtitles have unknown distribution rights and are not imported

minbpe: Minimal Byte-Pair Encoding tokenizer (Let's build the GPT Tokenizer)

作者 / 机构: Andrej Karpathy | 原始出处链接 ↗

对应章节 / 范围: README exercise: train a tokenizer on your own text and report compression ratio

验证版本与日期: commit 1acefe8 (Verified: 2026-10-30)

入选理由:

Frames tokenizer training as fitting merge parameters and compression as the evaluable metric.

来源前置条件:

Day 39 Activities 1-2

安全回退方案（离线弹性）:

The local merge trainer and the deterministic text_tools splits run fully offline.

对比候选资源与选型分析 (3)

OpenAI tiktoken ↗ compared_alternative [MIT]

Production BPE with Rust core and regex pre-tokenization; selected as the production contrast source rather than the primary teaching implementation.

Hugging Face tokenizers + NLP course chapter 6 ↗ compared_alternative [Apache-2.0 (library) / CC BY-NC-SA? (course text varies)]

High-quality BPE coverage but frames tokenization through library APIs; minbpe exposes the raw merge loop for hand tracing.

Google SentencePiece ↗ compared_alternative [Apache-2.0]

Industrial tokenizer trainer supporting BPE and unigram models; C++ core hides the teaching mechanics.

linking MIT

CS336 Assignment 1: Basics (Spring 2025 tagged release)

作者 / 机构: Stanford University CS336 Staff | 原始出处链接 ↗

对应章节 / 范围: README setup; tests/adapters.py; tests/test_optimizer.py; tests/test_nn_utils.py; tests/test_serialization.py

验证版本与日期: spring2025 tag; README, tests and MIT LICENSE checked 2026-11-01

入选理由:

Lead assignment-driven source for pretraining component practice and tests. nanoGPT remains a compact historical code-reading companion, not the current recommended training curriculum.

来源前置条件:

Python systems programming

安全回退方案（离线弹性）:

The local verification script trains merges on a train split and reports val compression offline.

对比候选资源与选型分析 (2)

Karpathy nanoGPT ↗ compared_alternative [MIT]

Simpler code layout, useful complementary reference for minimal PyTorch Transformer.

Hugging Face Transformers Course ↗ compared_alternative [Apache-2.0]

High-level API focus rather than building from raw tensor fundamentals.

04 120 分钟

独立掌握检查：手算合并追踪与模块检索复盘

独立掌握检查（无 AI 辅助）

前置要求

完成前面所有活动；如受阻，使用列出的回退链接。

学习目标

在无辅助情况下追踪新文本的 BPE 合并、用已知表编码、默写 UTF-8 长度分级与加一平滑公式，并针对薄弱环节制定具体回退复习计划。

操作指引

本检查期间不要查看答案或使用 AI。必做工作：(1) 手算 'ababa' 的前两次合并；(2) 在第 39 天合并表下编码 'aaab'；(3) 默写四类 UTF-8 字节长度与加一平滑公式；(4) 为失误项记录回退计划。选做工作：用两句话对比基于计数的二元模型与学习合并的 BPE 分词器。

自主演练与记录

闭卷作答：(a) 'ababa' 的前两次合并是什么？最终 ID 序列为何？(b) 在合并表 {(97,97)→256, (256,97)→257, (257,98)→258} 下 encode('aaab') 是多少？(c) 默写：'a', 'é', '猫', '😀' 的 UTF-8 字节数，以及加一平滑转移概率公式 P(next|context)。

标记为已完成

独立掌握标准

所有合并与 ID 准确无误，默写知识点与公式完全正确，回退计划具体指明用于补救失误的对应活动编号（Day 37-39）。

权威源资源与权利证明

linking CC BY 4.0 (ACL Anthology, 2016 or later) Paper text is not reproduced; linking only

Neural Machine Translation of Rare Words with Subword Units

作者 / 机构: Rico Sennrich, Barry Haddow, Alexandra Birch | 原始出处链接 ↗

对应章节 / 范围: Section 3: merge operations as learned segmentation vocabulary

验证版本与日期: ACL 2016 (Verified: 2026-10-30)

入选理由:

Primary reference for interpreting merges as a learned vocabulary of subword units.

来源前置条件:

Basic probability and text processing

安全回退方案（离线弹性）:

The mastery check contains a complete worked merge trace with verified ids.

对比候选资源与选型分析 (2)

Schuster & Nakajima: Japanese and Korean Voice Search (WordPiece) ↗ compared_alternative [IEEE copyright]

Related likelihood-scored variant used in BERT; paywalled and less aligned with frequency-greedy teaching merges.

Kudo & Richardson: SentencePiece (unigram language model) ↗ compared_alternative [CC BY 4.0 (paper, ACL Anthology) / Apache-2.0 (code)]

Strong probabilistic alternative segmentation; deferred because deterministic BPE merges are more hand-traceable at this stage.

linking MIT License (repository) / Standard YouTube License (video, subtitle rights unknown) Video subtitles have unknown distribution rights and are not imported

makemore: Character-level language models on names.txt

作者 / 机构: Andrej Karpathy | 原始出处链接 ↗

对应章节 / 范围: makemore.py part 1: bigram count model as the count-based baseline against learned models

验证版本与日期: Verified 2026-10-30

入选理由:

Connects the count baseline of Day 38 to the tokenizer artifacts of Day 39 for the closing retrieval review.

来源前置条件:

Basic Python

安全回退方案（离线弹性）:

The retrieval review works entirely from local verified tables and traces.

对比候选资源与选型分析 (2)

Stanford CS336: Language Modeling from Scratch ↗ compared_alternative [No license declared (the repository has no LICENSE file, so all rights are reserved by default)]

More rigorous and comprehensive but assumes PyTorch fluency; retained as the systems-rigor companion source.

Karpathy nanoGPT ↗ compared_deferred [MIT]

Strong Transformer training reference but beyond the count-based baseline scope; deferred to later pretraining days.