ロスなし圧縮アルゴリズム

【はじめに】
アルゴリズムとは、数学やコンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言います。現在ではほとんどが便利になってしまい、業務で意識することはほとんどありません。ですが、

【圧縮アルゴリズム】
そもそも圧縮とはなんでしょうか？これは名前の通り圧力をかけて縮めることを言います。日常的にも服を押し込みカバンに入れたり、冬用布団の空気を抜いて小さくしたりと様々な場面で活用されています。

この圧縮技術はデータでも同じように行われています。インターネット越しに行われる通信のほとんどはあなたが知らないうちにに圧縮技術が使われています。メールでファイルを送る際や、電話ですら圧縮されてから送られます。そのおかげでそのまま送る場合の数分の一の時間でやり取りすることができています。

この当たり前になりすぎて意識していない技術は頭の良い人が考えた圧縮アルゴリズムによって成り立っています。よくフリーランチはない(代償なしに得られるものはないと言う意味)と言われますが今回見ていくロスなし圧縮はデメリットがありません。

恐ろしいですね。では見ていきましょう。

【ロスなし圧縮〜RLE】
早速ですが、これを短くするにはどうすればいいでしょうか？
「aaaaabbbbccc」

すぐに思いつく方もいるのではないでしょうか？もし思いつかなければこれを電話で伝える場合どうするかを考えてみてください。

「aaaaabb....」とは伝えないと思います。
実際は「aが5つ、bが4つ、cが3つ」と伝えると思います。反復しているものはまとめてしまいその個数分を伝えれば短くできますね。

これの書きかたを少し変えてみると比較しやすくなります。「a5b4c3」です。最初の文が12個、変換したものが6個です。半分にまで減らせましたね。

単純な話これがRLEです。ランレングス圧縮と呼ばれるものです。日本語では連長圧縮です。連なった長さのものを圧縮する、名前通りですね。

拍子抜けするほど単純ですが、アルゴリズムのハードルは下がったのではないでしょうか？

まあ、連続した文字列は使える場面はかなり限定的で圧縮できるものも限られています。

【ロスなし圧縮】
assyukuassyukuassyuku
これを短くするにはどうすればいいでしょうか？

もし、RLEでするならa1s2y1....明らかに増えていきますね。これを短くする第一歩としてassyukuと繰り返されていることがわかると思います。

なら簡単ですねassyuku×3でいいんですから。ただ、コンピュータは厳密です。なのでもっと細かく指示を出さないとやってくれません。

assyuku7b2cとしてあげましょう。意味は7個backして2回copyするという意味です。

場所や回数を明確にする必要があります。元の文が21文字に対して11文字です。約50%減りました。これは大きいですね。

【ハフマン符号】
文字にはコンピュータで扱いやすいように2進数が識別子として割り振られています。例えばA=1、B=10、C=11...のように割り振られています。

これが圧縮に関わってくるのですが2進数だとややこしいので10進数で見ていきましょう。

a=01、b=02...y=25、z=26とします。これだけの文字しかないものとしましょう。特徴としては全てが2桁になっていることです。もしこれがa=1、b=2となっていればどうでしょうか？

1123は「aabc」とも「kbc」など色々な受け取り方が出来てしまい、コンピュータは読み取れなくなってしまう。

だがハフマン符号ではこれを行う。頻度によって文字数を減らすのである。例えば英語だとeとtが最も頻度が高い。

これらをe=1、t=2としてしまう。残りはa=03、b=04、c=05、d=06...と続いていく。ただ先ほども示した通りこのままではコンピュータは読み取れない。

なので逆に頻度の少ないものを3桁にしてしまう。例えばy=725、z=726としてしまう。これだとあまり文章が短くなったように感じないかも知れないが実際はa=010000010などの長い桁に対して頻度が多い順に1文字2文字...と続いていく。

そう考えるとどうだろうか？かなり圧縮されそうではないだろうか。実際かなり圧縮される。しかも文字数が増えれば増えるほど圧縮率も上がる。