Day 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 バイト列に分解され、まったく同じマージループに従います。任意の作業：4 回目のマージまで進め、生成されるトークンを特定してください。

演習と予測記録

'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 | オリジナル出所URL ↗

該当セクション・範囲: 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 | オリジナル出所URL ↗

該当セクション・範囲: 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 支援なし）

前提条件

前の活動を完了していること。行き詰まった場合は一覧の回復リンクを使用してください。

学習目標

学習したマージを優先順位（ランク）に従って貪欲に適用して新しいテキストをエンコードし、語彙バイト列の連結によって完全に可逆（ロスレス）デコードし、バイトレベル入力が未知トークン <unk> を一切必要としない理由を説明する。

手順

エンコードは現在の ID 列を繰り返しスキャンし、最も低いランク（最も初期に学習された）の既知ペアを順次マージします。必須の作業：マージ表 {(97,97)→256, (256,97)→257, (257,98)→258} を用いて 'aab' と 'baaa' を手計算でエンコードし、[258,100,258,97,99] をデコードします。任意の作業：この教育用トークナイザにまだ欠けている実運用向け機能を 2 つ挙げてください。

演習と予測記録

上記マージ表の下で encode('aab') と encode('baaa') を予測し、[258,100,258,97,99] をデコードしてください。バイトレベル入力下で 'é猫' がどのようにエンコードされるか、なぜ 'unknown' にならないのかを説明してください。

完了としてマーク

独立習得基準

与えられたマージ表を用いて新しい文字列を手作業で正しくエンコード・デコードでき、バイトレベル入力が <unk> を不要にする原理と、本番トークナイザとの 2 つの具体的な違いを説明できること。

公式ソースリソースと権利証跡

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 | オリジナル出所URL ↗

該当セクション・範囲: 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 | オリジナル出所URL ↗

該当セクション・範囲: 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 分

マージ規則は train でのみ適合；検証セットで圧縮率を評価

Agent 支援エンジニアリング確認

前提条件

前の活動を完了していること。行き詰まった場合は一覧の回復リンクを使用してください。

学習目標

マージ表を学習パラメータとして扱い、決定論的な train 分割でのみ適合させ、ホールドアウトされた validation（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×）を再現し、validation でマージを適合させた場合に発生するデータリークの害を説明できること。

公式ソースリソースと権利証跡

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 | オリジナル出所URL ↗

該当セクション・範囲: 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 | オリジナル出所URL ↗

該当セクション・範囲: 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 長さ分類と Add-one スムージングの公式を記憶から引き出し、誤答に対する回復計画を記述する。

手順

この確認中は解答や AI を参照しないでください。必須の作業：(1) 'ababa' の最初の 2 回のマージを手計算する；(2) 第 39 日のマージ表で 'aaab' をエンコードする；(3) 4 つの UTF-8 長さ分類と加算平滑化の公式を記憶から書き出す；(4) ミスに対する回復計画を記録する。任意の作業：カウントベースのバイグラム LM と学習型マージ BPE トークナイザを 2 文で対比する。

演習と予測記録

何も見ずに解答してください：(a) 'ababa' の最初の 2 回のマージと最終 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 | オリジナル出所URL ↗

該当セクション・範囲: 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 | オリジナル出所URL ↗

該当セクション・範囲: 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.