# トークン化：バイト対符号化（BPE）の手順と性質

> 文字列をトークン id の列に変えるバイト対符号化（BPE）を、記号列の書き換えとして定式化し、往復の一致・語彙の大きさ・長さの単調性・学習の停止性と計算量を証明する。貪欲な符号化が最短分割にならない反例と、最小実装の実行結果も載せる。
> https://rikai.mugen-giken.com/computer-science/llm-architecture/tokenization-bpe

## 0. この記事の要点

文章を扱う AI は、文字をそのまま読むのではなく、あらかじめ文字列を「番号の列」に直してから読みます。この記事は、その番号の振り方のうち最も広く使われている方法を、小さな例と証明つきで調べます。読み終えると、「元の文字列に必ず戻るのはなぜか」「なぜ手順が必ず終わるのか」「どこまでが保証され、どこからが保証されないのか」を、自分で説明できるようになります。

- 言語モデルが受け取るのは文字ではなく**トークン id の列**です。文字列をその列に変える手続きのうち、広く使われているバイト対符号化（BPE）を、記号列の書き換え規則として定義します。
- BPE の学習は「いちばん多い隣接ペアを 1 つの新しいトークンにする」操作の反復です。$m$ 回のマージのあと語彙の大きさはちょうど $|\Sigma| + m$ になります（<Ref to="prop-bpe-vocab-size" />）。
- 符号化して復号すると必ず元の記号列に戻ります（<Ref to="thm-bpe-roundtrip" />）。バイト単位で始めれば、どんな文字列も符号化でき、未知語が生じません。
- マージを 1 つ適用するとトークン数は置き換えた回数だけ減ります。この量を変量に取ると、学習が停止することと、マージの回数が「総記号数 − 語の数」以下であることが出ます（<Ref to="prop-bpe-training-termination" />）。
- BPE の符号化は貪欲な手続きで、語彙を固定したときの最短の分割を与えるとは限りません（<Ref to="prop-bpe-greedy-not-optimal" />）。また、バイト単位のトークンの境界は文字の境界と一致しないことがあります（<Ref to="prop-utf8-boundary" />）。

<Aside type="tip" title="この記事で使う事前知識">

- **数学的帰納法**: 「最初の場合に成り立ち、1 つ前までの場合から次の場合が出る」ことで、すべての場合を示す証明の型。→ [証明の技術](/mathematics/foundations/proof-techniques)
- **対偶**: 「A ならば B」と同じ内容を持つ「B でなければ A でない」という形。→ [対偶](/mathematics/foundations/proof-techniques#def-converse-contrapositive)
- **O 記法**: 入力が大きくなるときの手順の長さの増え方を、定数倍を無視して表す記法。→ [計算量と O 記法](/computer-science/algorithms/complexity-and-big-o)
- **単射**: 異なる元を必ず異なる元に写す写像。
- **辞書式順序**: 辞書のように、先頭から順に比べて大小を決める順序。
- **動的計画法**: 小さい部分問題の答えを表にためて、大きい問題の答えを組み立てる方法。

</Aside>

## 1. 動機：モデルに渡す「記号」を何にするか

言語モデルは、有限個の記号からなる列を入力に取り、次の記号の確率分布を出力する関数です。したがって最初に決めなければならないのは、文字列をどういう記号の列とみなすかです。素朴な選択肢は 2 つあります。

| 単位 | 語彙の大きさ | 列の長さ | 困る点 |
|---|---|---|---|
| 文字（またはバイト） | 小さい（バイトなら 256） | 長い | 列が長くなり、あとの章で見るとおり注意の計算量は列の長さの 2 乗で増える |
| 単語 | 大きい（数十万以上） | 短い | 学習時に無かった単語を表せない。語形変化や複合語のたびに語彙が増える |

BPE はこの中間を取る方法です。記号 1 個から始め、よく並んで現れる 2 つをまとめて新しい記号にする、という操作を決まった回数だけ繰り返します。よく現れる単語は 1 個のトークンになり、珍しい単語は短い断片の列になります。マージの回数 $m$ が、語彙の大きさと列の長さの釣り合いを決めるただ 1 つの調整量です。

もとは Gage がデータ圧縮の方法として発表したもので（[1]）、Sennrich・Haddow・Birch が機械翻訳の単語分割に転用しました（[2]）。Radford らは、文字ではなく UTF-8 のバイト列に対して BPE を行うことで、基本の語彙を 256 個に抑えたまま任意の文字列を扱えるようにしました（[3]）。この記事ではこのバイト単位の形を主に扱います。

この記事の目的は、手続きを紹介するだけでなく、「この手続きについて何が証明できるか」をはっきりさせることです。往復の一致や停止性のように必ず成り立つ性質と、最短性のように成り立たない性質を分けて示します。

## 2. 準備：記号列・語彙・復号

<Definition id="def-alphabet-vocab" title="アルファベット・語彙・復号">

空でない有限集合 $\Sigma$ を**アルファベット**、その元を**記号**という。記号の有限列を**記号列**といい、その全体を $\Sigma^{*}$、長さ 1 以上のものの全体を $\Sigma^{+}$ と書く。記号列 $s, t$ をつないだ列を $st$ と書き（**連結**）、長さを $|s|$ と書く。空列を $\varepsilon$ と書く。

有限集合 $V$ と写像 $\langle\!\langle \cdot \rangle\!\rangle : V \to \Sigma^{+}$ の組を**語彙**といい、$V$ の元を**トークン id**（または単にトークン）、$\langle\!\langle t \rangle\!\rangle$ をトークン $t$ の**表す記号列**という。$V$ の元の有限列 $x = (t_1, \ldots, t_n) \in V^{*}$ を**トークン列**といい、

$$
\mathrm{dec}(x) := \langle\!\langle t_1 \rangle\!\rangle \langle\!\langle t_2 \rangle\!\rangle \cdots \langle\!\langle t_n \rangle\!\rangle \in \Sigma^{*}
$$

を $x$ の**復号**という（$n = 0$ のときは $\mathrm{dec}(\varepsilon) = \varepsilon$）。$V_0 := \Sigma$、$\langle\!\langle a \rangle\!\rangle := a$ で定まる語彙を**基本語彙**という。

</Definition>

復号は連結について $\mathrm{dec}(xy) = \mathrm{dec}(x)\,\mathrm{dec}(y)$ を満たします。定義の右辺が、$x$ の分の連結と $y$ の分の連結をつないだものだからです。この性質は以下で繰り返し使います。

**バイトレベル**の場合は $\Sigma = \{0, 1, \ldots, 255\}$ で、$|\Sigma| = 256$ です。文字列は先に UTF-8 でバイト列に直しておきます（<Ref to="def-utf8" />）。

<Definition id="def-merge" title="マージ規則とその適用">

語彙 $(V, \langle\!\langle\cdot\rangle\!\rangle)$ のトークン $a, b \in V$ と、$V$ に属さない新しい id $c$ の組 $r = (a, b \mapsto c)$ を**マージ規則**という。規則 $r$ は語彙を $V' := V \cup \{c\}$、$\langle\!\langle c \rangle\!\rangle := \langle\!\langle a \rangle\!\rangle \langle\!\langle b \rangle\!\rangle$ に広げる。

規則 $r$ の**適用** $M_r : V'^{*} \to V'^{*}$ を、列の長さについて再帰的に次で定める。

$$
M_r(\varepsilon) = \varepsilon, \qquad M_r(t_1) = (t_1), \qquad
M_r(t_1 t_2 u) =
\begin{cases}
c \, M_r(u) & (t_1, t_2) = (a, b) \text{ のとき} \\
t_1 \, M_r(t_2 u) & \text{それ以外}
\end{cases}
$$

ここで $u \in V'^{*}$ は残りの列である。すなわち列を左から走査し、$a$ の直後に $b$ があればその 2 個を $c$ 1 個に置き換えて 2 つ進み、そうでなければ 1 つ進む。

トークン列 $x = (t_1, \ldots, t_n)$ について、ペア $(a, b)$ の**出現回数**を $\mathrm{cnt}_x(a, b) := \#\{ i : 1 \le i < n,\ (t_i, t_{i+1}) = (a, b)\}$、$M_r$ が $x$ の上で行う置き換えの回数を $\mathrm{rep}_r(x)$ と書く。$\mathrm{rep}_r$ は $M_r$ の定義の場合分けに沿って、$\mathrm{rep}_r(\varepsilon) = \mathrm{rep}_r(t_1) = 0$、1 つ目の場合 $\mathrm{rep}_r(t_1t_2u) = 1 + \mathrm{rep}_r(u)$、2 つ目の場合 $\mathrm{rep}_r(t_1t_2u) = \mathrm{rep}_r(t_2u)$ で定まる。

</Definition>

$a = b$ のとき、出現は重なりえます。列 $(a, a, a)$ では $\mathrm{cnt}(a, a) = 2$ ですが、左から走査すると最初の 2 個が $c$ になり、残りは $a$ 1 個なので、結果は $(c, a)$、$\mathrm{rep} = 1$ です。$\mathrm{rep}_r(x)$ は「重なりを除いて左から数えた出現回数」にあたります。

<Definition id="def-bpe" title="BPE の学習と符号化">

アルファベット $\Sigma$ に全順序が与えられているとする。**コーパス**とは、$\Sigma^{+}$ の元（**語**）の有限列 $C = (w_1, \ldots, w_K)$、$K \ge 1$ のことである。マージの回数の上限 $m \ge 0$ が与えられたとき、**BPE の学習**は次の手続きである。

1. $x_k^{(0)} := w_k$（各語を基本語彙のトークン列とみなす）、$V_0 := \Sigma$、$j := 0$ と置く。
2. $j = m$ ならば終了する。そうでなければ、$V_j$ の各ペア $(a, b)$ について、コーパス全体での出現回数 $N_j(a, b) := \sum_{k=1}^{K} \mathrm{cnt}_{x_k^{(j)}}(a, b)$ を数える（語をまたぐペアは数えない）。
3. すべてのペアで $N_j(a, b) = 0$ ならば終了する。
4. $N_j$ が最大のペアを選ぶ。最大のものが複数あるときは、$V_j$ の順序に関する辞書式順序（まず $a$ を比べ、等しければ $b$ を比べる）で最小のものを選ぶ。選んだペアを $(a_{j+1}, b_{j+1})$ とする。
5. 新しい id $c_{j+1}$ を作り、$V_{j+1} := V_j \cup \{c_{j+1}\}$ とし、順序は $c_{j+1}$ を $V_j$ のどの元よりも大きいと定める。規則 $r_{j+1} := (a_{j+1}, b_{j+1} \mapsto c_{j+1})$ をすべての語に適用して $x_k^{(j+1)} := M_{r_{j+1}}\big(x_k^{(j)}\big)$ とする。$j$ を 1 増やして 2 に戻る。

終了したときの $j$ を $m'$（$\le m$）とする。出力は**マージ規則の列** $(r_1, \ldots, r_{m'})$ である。

