圧縮アルゴリズムの話 〜可逆と非可逆をざっくり整理してみる〜
2021.06.25
この記事は最終更新日から1年以上が経過しています。
どもです。
普段なにげなく扱っている画像やテキストのファイル、気がつけば「これってどうやって小さくなってるんだ？」とふと気になることがあるんですよね。zip にしたらサイズが減る、JPEG だと写真がいい感じに軽くなる。当たり前に使っているけど、中身のアルゴリズムって意外とちゃんと説明できなかったりします。
ということで、今回は「圧縮アルゴリズム」について、自分の頭の整理も兼ねてざっくりまとめてみました。大きく分けると 可逆圧縮 と 非可逆圧縮 の2つに分かれます。
可逆圧縮（元に戻せるやつ）
可逆圧縮は、その名のとおり 圧縮したものを完全に元どおりに復元できる タイプの圧縮です。テキストやプログラムみたいに、1ビットでも変わったら困るデータに使われます。zip なんかもこっち側ですね。
代表的なものを2つ見ていきます。
ランレングス圧縮
参考: 連長圧縮 – Wikipedia
いちばんイメージしやすいのがこのランレングス（連長圧縮）です。同じデータが連続している部分を「データ＋繰り返し回数」にまとめる という、すごくシンプルな発想。
たとえばこんなデータがあったとして。
A A A A A B B B B B B B B B A A A
これを「A が5回、B が9回、A が3回」と読み替えて、こう表現します。
A 5 B 9 A 3
元が17文字だったものが6個の情報で済んでしまう。同じ値がずらっと並ぶデータほど効果が出るので、ベタ塗りの多い画像なんかと相性が良いんですよね。逆に、バラバラなデータだとかえって増えることもあるので、そこは使いどころ次第かと思います。
ハフマン符号化
もう一つの定番がハフマン符号化です。こちらは よく出てくるデータには短いビット列を、めったに出てこないデータには長いビット列を割り当てる という考え方。
普段、文字は全部おなじビット数で表現されてますが、出現頻度に応じてビットの長さを変えてあげれば、全体としてデータ量を減らせるよね、という発想です。出現回数を集計して、頻度の低いものから木構造（ハフマン木）を組み上げていくことで、最適な符号の割り当てを決めていきます。
ランレングスが「連続」に注目するのに対して、ハフマンは「頻度」に注目する、という違いで覚えておくと整理しやすいかと思います。
非可逆圧縮（元には戻せないけど軽い）
さて、ここからは非可逆圧縮です。
非可逆はその逆で、元のデータに完全には戻せない代わりに、ぐっと小さくできる タイプ。「多少情報が削れても人間の目や耳には分からないでしょ」というところを狙って、思い切ってデータを捨てます。写真や音声、動画みたいに、ちょっとくらい劣化しても実用上問題ないデータで大活躍します。
フーリエ変換（JPEG）
JPEG の圧縮で出てくるのがフーリエ変換まわりの考え方です。ざっくり言うと、画像を「波（周波数成分）の集まり」として捉え直す ことがキモになります。
画像を周波数の世界に変換してやると、「細かく変化している高周波の成分」と「ゆるやかに変化している低周波の成分」に分けられます。人間の目は細かい変化（高周波）には意外と鈍感なので、その部分の情報を削ってしまっても、見た目はそんなに変わらない。ここを削ることでサイズを大きく落とせる、というわけですね。JPEG の画質設定をぐっと下げるとモヤッとしたノイズが出てくるのは、まさにこの高周波成分を捨てているからなんだなと。
PNG quant / メディアンカット
参考: 減色アルゴリズム（メディアンカット法） – PETITMONTE
最後に PNG の減色まわり。pngquant みたいなツールで使われているのが メディアンカット法 というアルゴリズムです。
これは 画像で使われている色の数を、いい感じに減らす（減色する） ための手法。フルカラーだと膨大な色数になりますが、それを代表的な色だけに絞り込んでパレット化することで、ファイルサイズを小さくします。色空間の中で色を箱に詰めて、その箱を「中央値（メディアン）」のところでカットして分割していく……というのを繰り返して、最終的に必要な色数まで絞り込んでいくイメージですね。
PNG 自体はフォーマットとしては可逆なんですが、こうやって事前に減色してから保存することで、見た目をなるべく保ちつつ容量を落とせる、という合わせ技になっています。
まとめ
ということで、圧縮アルゴリズムをざっくり整理してみました。
- 可逆圧縮 … 完全に元へ戻せる。ランレングス（連続に注目）、ハフマン符号化（頻度に注目）など
- 非可逆圧縮 … 戻せない代わりに小さくできる。フーリエ変換を使った JPEG、メディアンカットによる減色など
普段ツール任せにしている圧縮も、中身の理屈を知っておくと「このデータならこっちの形式が向いてるな」みたいな判断がちょっとだけ早くなる気がします。自分も書きながら頭の中が整理できて、なかなかに胸アツでした。
ではではぁ。またまたぁ。
