圧縮

Haskellでそろそろ役に立ちそうなものを作ってみたい
何がいいかな。
と考えたとき、一番先に思いついたのがファイル圧縮。
画像ファイル、BMPを圧縮するようなものを作るのはどうだろう、と考える。
やはり可逆性が大事なので、有名な圧縮技法にはどのようなものがあるか調べてみる。

なんだかんだ、私、圧縮について全然詳しくない。

すると、代表的なものには
ラン・レングス法
ハフマン法
などがあるようです。
説明を読むと、どちらも講義なり自習なりで知っていることでした。
ちょっと安心。

ここに一応まとめておく。

  ラン・レングス法

同一データの並びを調べ、その連続数及びデータ列を記録する

　ハフマン法

出現頻度が高いものから順々に短いデータ列を与え、平均情報量を小さくする

ハフマンの場合は、出現率がとても小さいものの場合は無視してしまうという可能性もある。
これにより情報量は軽くできるが、可逆性は失われる。
単一な色で構成されたビット列の場合はどちらも有用であるが、実際はそんなことめったにないし。

どちらの方法をとるにしても、一度ファイルの内容を一度読み込む必要がありますね。
どうしようか。

調べてみたら、差分法という方法もあるようです。
動画などの処理に使われているよう。
これなら母体となるピクセルの情報を保持してやるだけで、その差分を取ればいいですね。
そのピクセルをうまい具合に決定してやれば、ある程度情報量を削減できそう。

もうすこし検討してみます