一般に、マージ規則の列 $R = (r_1, \ldots, r_m)$（各 $r_j$ は、基本語彙に $r_1, \ldots, r_{j-1}$ を加えた語彙 $V_{j-1}$ の上の規則）に対し、**符号化** $\mathrm{enc}_R : \Sigma^{*} \to V_m^{*}$ を

$$
\mathrm{enc}_R(s) := M_{r_m}\big( \cdots M_{r_2}\big(M_{r_1}(s)\big) \cdots \big)
$$

で定める。すなわち、記号列を基本語彙のトークン列とみなし、規則を**学習した順に** 1 つずつ適用する。

</Definition>

手順 4 の「同数のときの選び方」を定義に含めたのは、これが無いと学習の結果が実装によって変わるからです。全順序の取り方は何でもかまいませんが、決めておけば、同じコーパスと同じ $m$ からは必ず同じ規則の列が得られます。バイトレベルの実装では、バイトの値と id の整数としての大小を使えば手順 5 の順序と一致します。

<Definition id="def-utf8" title="バイトレベル BPE・特殊トークン・圧縮率">

**UTF-8** は、Unicode の符号位置（文字に割り当てた整数）を 1〜4 バイトの列に写す規格である。符号位置が U+0000〜U+007F のとき 1 バイト `0xxxxxxx`、U+0080〜U+07FF のとき 2 バイト `110xxxxx 10xxxxxx`、U+0800〜U+FFFF のとき 3 バイト `1110xxxx 10xxxxxx 10xxxxxx`、U+10000〜U+10FFFF のとき 4 バイト `11110xxx 10xxxxxx 10xxxxxx 10xxxxxx` になる（`x` に符号位置の 2 進表示を上位から入れる。[4]）。先頭が `10` のバイトを**継続バイト**という。

$\Sigma = \{0, \ldots, 255\}$ とし、文字列を UTF-8 のバイト列に直してから BPE の学習・符号化を行う方式を**バイトレベル BPE** という。

文の終わりや区切りを表すために、マージ規則とは別に語彙へ加える id を**特殊トークン**という。特殊トークンは符号化 $\mathrm{enc}_R$ の出力には現れず、システムが列に挿入する。

空でないバイト列 $s$ について、$|s| / |\mathrm{enc}_R(s)|$ を $s$ に対する**圧縮率**（1 トークンあたりのバイト数）という。

</Definition>

ひらがなや漢字の多くは U+0800〜U+FFFF にあるので 1 文字が 3 バイトです。たとえば「数学は積み重ねです」は 9 文字で 27 バイトになり、マージを 1 つも学習していないバイトレベル BPE ではトークン数も 27 です。

## 3. 往復の一致と語彙の大きさ

最初に、マージの適用 1 回について成り立つことを補題にまとめます。以降の命題はすべてこの補題から出ます。

次の補題は、「置き換えても表す文字列は変わらない」「置き換えた回数だけ長さが減る」という、直感的には当たり前に見える 4 つの事実を確かめるものです。証明では、列の先頭の 1〜2 個を見て、残りの短い列に同じことを使う、という形の帰納法を 1 回だけ行い、その中で 4 つをまとめて示します。<Ref to="def-merge" /> の場合分け（先頭が $(a, b)$ のとき、そうでないとき）の 2 通りを順に見ればよく、新しい工夫はありません。

<Lemma id="lem-merge-step" title="マージの適用 1 回の性質">

$r = (a, b \mapsto c)$ をマージ規則、$x \in V'^{*}$ をトークン列とする。次が成り立つ。

1. $\mathrm{dec}(M_r(x)) = \mathrm{dec}(x)$。
2. $|M_r(x)| = |x| - \mathrm{rep}_r(x)$。
3. $\mathrm{rep}_r(x) \le \mathrm{cnt}_x(a, b)$ であり、$\mathrm{cnt}_x(a, b) \ge 1$ ならば $\mathrm{rep}_r(x) \ge 1$。
4. $a \ne b$ ならば $\mathrm{rep}_r(x) = \mathrm{cnt}_x(a, b)$。

</Lemma>

<Proof of="lem-merge-step">

列の長さ $n = |x|$ についての帰納法（長さが $n$ 未満のすべての列で成り立つと仮定して $n$ で示す形。<Ref to="mathematics/foundations/proof-techniques#thm-strong-induction" />）で、1〜4 を同時に示します。

$n = 0, 1$ のとき、$M_r(x) = x$、$\mathrm{rep}_r(x) = 0$、$\mathrm{cnt}_x(a, b) = 0$ なので、1〜4 はすべて成り立ちます。

$n \ge 2$ とし、$x = t_1 t_2 u$ と書きます。

**$(t_1, t_2) = (a, b)$ のとき。** $M_r(x) = c\,M_r(u)$、$\mathrm{rep}_r(x) = 1 + \mathrm{rep}_r(u)$ です。$u$ の長さは $n - 2$ なので帰納法の仮定が使えます。

