Definition：
minibpeとは、有限アルファベット $\Sigma$ 上の列（通常はUTF-8バイト列）$T \in \Sigma^*$ に対して、隣接する記号対の頻度に基づき反復的に置換規則を導入し、語彙集合 $V$ と置換規則集合 $R$ を同時に学習するアルゴリズムである。各反復では最頻出の隣接対 $(a,b)$ を新記号 $c$ に写像する規則 $c \rightarrow ab$ を導入し、列中の出現箇所を $c$ に置換する。この操作を語彙サイズ制約のもとで繰り返すことにより、入力列の階層的な再符号化（トークン化）を得る。
minibpeは、形式言語理論の観点では、文字列 $T$ に対して逐次的に生成規則を追加することにより、簡約文法を構築する過程とみなせる。初期状態では語彙は単一記号集合 $\Sigma$ であり、言語は $T$ のみを生成する自明な構造である。
各ステップ $k$ において、最頻出対 $(a,b)$ に対して新記号 $c_k$ を導入し、以下の生成規則を追加する：
\[c_k \rightarrow ab\]
このとき、列は逐次的に変換され、$T^{(k)}$ を第 $k$ ステップ後の列とすると、
\[T^{(k+1)} = \text{Replace}(T^{(k)}, ab \mapsto c_k)\]
最終的に得られる規則集合 $R = \{c_1 \rightarrow a_1 b_1, \dots, c_K \rightarrow a_K b_K\}$ は、元の列を再構成するための逐次的な文法として機能する。この構造は辞書型文法圧縮の一形態である。
minibpeは可逆圧縮アルゴリズムとして理解できる。元の列 $T$ は、最終トークン列 $Z$ と規則集合 $R$ によって完全に復元可能である。
圧縮の目的は、全体の記述長
\[L = |Z| \cdot \log |V| + \sum_{r \in R} \text{cost}(r)\]
を小さくすることである。ここで $|Z|$ はトークン列長、$|V|$ は語彙サイズである。
minibpeは各ステップで出現頻度最大のペアを選択することで、トークン列長の削減量を最大化する貪欲戦略を採用している。ペア $(a,b)$ の出現回数を $f(a,b)$ とすると、そのマージによる削減効果はおおよそ $f(a,b)$ に比例する。
情報理論的には、minibpeは高頻度部分列に短い符号を割り当てる近似的手法である。確率分布 $P(x)$ に対する最適符号長は
\[\ell(x) = -\log P(x)\]
で与えられるが、minibpeは明示的な確率推定を行わず、頻度情報を用いた局所的最適化により平均符号長
\[\mathbb{E}[\ell] = \sum_x P(x)\ell(x)\]
を低減する方向に働く。
各反復において隣接ペアの頻度計数を行うため、単純実装では1ステップあたり $O(n)$、全体では $O(nK)$ の計算量となる（$n$ は列長、$K$ はマージ回数）。
実装上は、ヒープやインデックス構造を導入することで効率化が可能である。
Byte Pair Encoding（BPE）は、1994年にPhilip Gageによって提案された可逆圧縮手法である。論文 "A New Algorithm for Data Compression"（C Users Journal, 1994年2月号）において初めて公表された。元のアルゴリズムはバイナリデータを含む任意のバイト列に適用可能な汎用圧縮手法として設計されており、データ中に存在しない未使用バイトを新たな記号として割り当てることでバイト対を置換し、置換テーブルを用いて元のデータを完全に復元する可逆圧縮を実現した。
その後20年あまりの間、BPEはLZWやハフマン符号など、より高度な圧縮アルゴリズムの陰に隠れ、データ圧縮の主流からは外れた位置にとどまっていた。
2016年、Rico Sennrich・Barry Haddow・Alexandra Birch（エディンバラ大学）が論文 "Neural Machine Translation of Rare Words with Subword Units"（ACL 2016）においてBPEをサブワード分割手法としてニューラル機械翻訳に導入した。
この転用における本質的な変更点は、対象を「バイト列の圧縮」から「文字列のサブワード単位への分割」へと読み替えたことにある。具体的には、語末マーカー（</w>）を用いて各単語を文字単位に分解したうえでBPEを適用し、頻度の高い文字対を逐次的にマージして語彙を構築する。これにより、未知語（Out-of-Vocabulary; OOV）問題を緩和しつつ、形態素的に透明なサブワード単位の語彙を自動的に獲得できることが示された。この手法は未知語問題の解決に寄与し、翻訳品質の向上にも貢献したことで自然言語処理分野に急速に普及した。
2019年、OpenAIはGPT-2（"Language Models are Unsupervised Multitask Learners", Radford et al.）においてバイトレベルBPE（Byte-Level BPE）を導入した。これはUnicodeテキストをまずUTF-8バイト列に変換し、256バイトを基底語彙として扱うことで、未知語トークン（<UNK>）を一切排除し、あらゆるテキストを損失なく符号化できる手法である。また、正規表現による事前分割（pre-tokenization）を組み合わせることで、単語境界・空白・数字・記号などの扱いを制御した。この設計はGPT-3、GPT-4と引き継がれ、現在のOpenAI製モデルが使用するtiktoken（2022年公開、Rust実装）にも採用されている。
同様に、RoBERTa・BART・DeBERTaなどBERTライクなモデルにもバイトレベルBPEが採用されており、BPEはLLM（大規模言語モデル）の標準的なトークナイザとして広く定着している。
minibpeはこのBPEアルゴリズムを簡潔に実装したものであり、その理論的本質を明示的に理解するための基盤的モデルである。Andrej Karpathyが教育目的で公開したminBPE実装はその代表例として知られ、BPEの動作原理をPythonで最小限に表現したものとして参照される。
Input: Training text $T$, Target vocab size $V$
$\text{tokens} = \text{list}(\text{UTF-8 encode}(T))$
$\text{vocab} = \{ i \mapsto \text{byte}(i) \mid i = 0, \dots, 255 \}$
$\text{merges} = \{\}$
$\text{next\_id} = 256$
for $k = 1$ to $(V - 256)$ do
$\text{pairs} = \text{count adjacent pairs in tokens}$
if $\text{pairs} = \emptyset$ then break
$\text{best\_pair} = \arg\max_{p} \text{pairs}[p]$
$\text{new\_token} = \text{vocab}[p_1] \, || \, \text{vocab}[p_2]$ // バイト列の連結
$\text{vocab}[\text{next\_id}] = \text{new\_token}$
$\text{merges}[\text{best\_pair}] = \text{next\_id}$
$\text{tokens} = \text{merge best\_pair in tokens}$ // 出現箇所を新トークンで置換
$\text{next\_id} = \text{next\_id} + 1$
end for
Encoding:
$\text{tokens} = \text{list}(\text{UTF-8 encode}(T))$
while True do
$\text{pairs} = \text{count adjacent pairs}$
$\text{best\_pair} = \text{None}$
$\text{best\_id} = \infty$
for each $(p, id) \in \text{merges}$ do
if $p \in \text{pairs}$ and $id < \text{best\_id}$ then
$\text{best\_pair} = p$
$\text{best\_id} = id$
end for
if $\text{best\_pair} = \text{None}$ then break
$\text{tokens} = \text{merge best\_pair using best\_id}$
end while
Decoding:
$\text{output} = \bigoplus_{t \in \text{tokens}} \text{vocab}[t]$
$\text{return UTF-8 decode}(\text{output})$
Output: Learned vocabulary $\text{vocab}$, merge rules $\text{merges}$, encoded tokens
Mathematics is the language with which God has written the universe.