BPEに挑戦してみた

地球にやさしいアルゴリズム - 第2回 パズルみたいに楽しいデータ圧縮：ITproを見てまたもや作成してみた。
記事内では幾つかの圧縮アルゴリズムが紹介されているが、メインはBPE(Byte Pair Encoding)というアルゴリズムだ。
これは名前通り2バイトをペアと考えるのを基本とする。
そのペア(2Byte)の中で最も数が多いものをそのデータ内で使用していない値(1Byte)で置き換える、というもの。

(例)
ABBBBCCBBCC
↓"BB"のペアが最頻出なのでZ(使っていない値)に置き換え
AZZCCZCC
↓"CC"のペアが最頻出なのでY(使っていない値)に置き換え
AZZYZY
↓"ZY"のペアが最頻出なのでX(使っていない値)に置き換え
AZXX
※どのペアも出現回数が少ないので終了
※変換テーブルは"Z→BB", "Y→CC", "X→ZY"の3つ

<<圧縮>>
1.圧縮元データ内で使われていないデータを調べ上げ、置き換え候補とする
2.現在のデータから最頻出のペアを調べる
　2'.最頻出回数が少なければもう置き換えずに終了する
3.最頻出ペアを「置き換え候補」に置き換える
　3'.置き換え候補が無いなら終了する
4.変換テーブルと変換後データを出力する<<展開>>
1.変換テーブルを読み込む
2.1つずつ変換テーブルのデータを使って圧縮済みデータを置き換える


BPEはこの記事で初めて知ったが、なかなか面白くて理解しやすいアルゴリズムだ。
圧縮には時間が掛かるが展開が速くメモリも少なくて済むので組み込み系などで使うらしい。
実装も短く済んだし(プログラムの効率はともかく)、良いかも。