1. $\mathrm{dec}(M_r(x)) = \langle\!\langle c \rangle\!\rangle\, \mathrm{dec}(M_r(u)) = \langle\!\langle a \rangle\!\rangle \langle\!\langle b \rangle\!\rangle\, \mathrm{dec}(u) = \mathrm{dec}(x)$。2 つ目の等号で $\langle\!\langle c \rangle\!\rangle = \langle\!\langle a \rangle\!\rangle \langle\!\langle b \rangle\!\rangle$（<Ref to="def-merge" />）と仮定の 1 を使いました。
2. $|M_r(x)| = 1 + |M_r(u)| = 1 + (n - 2) - \mathrm{rep}_r(u) = n - (1 + \mathrm{rep}_r(u)) = |x| - \mathrm{rep}_r(x)$。
3. $x$ での出現は、位置 1 の出現と、$u$ の中の出現を含むので $\mathrm{cnt}_x(a, b) \ge 1 + \mathrm{cnt}_u(a, b) \ge 1 + \mathrm{rep}_r(u) = \mathrm{rep}_r(x)$。また $\mathrm{rep}_r(x) \ge 1$ です。
4. $a \ne b$ とします。位置 2 から始まるペアは $(t_2, t_3) = (b, t_3)$ で、$b \ne a$ なので $(a, b)$ ではありません。したがって $x$ での出現は位置 1 と $u$ の中の出現だけで、$\mathrm{cnt}_x(a, b) = 1 + \mathrm{cnt}_u(a, b) = 1 + \mathrm{rep}_r(u) = \mathrm{rep}_r(x)$。

**$(t_1, t_2) \ne (a, b)$ のとき。** $M_r(x) = t_1\,M_r(t_2 u)$、$\mathrm{rep}_r(x) = \mathrm{rep}_r(t_2 u)$ です。$t_2 u$ の長さは $n - 1$ なので仮定が使えます。位置 1 は出現でないので $\mathrm{cnt}_x(a, b) = \mathrm{cnt}_{t_2 u}(a, b)$ です。

1. $\mathrm{dec}(M_r(x)) = \langle\!\langle t_1 \rangle\!\rangle\, \mathrm{dec}(M_r(t_2 u)) = \langle\!\langle t_1 \rangle\!\rangle\, \mathrm{dec}(t_2 u) = \mathrm{dec}(x)$。
2. $|M_r(x)| = 1 + (n - 1) - \mathrm{rep}_r(t_2 u) = |x| - \mathrm{rep}_r(x)$。
3. $\mathrm{rep}_r(x) = \mathrm{rep}_r(t_2 u) \le \mathrm{cnt}_{t_2 u}(a, b) = \mathrm{cnt}_x(a, b)$。$\mathrm{cnt}_x(a, b) \ge 1$ なら $\mathrm{cnt}_{t_2 u}(a, b) \ge 1$ で、仮定より $\mathrm{rep}_r(t_2 u) \ge 1$。
4. $a \ne b$ なら仮定より $\mathrm{rep}_r(t_2 u) = \mathrm{cnt}_{t_2 u}(a, b)$ で、両辺はそれぞれ $\mathrm{rep}_r(x)$、$\mathrm{cnt}_x(a, b)$ に等しい。

</Proof>

<Theorem id="thm-bpe-roundtrip" title="符号化と復号の往復">

$R = (r_1, \ldots, r_m)$ を任意のマージ規則の列とする。符号化 $\mathrm{enc}_R$ は $\Sigma^{*}$ の全体で定義され、任意の記号列 $s \in \Sigma^{*}$ について

$$
\mathrm{dec}\big(\mathrm{enc}_R(s)\big) = s
$$

が成り立つ。とくにバイトレベル BPE では、任意のバイト列（したがって UTF-8 で表せる任意の文字列）が符号化でき、語彙に無いために表せない入力（未知語）は存在しない。

</Theorem>

<Proof of="thm-bpe-roundtrip">

まず全域性を確かめます。$M_r$ は長さについての再帰で定義されており、再帰のたびに引数の長さが 1 以上減るので、どの列に対しても有限回で値が定まります。$\mathrm{enc}_R$ はそれを $m$ 回合成したものなので、すべての $s \in \Sigma^{*}$ に対して定義されます。$s$ の各記号は基本語彙のトークンなので、入力に「語彙に無い記号」はありえません。

次に等式を、適用した規則の個数 $j$ についての帰納法（<Ref to="mathematics/foundations/proof-techniques#thm-induction" />）で示します。$y_0 := s$、$y_j := M_{r_j}(y_{j-1})$ と置き、$\mathrm{dec}(y_j) = s$ を示します。

$j = 0$ のとき、$y_0 = s$ は基本語彙のトークン列で、$\langle\!\langle a \rangle\!\rangle = a$ なので $\mathrm{dec}(y_0) = s$ です。

$j - 1$ で成り立つとすると、<Ref to="lem-merge-step" /> の 1 より $\mathrm{dec}(y_j) = \mathrm{dec}(M_{r_j}(y_{j-1})) = \mathrm{dec}(y_{j-1}) = s$ です。

$\mathrm{enc}_R(s) = y_m$ なので主張が従います。

</Proof>

この定理は「マージ規則の列がどのように作られたか」を使っていません。学習で得た列でも、手で書いた列でも成り立ちます。逆向きの $\mathrm{enc}_R(\mathrm{dec}(x)) = x$ は一般には成り立ちません。<Ref to="ex-same-string" /> で見ます。

<Proposition id="prop-bpe-vocab-size" title="語彙の大きさ">

$m$ 個のマージ規則の列で広げた語彙 $V_m$ の大きさは $|V_m| = |\Sigma| + m$ である。とくに BPE の学習が $m'$ 回のマージで終了したとき、語彙の大きさは $|\Sigma| + m'$ である。

</Proposition>

<Proof of="prop-bpe-vocab-size">

$j$ についての帰納法です。$|V_0| = |\Sigma|$。規則 $r_j$ は $V_{j-1}$ に属さない id を 1 つだけ加えるので（<Ref to="def-merge" />）、$|V_j| = |V_{j-1}| + 1$。したがって $|V_m| = |\Sigma| + m$ です。

</Proof>

<Example id="ex-same-string" title="異なる id が同じ記号列を表す例">

id の個数は $|\Sigma| + m$ ですが、表す記号列がすべて異なるとは限りません。$\Sigma = \{\mathrm{a}, \mathrm{b}, \mathrm{c}\}$ とし、手で書いた規則の列

$$
r_1 = (\mathrm{a}, \mathrm{b} \mapsto 4), \quad r_2 = (\mathrm{b}, \mathrm{c} \mapsto 5), \quad r_3 = (4, \mathrm{c} \mapsto 6), \quad r_4 = (\mathrm{a}, 5 \mapsto 7)
$$

を考えます。$\langle\!\langle 4 \rangle\!\rangle = \mathrm{ab}$、$\langle\!\langle 5 \rangle\!\rangle = \mathrm{bc}$ で、$\langle\!\langle 6 \rangle\!\rangle = \mathrm{ab}\cdot\mathrm{c} = \mathrm{abc}$、$\langle\!\langle 7 \rangle\!\rangle = \mathrm{a}\cdot\mathrm{bc} = \mathrm{abc}$ です。id 6 と 7 は同じ記号列を表します。したがって $\mathrm{dec}$ は単射ではなく、$\mathrm{dec}((6)) = \mathrm{dec}((7)) = \mathrm{abc}$ です。

それでも符号化は 1 通りに決まります。$\mathrm{enc}_R$ は規則を決まった順に決まった向きで適用する関数だからです。実際、$\mathrm{abc}$ に $r_1$ を適用すると $(4, \mathrm{c})$、$r_2$ は当てはまる箇所がなく、$r_3$ で $(6)$、$r_4$ は当てはまらず、$\mathrm{enc}_R(\mathrm{abc}) = (6)$ です。一方 $\mathrm{enc}_R(\mathrm{dec}((7))) = (6) \ne (7)$ なので、復号してから符号化し直すと元のトークン列に戻らないことがあります。

この規則の列は説明のために手で書いたもので、<Ref to="def-bpe" /> の学習の出力として得られるとは主張しません。

</Example>

## 4. 長さの単調性と学習の停止性

