バイト対符号化

BPE（Byte Pair Encoding；バイト対符号化）は、データ圧縮法のひとつで、可逆圧縮に分類される。 一般的な圧縮法と比較して圧縮速度が極端に遅いという欠点はあるが、展開速度は爆発的な速さである。また、展開ルーチンが非常に小さく作ることが可能であるという特徴を持つ。このような特徴から、性能の低いコンピュータ用のゲームソフトのデータ圧縮などに用いられることが多い。

符号化の原理

出現頻度が高い2バイトを使われていない1バイトに置き換えていくことを繰り返して圧縮する。

ABCDCDABCDCDE	出現頻度の高い CD のペアを使われていない Z に、次に頻度の高い AB のペアを Y に置き換える
YZZYZZE	出現頻度の高い YZ（ZZ でも構わない）のペアを使われていない X に置き換える
XZXZE	出現頻度の高い XZ のペアを使われていない W に置き換える
WWE	WWのペアはひとつしか出てこないのでここで終わり

実際には、これに符号の対応表を付加してからファイルに出力する。