第 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.