<Proposition id="prop-bpe-length-monotone" title="トークン数は増えない">

$r = (a, b \mapsto c)$ をマージ規則、$x$ をトークン列とする。

1. $|M_r(x)| = |x| - \mathrm{rep}_r(x) \le |x|$。すなわちマージを 1 つ適用するとトークン数はちょうど $\mathrm{rep}_r(x)$（重なりを除いて左から数えた $(a, b)$ の出現回数）だけ減り、増えることはない。$a \ne b$ なら減る数は出現回数 $\mathrm{cnt}_x(a, b)$ に等しい。
2. 任意のマージ規則の列 $R$ と記号列 $s$ について $|\mathrm{enc}_R(s)| \le |s|$。$s \ne \varepsilon$ なら $|\mathrm{enc}_R(s)| \ge 1$。

</Proposition>

<Proof of="prop-bpe-length-monotone">

1 は <Ref to="lem-merge-step" /> の 2 と 4、および $\mathrm{rep}_r(x) \ge 0$ から従います。

2 の前半は、1 を $r_1, \ldots, r_m$ に順に使って $|s| = |y_0| \ge |y_1| \ge \cdots \ge |y_m| = |\mathrm{enc}_R(s)|$ です（$y_j$ は <Ref to="thm-bpe-roundtrip" /> の証明と同じ）。後半は、$|\mathrm{enc}_R(s)| = 0$ なら $\mathrm{enc}_R(s) = \varepsilon$ で、<Ref to="thm-bpe-roundtrip" /> より $s = \mathrm{dec}(\varepsilon) = \varepsilon$ となることの対偶です。

</Proof>

2 から、圧縮率 $|s| / |\mathrm{enc}_R(s)|$ は必ず 1 以上です。

<Proposition id="prop-bpe-training-termination" title="学習の停止性とマージ回数の上界">

コーパス $C = (w_1, \ldots, w_K)$ の総記号数を $N := \sum_{k=1}^{K} |w_k|$ とする。<Ref to="def-bpe" /> の学習は、$m$ の値によらず（$m$ を上限なしにしても）有限回で終了し、行われるマージの回数 $m'$ は

$$
m' \le N - K
$$

を満たす。

</Proposition>

<Proof of="prop-bpe-training-termination">

$j$ 回のマージのあとの総トークン数を $T_j := \sum_{k=1}^{K} \big|x_k^{(j)}\big|$ とし、$v_j := T_j - K$ と置きます。$v$ が学習のループの変量（<Ref to="computer-science/software-design-testing/contracts-and-invariants#def-variant" />）であることを示します。

**下に有界。** 各語 $w_k$ は空でなく、$\mathrm{dec}\big(x_k^{(j)}\big) = w_k \ne \varepsilon$（<Ref to="lem-merge-step" /> の 1 を $j$ 回）なので $\big|x_k^{(j)}\big| \ge 1$ です。よって $T_j \ge K$、$v_j \ge 0$ です。

**真に減る。** $j + 1$ 回目のマージが行われるのは、手順 3 を通過したとき、すなわち選ばれたペアの出現回数が $N_j(a_{j+1}, b_{j+1}) \ge 1$ のときです。するとある語 $k_0$ で $\mathrm{cnt}_{x_{k_0}^{(j)}}(a_{j+1}, b_{j+1}) \ge 1$ で、<Ref to="lem-merge-step" /> の 3 より $\mathrm{rep}_{r_{j+1}}\big(x_{k_0}^{(j)}\big) \ge 1$ です。<Ref to="prop-bpe-length-monotone" /> の 1 より、その語のトークン数は 1 以上減り、ほかの語のトークン数は増えません。したがって $T_{j+1} \le T_j - 1$、$v_{j+1} \le v_j - 1$ です。

非負の整数値を取り、ループを 1 回まわるごとに 1 以上減る量があるので、ループは有限回で終了します（<Ref to="computer-science/software-design-testing/contracts-and-invariants#thm-total-correctness" /> の 1）。回数については、$v_0 = N - K$ で、$m'$ 回のマージのあと $0 \le v_{m'} \le v_0 - m'$ なので $m' \le N - K$ です。

</Proof>

上界 $N - K$ は、すべての語がトークン 1 個になった状態に対応します。そのときどの語にも隣接ペアが無いので、手順 3 で必ず終了します。

<Example id="ex-training-trace" title="小さなコーパスで 5 回のマージを追う">

コーパスを、語 slow が 4 個、slower が 2 個、lowest が 3 個、newest が 3 個の計 $K = 12$ 語とします。総記号数は $N = 4\cdot4 + 2\cdot6 + 3\cdot6 + 3\cdot6 = 64$ です。記号の順序は文字コードの順（$\mathrm{e} < \mathrm{l} < \mathrm{n} < \mathrm{o} < \mathrm{r} < \mathrm{s} < \mathrm{t} < \mathrm{w}$）とし、新しいトークンはそれらより大きいとします。

| 回 | 選ばれたペア | 出現回数 | 同数だったほかのペア | 新しいトークン | 総トークン数 | 各語の分割（slow / slower / lowest / newest） |
|---|---|---|---|---|---|---|
| 0 | | | | | 64 | s l o w / s l o w e r / l o w e s t / n e w e s t |
| 1 | (l, o) | 9 | (o, w) | lo | 55 | s lo w / s lo w e r / lo w e s t / n e w e s t |
| 2 | (lo, w) | 9 | なし | low | 46 | s low / s low e r / low e s t / n e w e s t |
| 3 | (e, s) | 6 | (s, t)、(s, low) | es | 40 | s low / s low e r / low es t / n e w es t |
| 4 | (s, low) | 6 | (es, t) | slow | 34 | slow / slow e r / low es t / n e w es t |
| 5 | (es, t) | 6 | なし | est | 28 | slow / slow e r / low est / n e w est |

1 回目は (l, o) と (o, w) がともに 9 回（slow 4 + slower 2 + lowest 3）で並び、$\mathrm{l} < \mathrm{o}$ なので (l, o) が選ばれます。3 回目は 3 つのペアが 6 回で並び、第 1 成分が最小の (e, s) が選ばれます。4 回目は (s, low) と (es, t) が並びますが、s は基本の記号で、あとから作った es より小さいので (s, low) です。

総トークン数は $64 \to 55 \to 46 \to 40 \to 34 \to 28$ と、毎回ちょうど出現回数だけ減っています。5 回とも $a \ne b$ なので、<Ref to="prop-bpe-length-monotone" /> の 1 のとおりです。5 回のマージ後の圧縮率は $64 / 28 \approx 2.29$ バイト／トークン、語彙の大きさはバイトレベルなら $256 + 5 = 261$ です。

このまま上限なしで続けると 11 回のマージで全語が 1 トークンになって終了します（総トークン数 12）。<Ref to="prop-bpe-training-termination" /> の上界 $N - K = 52$ よりずっと少ないのは、1 回のマージで総トークン数が 2 以上減ることが多いからです。

学習した 5 つの規則で、コーパスに無い語 slowest を符号化すると、s l o w e s t → s lo w e s t → s low e s t → s low es t → slow es t → slow est で、2 トークンになります。

</Example>

