BPE の符号化は最短分割とは限らない

あるコーパスから 定義 2.3 の学習で得たマージ規則の列 $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})$ 回行えば求まる。