第1章 概要
Byte Pair Encoding(BPE)とは
「月刊 C MAGAZINE」1997年11月号(ソフトバンク刊)にて紹介された、90年代当時は非常に高速な展開処理が可能であったデータ圧縮アルゴリズムです。
原理としては、隣同士のデータの組み合わせ(2バイト)を1バイトに圧縮して「辞書」を作成、既に使われた組み合わせのデータを「辞書」で符号化、新たに見つけた組み合わせを「辞書」に加えて…の繰り返しとなります。
圧縮されたデータは必ず辞書のバッファが含まれています。バッファサイズは可変であり、組み合わせが少ない単純なデータは辞書のバッファを減らすことで実ファイルのサイズを減らすことができます。逆に組み合わせが多い複雑なデータは辞書のバッファを増やすことで多くの組み合わせに対応させ、実ファイルのサイズを減らすことができます。
辞書のバッファサイズはユーザーが調節できます。データ毎に最適なバッファサイズを見つけて、圧縮ファイルのサイズを最小限に抑えましょう。
BPEの特徴
BPEは展開スピードを重要視したアルゴリズムであり、90年代当時は他のアルゴリズムでは到底真似できない非常に高速な展開速度を叩き出していました。展開後32KBになるデータをわずか0.5秒(turboR, R800-DRAMモード時)で展開すると言えば、その高速ぶりが理解できるものと思われます。
BPEは展開スピードの速さに加え、90年代当時に利用されていた他の圧縮アルゴリズムと決してひけを取らない圧縮率を誇っていました。さすがにLZ法を超える圧縮率は出せませんが、あと少しでLZ法と肩を並べる程度の圧縮率が期待できます。
BPEはデータが100%復元する「可逆圧縮」のアルゴリズムですので、あらゆるデータに有効利用できます。当クラブが想定している用途は主に画像圧縮ですが、ビットマップデータの圧縮では特にSCREEN8以上のCGの圧縮率が良くなり、MAG形式のようにタイルパターンに頼らずとも圧縮率が期待できます。
当クラブ独自の実装として、DMシステム2では「VRAMの任意のアドレスへの展開機能」の他に「RAMへの展開機能」もございますので、BGMデータやマシン語等のバイナリデータ、テキスト等なんでも指定されたメモリへ高速にデータ展開できます。また、COPY形式の矩形CGデータは矩形のまま圧縮し、DMシステム2上での展開時にロジカルオペレーションと展開方向を指定できます。下から上方向へ重ね合わせ(TPSET)で展開する等、夢が膨らみます(笑)。
Byte Pair Encodingの理論については以下の文献をご参照ください。
- 原文: C/C++ Users Journal Vol.15, No.9 Philip Gage → http://www.pennelynn.com/Documents/CUJ/HTML/94HTML/19940045.HTM
- 日本語: C MAGAZINE 1997年11月号 太田純 訳「ランダムアクセスが可能なデータ圧縮技法」 → https://www.amazon.co.jp/dp/B00KLPFSGA
- Wikipedia - バイト対符号化 → https://ja.wikipedia.org/wiki/%E3%83%90%E3%82%A4%E3%83%88%E5%AF%BE%E7%AC%A6%E5%8F%B7%E5%8C%96
2021年現在、Z80で実行可能かつBPE以上に高性能な圧縮アルゴリズムが存在します。こちらのプロダクトとDMシステム2を組み合わせていただくのも有用かと思います。
- Exomizer(圧縮率に有利) → https://bitbucket.org/magli143/exomizer/wiki/Home
- LZEe(展開速度に有利) → https://github.com/uniabis/lzee
- BARGAIN(MSXに特化) → https://www.vector.co.jp/soft/dl/other/msx/se179373.html