<Figure caption="slowest の符号化。下段の 7 個の記号が、学習した順（かっこ内の番号）にまとめられ、最終的に slow と est の 2 トークンになる。">
<svg viewBox="0 0 620 250" width="100%" role="img" aria-label="slowest を 5 つのマージ規則で符号化する過程の木">
  <g fill="none" stroke="currentColor" stroke-width="1.3">
    <rect x="40" y="195" width="44" height="34" rx="5" />
    <rect x="120" y="195" width="44" height="34" rx="5" />
    <rect x="200" y="195" width="44" height="34" rx="5" />
    <rect x="280" y="195" width="44" height="34" rx="5" />
    <rect x="360" y="195" width="44" height="34" rx="5" />
    <rect x="440" y="195" width="44" height="34" rx="5" />
    <rect x="520" y="195" width="44" height="34" rx="5" />
    <rect x="150" y="140" width="64" height="30" rx="5" />
    <rect x="205" y="88" width="74" height="30" rx="5" />
    <rect x="410" y="140" width="64" height="30" rx="5" />
    <rect x="465" y="88" width="74" height="30" rx="5" />
    <line x1="142" y1="195" x2="172" y2="170" />
    <line x1="222" y1="195" x2="192" y2="170" />
    <line x1="182" y1="140" x2="232" y2="118" />
    <line x1="302" y1="195" x2="256" y2="118" />
    <line x1="402" y1="195" x2="432" y2="170" />
    <line x1="462" y1="195" x2="452" y2="170" />
    <line x1="442" y1="140" x2="492" y2="118" />
    <line x1="542" y1="195" x2="512" y2="118" />
  </g>
  <g fill="none" stroke="var(--sl-color-accent)" stroke-width="1.8">
    <rect x="105" y="30" width="84" height="32" rx="5" />
    <line x1="62" y1="195" x2="130" y2="62" />
    <line x1="242" y1="88" x2="160" y2="62" />
    <rect x="460" y="86" width="84" height="34" rx="6" />
  </g>
  <g fill="currentColor" font-size="15" text-anchor="middle">
    <text x="62" y="217">s</text>
    <text x="142" y="217">l</text>
    <text x="222" y="217">o</text>
    <text x="302" y="217">w</text>
    <text x="382" y="217">e</text>
    <text x="462" y="217">s</text>
    <text x="542" y="217">t</text>
    <text x="182" y="160">lo (1)</text>
    <text x="242" y="108">low (2)</text>
    <text x="442" y="160">es (3)</text>
    <text x="502" y="108">est (5)</text>
    <text x="147" y="51">slow (4)</text>
  </g>
</svg>
</Figure>

<Proposition id="prop-bpe-training-cost" title="素朴な学習の計算量">

出現回数の表（ペアをキーとする辞書）の 1 回の更新・参照、トークン 1 個の比較と書き込みを、それぞれ 1 ステップと数える。コーパスの総記号数を $N$、行うマージの回数を $m$ とすると、<Ref to="def-bpe" /> の手順をそのまま実行する実装のステップ数は $O(mN)$ である（$m \ge 1$ のとき）。

</Proposition>

<Proof of="prop-bpe-training-cost">

$j + 1$ 回目の反復のステップ数を見積もります。総トークン数は $T_j \le T_0 = N$ です（<Ref to="prop-bpe-length-monotone" />）。

- 手順 2（数える）: 各語の隣接ペアを 1 つずつ表に加える。隣接ペアの総数は $\sum_k \big(\big|x_k^{(j)}\big| - 1\big) \le T_j \le N$ なので、$N$ ステップ以下。
- 手順 3・4（選ぶ）: 表に載っている相異なるペアは高々 $N$ 個。最大値を探し、同数のものを辞書式に比べるのに、表の各項目につき定数ステップなので、ある定数 $\alpha$ について $\alpha N$ ステップ以下。
- 手順 5（適用する）: $M_r$ は各語を左から 1 回走査し、トークン 1 個につき定数回の比較と書き込みをするので、ある定数 $\beta$ について $\beta T_j \le \beta N$ ステップ以下。

よって 1 回の反復は $(1 + \alpha + \beta) N$ ステップ以下で、$m$ 回の反復の合計は $(1 + \alpha + \beta)\, mN$ 以下です。初期化（語をトークン列に写す）は $N$ ステップです。合計は $O(mN)$ です（$O$ 記法の定義は <Ref to="computer-science/algorithms/complexity-and-big-o#def-big-o" />、和と定数倍の扱いは <Ref to="computer-science/algorithms/complexity-and-big-o#prop-calculus" /> の 3 と 4）。

</Proof>

<Remark id="rem-faster-training">

<Ref to="prop-bpe-training-termination" /> より $m \le N - K$ なので、上限なしで学習すると最悪 $O(N^2)$ です。実用の実装は、(1) 同じ語をまとめて「語と頻度」の表にする、(2) ペアごとの出現位置の索引を持ち、マージで変わる箇所の回数だけを増減する、(3) 最大のペアを優先度つきキューで取り出す、という工夫で、毎回の全走査を避けます。この記事ではこれらの計算量の証明はしません。Sennrich らも、語をまたぐペアを数えないことで、頻度つきの語の辞書の上で学習できると述べています（[2]）。<Ref to="def-bpe" /> でコーパスを語の列としたのは、この形に合わせるためです。

</Remark>

## 5. 貪欲な符号化は最短とは限らない

なお、次の命題の後半は動的計画法の応用です。「先頭 $i$ 記号の最短の分け方」を $i$ の小さい方から順に表にしていき、最後のトークン 1 個を選ぶ候補を全部試して最小を取る、という考え方です。

語彙 $V_m$ を固定すると、記号列 $s$ を「$V_m$ のトークンの表す記号列の連結」に分ける方法は一般に複数あります。BPE の符号化はそのうちの 1 つを選びますが、それがトークン数最小とは限りません。

<Proposition id="prop-bpe-greedy-not-optimal" title="BPE の符号化は最短分割とは限らない">

あるコーパスから <Ref to="def-bpe" /> の学習で得たマージ規則の列 $R$ と記号列 $s$ で、$\mathrm{dec}(x) = s$ を満たすトークン列 $x \in V_m^{*}$ のうちに $|x| < |\mathrm{enc}_R(s)|$ となるものが存在する例がある。

一方、語彙 $V$ と記号列 $s$（$|s| = n$）が与えられたとき、$\mathrm{dec}(x) = s$ を満たす最短の $x$ の長さは、$V$ のトークンの表す記号列の最大の長さを $\ell_{\max}$ として、「$s$ の連続する一部分（第 $j$ 〜 $i$ 記号）が $V$ のどれかのトークンの表す記号列か」の判定を $O(n\,\ell_{\max})$ 回行えば求まる。

</Proposition>

<Proof of="prop-bpe-greedy-not-optimal">

**反例。** $\Sigma = \{\mathrm{a}, \mathrm{b}, \mathrm{c}, \mathrm{d}\}$（順序は $\mathrm{a} < \mathrm{b} < \mathrm{c} < \mathrm{d}$）、コーパスを ab が 4 個、bcd が 2 個、bc が 1 個とし、$m = 3$ とします。

- 1 回目: 出現回数は (a, b) が 4、(b, c) が 3、(c, d) が 2。最大は (a, b) で、新しいトークン ab ができます。語 bcd と bc には a が無いので変わりません。
- 2 回目: (b, c) が 3、(c, d) が 2。最大は (b, c) で、bc ができます。語 bcd は (bc, d)、語 bc は (bc) になります。
- 3 回目: 残るペアは (bc, d) の 2 回だけで、bcd ができます。

したがって $R$ は $r_1 = (\mathrm{a}, \mathrm{b} \mapsto \mathrm{ab})$、$r_2 = (\mathrm{b}, \mathrm{c} \mapsto \mathrm{bc})$、$r_3 = (\mathrm{bc}, \mathrm{d} \mapsto \mathrm{bcd})$ で、語彙の表す記号列は a, b, c, d, ab, bc, bcd の 7 個です（ここではトークンを表す記号列で呼んでいます）。

$s = \mathrm{abcd}$ を符号化します。$r_1$ で (ab, c, d)。$r_2$ は「b の直後に c」を探しますが、b はすでに ab の中に取り込まれていて、列には b というトークンがありません。$r_3$ も bc が無いので当てはまりません。よって $\mathrm{enc}_R(\mathrm{abcd}) = (\mathrm{ab}, \mathrm{c}, \mathrm{d})$ で 3 トークンです。ところが $x = (\mathrm{a}, \mathrm{bcd})$ は同じ語彙のトークン列で $\mathrm{dec}(x) = \mathrm{abcd}$、長さは 2 です。

**最短分割の計算。** $i = 0, 1, \ldots, n$ について、$s$ の先頭 $i$ 記号を表す最短のトークン列の長さを $f(i)$ と置きます（表せないときは $+\infty$）。$f(0) = 0$ で、$i \ge 1$ では

