RLE、レンジコーダ、ブロックソート ( BWT )、MTF などの圧縮関連技術

近頃圧縮技術に触れる機会があったのだが、
やー、圧縮は奥が深くて面白い！
探索、ハッシュ、整列 ( ソート ) ・・・いろんなアルゴリズムの勉強にもなる。

こういった圧縮周辺の技術は、以下のサイトで学ぶことができる。
詳しい解説と Python コードつきなので非常に分かりやすい。

ものすごくざっくりと学んだことをまとめてみる。

  • 記号に偏りがある場合は算術符号、ハフマン符号が効果的
    • BWT と組み合わせるとさらに効果が大きくなる
    • 算術符号は特許の嵐なので要注意
  • 記号に偏りがない場合は辞書式圧縮などが効果的
    • 場合によっては RLE も大きな効果を発揮する
      • BWT と組み合わせるとさらに効果が大きくなる
  • ソートの使い分け
    • 小さい集合のソートには挿入ソートが向いている
    • バケツソートは整列対象がバイト程度であれば最強である
      • ただしメモリは喰う
    • それ以外の用途はクイックソートが割とうまいことやってくれる

特に、BWT はパズルみたいで面白いので気に入った。
コストはかかるが、RLE にも算術符号にも効果があるのも大きな魅力だ。

実際に試すとき、私は C で実装した。
で、BWT を実装していたとき、標準関数である qsort では事足りなかった。
配列そのものをソートしたいのではなく、
配列に格納されたインデクスの先のデータでソートしてインデクスを並べ替えたかったからだ。
（バケツソートも試してみたかったがこういう用途への変形がよく分からなかったので断念した）

で、挿入ソートとクイックソートを適当に書いて性能を比べていた。
挿入ソートもクイックソートも、自分で書くのは Delphi でゲームを作ってたとき以来なの 10 年ぶりくらいだ。
その途中、比較関数を書いているときに、あれ？これって memcmp() で書けるな、と思って書き直した。

しかし、挿入ソートの性能は上がり、クイックソートの性能は下がった。
コードを見返してみても、理由がよく分からない。うーん、不思議。


とにかくこれらから学んだのは、
複雑そうに感じていた圧縮技術も割と簡単なアルゴリズムの組み合わせにすぎないということだ。

割と簡単、ということが分かったのはとても大事なこと。
割と簡単なら、よしやってみよう、という気になれるからだ。