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^{*}$ を

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