$$
f(i) = 1 + \min\big\{ f(i - \ell) : 1 \le \ell \le \min(\ell_{\max}, i),\ s \text{ の第 } i - \ell + 1 \text{ 〜 } i \text{ 記号が、あるトークンの表す記号列に等しい} \big\}
$$

が成り立ちます（該当する $\ell$ が無ければ $+\infty$）。理由は次のとおりです。先頭 $i$ 記号を表すトークン列の最後のトークンの表す記号列の長さを $\ell$ とすると、$1 \le \ell \le \min(\ell_{\max}, i)$ で、残りは先頭 $i - \ell$ 記号を表すトークン列なので長さは $f(i - \ell)$ 以上、よって全体は右辺以上です。逆に、右辺の最小を与える $\ell$ について、先頭 $i - \ell$ 記号の最短のトークン列の末尾にそのトークンを足せば、長さが右辺に等しいトークン列ができます。

これは、部分問題が $n + 1$ 個、$f(i)$ の依存先が $f(i - 1), \ldots, f(i - \ell_{\max})$ で、依存の向きが添字の小さい方に限られる（閉路が無い）部分問題族です。各 $f(i)$ の評価は高々 $\ell_{\max}$ 回の判定と比較なので、<Ref to="computer-science/algorithms/dynamic-programming#thm-memo-cost" /> より、全体は $O(n\,\ell_{\max})$ 回の判定で求まります。求める値は $f(n)$ です。

</Proof>

貪欲さの原因は、先に学習した規則が後の規則の材料を消費してしまうことです。それでも BPE の符号化が使われるのは、学習時にコーパスに施したのと同じ分割を符号化時にも再現するためです。モデルは学習時に見た分割のしかたでトークンの意味を覚えるので、符号化時だけ別の（短い）分割にすると、学習時に見ていない並びを入力することになります。

## 6. トークンが運べる情報量と、文字の境界

<Proposition id="prop-token-information" title="トークン列の総数と情報量">

語彙の大きさを $|V| \ge 2$ とする。

1. 長さ $n$ のトークン列は全部で $|V|^{n}$ 個ある。
2. 有限集合 $\mathcal{M}$ から長さ $n$ のトークン列の全体への単射が存在するならば、$|\mathcal{M}| \le |V|^{n}$、すなわち $\log_2 |\mathcal{M}| \le n \log_2 |V|$ である。言い換えると、トークン 1 個が区別できる場合の数は $|V|$ 通り、ビットに直すと $\log_2 |V|$ ビット以下である。

</Proposition>

<Proof of="prop-token-information">

1 は $n$ についての帰納法です。$n = 0$ のとき空列 1 個で $|V|^0 = 1$。長さ $n$ の列は、長さ $n - 1$ の列（$|V|^{n-1}$ 個）の末尾に $|V|$ 通りのトークンのどれかを足したもので、足し方が違えば列も違うので、$|V|^{n-1}\cdot|V| = |V|^{n}$ 個です。

2 は、単射の像が $\mathcal{M}$ と同じ個数の元を持つ部分集合であることから $|\mathcal{M}| \le |V|^{n}$。両辺の $\log_2$ を取ると（$\log_2$ は単調増加）$\log_2|\mathcal{M}| \le n\log_2|V|$ です。$n = 1$ のときが「トークン 1 個」の主張です。

</Proof>

<Example id="ex-bits-per-token" title="圧縮率との関係">

Radford らの語彙の大きさは 50,257 です（[3]）。$\log_2 50257 \approx 15.62$ なので、この語彙のトークン 1 個が区別できるのは 16 ビット弱の分です。

一方、圧縮率が仮に 4 バイト／トークンだとすると、トークン 1 個は平均して元のバイト列の 32 ビット分にあたります。4 バイトの列は $256^4 = 2^{32}$ 通りありますが、トークン 1 個は 50,257 通りしか区別できません。すべてのバイト列を 4 バイト／トークンで符号化することは <Ref to="prop-token-information" /> より不可能で、圧縮率が 1 を大きく超えるのは、自然言語の文に現れるバイト列が全体のごく一部に偏っているからです。ランダムなバイト列ではマージがほとんど当てはまらず、圧縮率は 1 に近くなります。

<Ref to="ex-training-trace" /> の例では、語彙 261（$\log_2 261 \approx 8.03$ ビット）で圧縮率が 2.29 でした。マージを増やすほど列は短くなりますが、語彙は 1 つずつ増えます。

| マージ回数 | 語彙の大きさ | コーパスの総トークン数 | 圧縮率 |
|---|---|---|---|
| 0 | 256 | 64 | 1.00 |
| 2 | 258 | 46 | 1.39 |
| 5 | 261 | 28 | 2.29 |
| 10 | 266 | 14 | 4.57 |
| 11 | 267 | 12 | 5.33 |

語彙を大きくする代償は、次章で見る埋め込み行列の大きさです。埋め込みの次元を $d$ とすると行列は $|V| \times d$ で、語彙が 1 増えるごとにパラメータが $d$ 個増えます。列が短くなる利得（注意の計算量は列の長さの 2 乗に比例します）と、この行列の大きさ、そして珍しいトークンほど学習データに現れる回数が減ることとの釣り合いで、$m$ を決めます。

</Example>

<Proposition id="prop-utf8-boundary" title="トークンの境界は文字の境界と一致するとは限らない">

バイトレベル BPE では、学習で得たマージ規則の列 $R$ と、UTF-8 として正しいバイト列 $s$ で、$\mathrm{enc}_R(s)$ の中に「表すバイト列が単独では UTF-8 として正しくない」トークンが現れる例がある。したがって、トークン列を文字列に戻すときは、トークンごとに UTF-8 として解釈するのではなく、$\mathrm{dec}$ で連結したバイト列の全体を解釈しなければならない。

</Proposition>

<Proof of="prop-utf8-boundary">

「あ」の符号位置は U+3042、「い」は U+3044 で、どちらも U+0800〜U+FFFF にあるので 3 バイトです（<Ref to="def-utf8" />）。16 進で「あ」は E3 81 82、「い」は E3 81 84 になります。

コーパスを、語「あい」（バイト列 E3 81 82 E3 81 84）2 個とし、$m = 1$ で学習します。語 1 個の中の隣接ペアは (E3, 81) が 2 回、(81, 82)、(82, E3)、(81, 84) が 1 回ずつなので、コーパス全体では (E3, 81) が 4 回で最大です。規則は $r_1 = (\mathrm{E3}, \mathrm{81} \mapsto 256)$ で、トークン 256 の表すバイト列は E3 81 です。

$s$ を「あ」のバイト列 E3 81 82 とすると、$\mathrm{enc}_R(s) = (256, \mathrm{82})$ です。トークン 256 の E3 81 は、先頭バイト E3（2 進で 11100011、3 バイトの文字の先頭）のあとに継続バイトが 1 個しか無いので、UTF-8 として正しくありません。トークン 82（2 進で 10000010）は継続バイトだけで、先頭バイトが無いのでこれも正しくありません。

一方 <Ref to="thm-bpe-roundtrip" /> より $\mathrm{dec}((256, \mathrm{82})) = s$ で、連結した全体は「あ」の正しい UTF-8 です。

</Proof>

<Figure caption="「あ」の UTF-8 の 3 バイトと、トークンの切れ目。トークン 256 は E3 81 の 2 バイトを表し、文字の途中で切れている。">
<svg viewBox="0 0 520 150" width="100%" role="img" aria-label="あの 3 バイト E3 81 82 のうち、最初の 2 バイトが 1 つのトークン、最後の 1 バイトが別のトークンになる様子">
  <g fill="none" stroke="currentColor" stroke-width="1.3">
    <rect x="60" y="55" width="120" height="40" rx="5" />
    <rect x="180" y="55" width="120" height="40" rx="5" />
    <rect x="300" y="55" width="120" height="40" rx="5" />
  </g>
  <g fill="none" stroke="var(--sl-color-accent)" stroke-width="1.8">
    <rect x="60" y="102" width="240" height="30" rx="5" />
    <rect x="300" y="102" width="120" height="30" rx="5" />
    <path d="M60 40 H420" />
  </g>
  <g fill="currentColor" font-size="15" text-anchor="middle">
    <text x="120" y="80">E3</text>
    <text x="240" y="80">81</text>
    <text x="360" y="80">82</text>
    <text x="180" y="122">トークン 256</text>
    <text x="360" y="122">トークン 82</text>
    <text x="240" y="28">文字「あ」</text>
  </g>
