第1章 概要
Byte Pair Encoding（BPE）とは
「月刊 C MAGAZINE」1997年11月号(ソフトバンク刊)にて紹介された、1990年代当時は非常に高速な展開処理が可能であったデータ圧縮アルゴリズムです。
原理としては、隣同士のデータの組み合わせ(2バイト)を1バイトに圧縮して「辞書」を作成、既に使われた組み合わせのデータを「辞書」で符号化、新たに見つけた組み合わせを「辞書」に加えて…の繰り返しとなります。
圧縮されたデータは必ず辞書のバッファが含まれています。バッファサイズは可変であり、組み合わせが少ない単純なデータは辞書のバッファを減らすことで実ファイルのサイズを減らすことができます。逆に組み合わせが多い複雑なデータは辞書のバッファを増やすことで多くの組み合わせに対応させ、実ファイルのサイズを減らすことができます。
辞書のバッファサイズはユーザーが調節できます。データ毎に最適なバッファサイズを見つけて、圧縮ファイルのサイズを最小限に抑えましょう。
Byte Pair Encodingの理論については以下の文献をご参照ください。
Byte Pair Encoding（BPE）の特徴
BPEは展開スピードを重要視したアルゴリズムであり、1990年代当時は他のアルゴリズムでは到底真似できない非常に高速な展開速度を叩き出していました。展開後32KBになるデータをわずか0.5秒(turboR, R800-DRAMモード時)で展開すると言えば、その高速ぶりが理解できるものと思われます。
BPEは展開スピードの速さに加え、90年代当時に利用されていた他の圧縮アルゴリズムと決してひけを取らない圧縮率を誇っていました。さすがにLZ法を超える圧縮率は出せませんが、あと少しでLZ法と肩を並べる程度の圧縮率が期待できます。
BPEはデータが100％復元する「可逆圧縮」のアルゴリズムですので、あらゆるデータに有効利用できます。当クラブが想定している用途は主に画像圧縮ですが、ビットマップデータの圧縮では特にSCREEN8以上のCGの圧縮率が良くなり、MAG形式のようにタイルパターンに頼らずとも圧縮率が期待できます。
当クラブ独自の実装として、DMシステム2では以下の機能があります。
- 圧縮データを配置するメモリはRAM・VRAMのどちらでも有効、展開先のメモリについてもRAM・VRAMのどちらでも任意のアドレスへ展開できます。BGMデータやマシン語等のバイナリデータ、テキスト等なんでも指定されたメモリへ高速にデータ展開できます。
- COPY形式の矩形CGデータは矩形のまま圧縮し、DMシステム2上での展開時にロジカルオペレーションと展開方向を指定できます。下から上方向へ重ね合わせ(TPSET)で展開する等、夢が膨らみます(笑)。
第2章 DMシステム2での使用方法
BPE圧縮データを作る
アプリは4種類あります。ハードウェア環境に併せてご利用ください。アプリは ダウンロードのページ で入手してください。
- MSX-DOS(CP/M)版 EBPE.COM（version 0.30）
- MSX-DOS版 EBPEMSX.COM（version 0.95, 佐野友則さん制作)
- MS-DOS汎用版 EBPE.EXE（version 0.43）
- Win32版 EBPE32.EXE（version 0.43）
各種コマンドラインから以下のパラメータを指定し、コマンドを実行してください。
- A>EBPE [.<出力ファイルの拡張子>] [-|/<options>] <圧縮ファイル>
- C>EBPE32 [.<出力ファイルの拡張子>] [-|/<options>] <圧縮ファイル>
出力ファイルの拡張子を省略した場合の拡張子は .BPE になります。
EBPE.EXEは、Windows 95/98の「MS-DOSプロンプト」からでも実行できます。
EBPE32.EXEは、Win32環境(32bit/64bit版 Windows)の「コマンド プロンプト」上で実行します。
Windows 10以降の「コマンド プロンプト」でEBPE32.EXEを実行すると、一部の環境ではセキュリティソフトによってBPEデータの出力後に即削除される現象が発生する ようです。後述のバッチファイルでは削除される現象が発生しない ようです。
コマンドオプション
コマンドオプション 一覧表
| -h |
ヘルプメッセージを表示します |
| -b# |
辞書のバッファサイズを変更します（# ← 256～32768） |
| -i# |
DMシステム2のデータ形式を直接指定します（# ← 16進数で） |
| -m |
出力ファイルにMSXのBSAVEヘッダを付けません |
| -m- |
出力ファイルにMSXのBSAVEヘッダを付けます（デフォルト設定） |
| -a |
辞書のバッファサイズを自動調整します |
| -a- |
辞書のバッファサイズ自動調整を行いません（デフォルト設定） |
| -v |
圧縮時の状況を詳細表示します |
※出力ファイルの拡張子を省略した場合の拡張子は .BPE になります。
バッファサイズの指定オプション(-b#)
辞書のバッファサイズを任意指定します。(256～32768) 省略するとデフォルト設定の 4096（バイト）になります。
※MSX-DOS版 EBPE.COMの最大バッファサイズは 8192 です。
※MSX-DOS版 EBPEMSX.COMの最大バッファサイズは 12288 です。
自動調整オプション(-a)
辞書のバッファサイズを自動で調整します。
A>EBPE -a -b32768 hogehoge.dat
のように -aオプションを指定すると、辞書のバッファサイズを 512,1024,2048,4096,8192,16384,32768 と変更しつつ圧縮した結果一番圧縮率の高いものを選択します。
※MSX-DOS版 EBPE.COM・EBPEMSX.COM では -aオプションが利用できません。
Windows向け：辞書バッファサイズの総当たりバッチファイル
バッチファイルの概要
バッチファイルを起動してデータを作成する動画
昨今のWindows PCは非常にメモリが豊富で高速に動作しますので、1990年代当時は実行したくなかった「辞書バッファサイズを手動でちまちま変えて圧縮作業を繰り返しファイルサイズが一番小さなものを採用する」という行為が非常に手軽になりました。
以下のテキストデータを各種テキストエディタへコピーし、バッチファイル（拡張子 .BAT）としてファイル保存してください。
ebpe32 .256 -b256 %1
ebpe32 .512 -b512 %1
ebpe32 .1K -b1024 %1
ebpe32 .2K -b2048 %1
ebpe32 .3K -b3072 %1
ebpe32 .4K -b4096 %1
ebpe32 .5K -b5120 %1
ebpe32 .6K -b6144 %1
ebpe32 .7K -b7168 %1
ebpe32 .8K -b8192 %1
ebpe32 .9K -b9216 %1
ebpe32 .10K -b10240 %1
ebpe32 .11K -b11264 %1
ebpe32 .12K -b12288 %1
ebpe32 .13K -b13312 %1
ebpe32 .14K -b14336 %1
ebpe32 .15K -b15360 %1
ebpe32 .16K -b16384 %1
ebpe32 .AUT -a %1
上記バッチファイルを仮に EBPEBAT.BAT と命名し、EBPE32.EXEと圧縮対象ファイルとバッチファイルを同じフォルダへ配置したうえで、コマンド プロンプトよりバッチファイルを実行してください。
C>EBPEBAT ＜圧縮対象ファイル＞
バッチ処理では、バッファサイズ256バイトから16KバイトまでBPE圧縮を繰り返し実行します。1分ほど待つとファイル名は同じで拡張子が異なる複数の圧縮データが作成されてバッチ処理が終了しますので、ファイルサイズの一番小さなものを採用する(それ以外は捨てる)ことで、最大級の圧縮効率が得られます。自動調整オプションを設定するよりもサイズが小さくなる場合もありますので、ぜひお試しください。
C>dir ＜ファイル名(8文字)＞.* /OS
なお、採用した圧縮データファイルは、拡張子を「.BPE」へリネームしておくことをおすすめします。
第3章 使用上の注意
データの圧縮について
Byte Pair Encodingの圧縮技法は、データ圧縮処理に大変時間がかかります。特にMSX2/2+ではあまりにも遅くて暴走しているように見える場合があります。佐野友則さん制作の EBPEMSX.COM は当クラブのものより高速化されていますので、MSX実機では佐野さんのアプリをおすすめします。
BPE圧縮アプリ毎に圧縮結果(ファイルサイズ)が異なることがありますが、展開されるデータに支障はありません。
1997年6月にBPE圧縮の仕様を若干変更しました。旧仕様ではアルゴリズム上のミスで正常に展開できないデータを作る場合があり、新仕様を搭載したDMシステム2(97/06/01以降)では旧仕様のBPEデータが正常に展開できません。旧仕様のBPEデータを新仕様のシステムで利用するには、佐野友則さんのBPE補正ツール「FIXBPE」でこの問題が回避できます。
データの展開について
UNIX版「fMSX」のソースから派生した一部のMSXエミュレータではVDPエミュレーションに致命的なバグがある為、BPE展開機能をご利用できない場合があります。
第4章 圧縮時のデータ形式の分類
DMシステム2のBPE圧縮は「バイナリシステム」と組み合わせることにより、データの自動展開と即利用が指定できます。
圧縮時にデータ形式が認識されるものは以下の通りです。
データ形式の分類一覧表
| No. |
データ形式の内容 |
拡張子(デフォルト) |
| 0 |
その他（RAMへ転送するベタデータ） |
| 1 |
BGMデータ |
.MGS .BGM |
| 2 |
SEDRVに対応したSEテーブル |
.SE |
| 3 |
RAMへ転送するバイナリーデータ |
.OBJ .BIN |
| 4 |
DM-PALETに対応したパレットテーブル |
.PLn .BPn |
| 8 |
VRAMへ転送するベタデータ |
.SCn .SRn |
| 9 |
COPY形式のCGデータ |
.PIn .GLn |
| 10 |
PCMデータ |
.PCM .PCP |
※データ形式は圧縮ツールのオプション指定で変更も可能です。
![[Back]](ds2h.gif){kind=small}
トップページへ