</svg>
</Figure>

文字の途中でトークンが切れると、トークンを 1 個ずつ生成して画面に出す場面で問題になります。直前までのバイト列が文字の途中で終わっているあいだは表示を保留し、文字が完成してから出す必要があります。

<Remark id="rem-other-tokenizers" title="ほかの分割方式">

サブワードへの分割には BPE 以外の方式もあります。Kudo は、ユニグラム言語モデル（各サブワードに確率を割り当て、分割の確率をその積とする模型）に基づいて、1 つの文に対する複数の分割を確率つきで扱う方法を提案しました（[5]）。BPE の符号化が決定的に 1 つの分割を返すのに対し、こちらは分割の候補に確率が付く点が違います。WordPiece と呼ばれる方式も、マージするペアの選び方と符号化の手続きが BPE と異なります。

文字単位（バイト単位）は、この記事の枠組みでは $m = 0$ の場合です。単語単位は、語彙を「学習データに現れた単語」に固定する方式で、語彙に無い単語を表せない点が <Ref to="thm-bpe-roundtrip" /> と対照的です。どの方式が良いかは、言語やデータに依る経験的な問題です。

</Remark>

## 7. 最小実装と検査

バイトレベル BPE の学習・符号化・復号を、Python の標準ライブラリだけで書きます。`apply_merge` が <Ref to="def-merge" /> の $M_r$、`train` が <Ref to="def-bpe" /> の学習、`encode` が $\mathrm{enc}_R$、`decode` が $\mathrm{dec}$ です。新しいトークンの id は 256 から順に振るので、整数の大小が手順 5 の順序になります。

```python
# Python 3.12.14（標準ライブラリのみ）
import random
from collections import Counter

def apply_merge(seq, pair, new_id):
    """列 seq を左から走査し、隣り合う pair を new_id に置き換える。"""
    out, i = [], 0
    while i < len(seq):
        if i + 1 < len(seq) and (seq[i], seq[i + 1]) == pair:
            out.append(new_id); i += 2
        else:
            out.append(seq[i]); i += 1
    return out

def train(words, num_merges):
    """words: bytes のリスト（コーパス）。マージ規則の列を返す。"""
    seqs = [list(w) for w in words]
    merges = []
    for step in range(num_merges):
        counts = Counter()
        for s in seqs:
            counts.update(zip(s, s[1:]))
        if not counts:
            break
        best = max(counts.values())
        pair = min(p for p, c in counts.items() if c == best)  # 同数なら id の辞書式順序で最小
        new_id = 256 + step
        seqs = [apply_merge(s, pair, new_id) for s in seqs]
        merges.append(pair)
    return merges

def encode(data, merges):
    seq = list(data)
    for step, pair in enumerate(merges):
        seq = apply_merge(seq, pair, 256 + step)
    return seq

def token_bytes(merges):
    table = [bytes([b]) for b in range(256)]
    for a, b in merges:
        table.append(table[a] + table[b])
    return table

def decode(ids, merges):
    table = token_bytes(merges)
    return b"".join(table[t] for t in ids)

if __name__ == "__main__":
    corpus = [b"slow"] * 4 + [b"slower"] * 2 + [b"lowest"] * 3 + [b"newest"] * 3
    merges = train(corpus, 5)
    table = token_bytes(merges)
    for step, (a, b) in enumerate(merges):
        print(256 + step, table[a], "+", table[b], "->", table[256 + step])
    print([table[t] for t in encode(b"slowest", merges)])

    random.seed(0)
    ok = 0
    for trial in range(2000):
        n = random.randrange(0, 40)
        alphabet = b"elnostw" if trial % 2 == 0 else bytes(range(256))
        data = bytes(random.choice(alphabet) for _ in range(n))
        ids = encode(data, merges)
        assert decode(ids, merges) == data and len(ids) <= len(data)
        ok += 1
    print("roundtrip ok:", ok)
```

実行結果です。マージの順は <Ref to="ex-training-trace" /> の表と一致します。後半は、長さ 0〜39 のランダムなバイト列 2,000 本（半分はマージが当てはまりやすいように 7 文字だけから、半分は 256 種のバイト全体から選ぶ）で、往復の一致（<Ref to="thm-bpe-roundtrip" />）と長さが増えないこと（<Ref to="prop-bpe-length-monotone" />）を確かめています。

```text
256 b'l' + b'o' -> b'lo'
257 b'lo' + b'w' -> b'low'
258 b'e' + b's' -> b'es'
259 b's' + b'low' -> b'slow'
260 b'es' + b't' -> b'est'
[b'slow', b'est']
roundtrip ok: 2000
```

次に、<Ref to="prop-bpe-greedy-not-optimal" /> の反例を実行し、BPE の分割と動的計画法による最短分割を比べます。上のコードを `bpe.py` として保存してあるとします。

```python
# Python 3.12.14（標準ライブラリのみ）。bpe.py は前のコード
from bpe import train, encode, token_bytes

def shortest(data, vocab):
    """vocab（bytes の集合）のトークンへの分割のうち最短のものを動的計画法で求める。"""
    n, longest = len(data), max(len(t) for t in vocab)
    INF = float("inf")
    f, back = [0] + [INF] * n, [0] * (n + 1)
    for i in range(1, n + 1):
        for length in range(1, min(longest, i) + 1):
            if data[i - length:i] in vocab and f[i - length] + 1 < f[i]:
                f[i], back[i] = f[i - length] + 1, length
    parts, i = [], n
    while i > 0:
        parts.append(data[i - back[i]:i]); i -= back[i]
    return parts[::-1]

corpus = [b"ab"] * 4 + [b"bcd"] * 2 + [b"bc"]
merges = train(corpus, 3)
table = token_bytes(merges)
print("merges:", [(table[a], table[b]) for a, b in merges])
vocab = set(table[t] for t in list(b"abcd") + [256, 257, 258])
print("vocab :", sorted(vocab))
bpe = [table[t] for t in encode(b"abcd", merges)]
opt = shortest(b"abcd", vocab)
print("BPE   :", bpe, len(bpe))
print("DP    :", opt, len(opt))
```

```text
merges: [(b'a', b'b'), (b'b', b'c'), (b'bc', b'd')]
vocab : [b'a', b'ab', b'b', b'bc', b'bcd', b'c', b'd']
BPE   : [b'ab', b'c', b'd'] 3
DP    : [b'a', b'bcd'] 2
```

最後に <Ref to="prop-utf8-boundary" /> の例です。トークンを 1 個ずつ UTF-8 として解釈すると例外になり、連結してから解釈すると元の文字に戻ります。

```python
# Python 3.12.14（標準ライブラリのみ）。bpe.py は前のコード
from bpe import train, encode, decode, token_bytes

corpus = ["あい".encode("utf-8")] * 2
merges = train(corpus, 1)
table = token_bytes(merges)
print("あ =", "あ".encode("utf-8").hex(" "), "/ い =", "い".encode("utf-8").hex(" "))
print("merge:", table[merges[0][0]].hex(), "+", table[merges[0][1]].hex())
ids = encode("あ".encode("utf-8"), merges)
print("ids  :", ids, [table[t].hex() for t in ids])
for t in ids:
    try:
        print(t, "->", table[t].decode("utf-8"))
    except UnicodeDecodeError as e:
        print(t, "-> UnicodeDecodeError:", e.reason)
print("whole:", decode(ids, merges).decode("utf-8"))
```

```text
あ = e3 81 82 / い = e3 81 84
merge: e3 + 81
ids  : [256, 130] ['e381', '82']
256 -> UnicodeDecodeError: unexpected end of data
130 -> UnicodeDecodeError: invalid start byte
whole: あ
```

## 8. 次章へ：語彙の大きさがモデルの大きさを決める

この章で作ったのは、文字列からトークン id の列 $(t_1, \ldots, t_n)$、$t_i \in V$ への写像と、その逆向きの復号です。以降の章のモデルが見るのはこの id の列だけで、文字やバイトは見ません。モデルにとって id は順序も大きさも意味を持たない名前なので、次章ではまず各 id を $d$ 次元のベクトルに置き換えます。その表が $|V| \times d$ の埋め込み行列で、出力側でも「次のトークン」を $|V|$ 通りから選ぶために同じ大きさの行列が要ります。<Ref to="prop-bpe-vocab-size" /> の $|V| = |\Sigma| + m$ が、モデルの入口と出口の大きさをそのまま決めます。

## 9. 演習

<Exercise id="exr-apply-merge" difficulty="易">

(1) $r = (\mathrm{a}, \mathrm{a} \mapsto \mathrm{c})$ を列 $(\mathrm{a}, \mathrm{a}, \mathrm{a}, \mathrm{a})$ に適用した結果と、$\mathrm{cnt}$、$\mathrm{rep}$ の値を求めよ。(2) <Ref to="ex-training-trace" /> の 5 つの規則で lower を符号化せよ。

<Solution>

(1) 左から走査すると、位置 1・2 の (a, a) が c になり、次に位置 3・4 の (a, a) が c になるので、結果は (c, c) です。出現は位置 1, 2, 3 の 3 か所なので $\mathrm{cnt} = 3$、置き換えは 2 回なので $\mathrm{rep} = 2$ です。長さは $4 - 2 = 2$ で、<Ref to="lem-merge-step" /> の 2 と合います。

(2) l o w e r に (l, o) を適用して lo w e r、(lo, w) を適用して low e r。(e, s) は s が無いので変化なし、(s, low) は s が無いので変化なし、(es, t) も変化なしです。結果は (low, e, r) の 3 トークンです。

</Solution>
</Exercise>

<Exercise id="exr-run-length" difficulty="標準">

$r = (\mathrm{a}, \mathrm{a} \mapsto \mathrm{c})$ とし、$x$ を a が $\ell$ 個並んだ列とする。$\mathrm{rep}_r(x) = \lfloor \ell / 2 \rfloor$ であることを示せ。

<Solution>

$\ell$ についての帰納法で示します。$\ell = 0, 1$ のとき、<Ref to="def-merge" /> より $\mathrm{rep}_r(x) = 0 = \lfloor \ell/2 \rfloor$ です。$\ell \ge 2$ のとき、先頭の 2 個は (a, a) なので 1 つ目の場合にあたり、$\mathrm{rep}_r(x) = 1 + \mathrm{rep}_r(u)$ で、$u$ は a が $\ell - 2$ 個並んだ列です。帰納法の仮定より $\mathrm{rep}_r(u) = \lfloor (\ell - 2)/2 \rfloor = \lfloor \ell/2 \rfloor - 1$ なので、$\mathrm{rep}_r(x) = \lfloor \ell/2 \rfloor$ です。出現回数は $\mathrm{cnt}_x(\mathrm{a}, \mathrm{a}) = \ell - 1$ なので、$\ell \ge 3$ では $\mathrm{rep} < \mathrm{cnt}$ となり、<Ref to="lem-merge-step" /> の 4 に $a \ne b$ の仮定が要ることが分かります。

</Solution>
</Exercise>

<Exercise id="exr-bound-attained" difficulty="標準">

<Ref to="prop-bpe-training-termination" /> の上界 $m' \le N - K$ で等号が成り立つコーパスの例を、任意の $N \ge 2$、$K = 1$ について作れ。

<Solution>

相異なる $N$ 個の記号 $a_1 < a_2 < \cdots < a_N$ を並べた 1 語 $w = a_1 a_2 \cdots a_N$ をコーパスとし、上限なしで学習します。次を帰納法で示します：$j$ 回のマージのあと、語のトークン列に同じトークンは 2 回現れず、総トークン数は $N - j$ である。

$j = 0$ では記号がすべて異なるので成り立ちます。$j$ で成り立つとし、$N - j \ge 2$ とします。トークンがすべて異なるので、どの隣接ペアも出現回数はちょうど 1 で、手順 3 を通過します。選ばれたペア $(a, b)$ は $a \ne b$ で出現回数 1 なので、<Ref to="lem-merge-step" /> の 2 と 4 より総トークン数は 1 だけ減って $N - j - 1$ になります。新しいトークンは 1 か所にだけ現れ、ほかのトークンは元のままなので、同じトークンが 2 回現れることはありません。

したがって総トークン数が 1 になるまで、ちょうど $N - 1$ 回マージが行われます。$N - K = N - 1$ なので等号が成り立ちます。

</Solution>
</Exercise>

<Exercise id="exr-concatenation" difficulty="標準">

記号列を連結してから符号化すると、別々に符号化して並べたものよりトークン数が**増える**ことがある。$\Sigma = \{\mathrm{a}, \mathrm{b}, \mathrm{c}, \mathrm{d}\}$ 上の 3 つの規則の列で、$|\mathrm{enc}_R(st)| > |\mathrm{enc}_R(s)| + |\mathrm{enc}_R(t)|$ となる $s, t$ の例を作れ。

<Solution>

$r_1 = (\mathrm{b}, \mathrm{c} \mapsto \mathrm{bc})$、$r_2 = (\mathrm{a}, \mathrm{b} \mapsto \mathrm{ab})$、$r_3 = (\mathrm{c}, \mathrm{d} \mapsto \mathrm{cd})$ とし、$s = \mathrm{ab}$、$t = \mathrm{cd}$ とします。

$\mathrm{enc}_R(s)$: a b に $r_1$ は当てはまらず、$r_2$ で (ab)、$r_3$ は当てはまらないので 1 トークン。$\mathrm{enc}_R(t)$: c d に $r_1$、$r_2$ は当てはまらず、$r_3$ で (cd) の 1 トークン。合わせて 2 トークンです。

$\mathrm{enc}_R(st)$: a b c d に $r_1$ を適用すると (a, bc, d)。$r_2$ は b が無いので当てはまらず、$r_3$ も c が無いので当てはまりません。結果は 3 トークンで、$3 > 1 + 1$ です。

境界をまたぐ (b, c) が先にまとめられ、両側の規則の材料が無くなったためです。<Ref to="prop-bpe-greedy-not-optimal" /> と同じ仕組みで、符号化が連結と両立しない（$\mathrm{enc}_R(st) \ne \mathrm{enc}_R(s)\,\mathrm{enc}_R(t)$ となりうる）ことも分かります。復号のほうは常に $\mathrm{dec}(xy) = \mathrm{dec}(x)\,\mathrm{dec}(y)$ です。

</Solution>
</Exercise>

## 参考文献

- [1] P. Gage, "A New Algorithm for Data Compression", *The C Users Journal* 12(2) (1994), 23–38 — バイト対符号化の原典。書誌は [2] の参考文献表による。
- [2] R. Sennrich, B. Haddow, A. Birch, "Neural Machine Translation of Rare Words with Subword Units", ACL 2016. [arXiv:1508.07909](https://arxiv.org/abs/1508.07909) — BPE を単語分割に使った論文。3.2 節に手続きと、語彙の大きさが「初期の語彙＋マージ回数」になることの記述がある。
- [3] A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, I. Sutskever, "Language Models are Unsupervised Multitask Learners", OpenAI, 2019 — 2.2 節（UTF-8 のバイト列に対する BPE）と 2.3 節（語彙の大きさ 50,257）。
- [4] F. Yergeau, "UTF-8, a transformation format of ISO 10646", RFC 3629 (STD 63), 2003. [https://www.rfc-editor.org/rfc/rfc3629](https://www.rfc-editor.org/rfc/rfc3629) — 3 節に符号位置の範囲とバイト列の対応表がある。
- [5] T. Kudo, "Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates", ACL 2018. [arXiv:1804.10959](https://arxiv.org/abs/1804.10959) — ユニグラム言語モデルによる分割。