先日社内の勉強会で圧縮アルゴリズムについてやりました。データ圧縮は身近でよく使われているものですが、中身について知らない方も多いのではないのでしょうか。今回は、連長符号について書こうと思います。今では使われることはほとんどなくなりましたが、圧縮アルゴリズムの基礎とも言えるもので、覚えておいて損はないと思います。圧縮とはデータを圧縮するということは、どういうことでしょうか。データを圧縮するということは、サイズが小さくなることですが、より短い情報量で元のデータを表現できれば良いわけです。元のデータを再現する必要はなく、同じ効果を得られてより短い情報量で表現できれば、圧縮効率は上がります。データ圧縮は、元のデータをより短い情報で表現し必要な情報を得られること、言えることができると思います。データを圧縮するには、必ずしも元のデータが復元できる必要があるとは限りません。元のデータが復元できないと困ることも多くあります。可逆圧縮その名の通り、元のデータが完全に復元できる圧縮を可逆圧縮と言います。我々が普段使っている圧縮は、元のデータが復元できないと困るので、可逆圧縮が使われます。対して、元のデータを完全に復元できないものの、目的を達成することができるデータ圧縮を非可逆圧縮と言います。元のデータが復元できなくても、目的が達成できるので、基本的には特定の環境下でのみの適用となります。画像・音声データの圧縮で使われているアルゴリズムです。これらのデータの高周波成分(高すぎる音、色変化の激しい部分)は、切り捨てたり、ざっくしとした数値に丸めてしまっても知覚にそれほど大きな影響はありません。元のデータはなくなりますが、高周波成分を削ってデータ量を少なくします。したりすると思いますが、これらも非可逆圧縮と言えるでしょう。変数名や関数名が変わったりするので、元のソースコードを復元することはできません。ブラウザで実行する分には、余計なスペースはいりませんし、変数名や関数名は同じである必要はありませんので、使用に全く問題はありません。元のソースコードから比べてもデータは少なくなっているので、圧縮されています。圧縮できるのかなぜデータを圧縮することができるのでしょうか。データの中には、冗長なデータや、法則性のあるデータがあります。これらのデータはその冗長性や法則性を利用して、より短いデータで表現することができます。符号化データ圧縮の話をする前に、まず符号化について考えます。情報に対して割り当てられたコードのことを符号と言います。いうコードが割り当てられています。0x42この割当てられた符号を使って情報に対してコードを割り当てることを符号化と言います。ちなみに符号化の逆は復号です。復号化と間違える人がいるので気をつけましょう。連長符号では、具体的に連長符号について見ていきます。Compression(RLE)とも呼ばれます。長さで符号化する非常に単純なアルゴリズムです。次のようなデータを連長符号で圧縮するのを考えてみましょう。28バイトアルファベットが28文字ありますから、データ量は28バイトです。長さ(1バイト)で符号化すると、次のようになります。14バイトちょっと紛らわしいですが、ここの数字は文字ではなく、数値になってます。連長符号化後のデータ量は14バイトになっていますので、圧縮率は50%になっています。ところが、このアルゴリズムでは必ずしもデータ量が短くなるとは限りません。次のようなデータを圧縮することを考えてみます。7バイトこれを連長符号で圧縮するとこうなります。データ量が逆に増えてしまいました。これでは全然圧縮になっていません。連長符号は連続したデータがないと圧縮できないことから、いわゆるベタ絵の圧縮などに使われます。ベタ絵は同じ色が連続することが多いので、連長符号でうまく圧縮することができるのです。次のようなアルゴリズムで符号化していきます。いう数値を有効活用するためです。範囲で、1-128の繰り返さない文字列数を表現します。表現するのは、繰り返す文字列は必ず2文字以上になるので、1から始まらずに2から始まるためです。範囲で、2-128の繰り返す文字列数を表現します。符号化してみましょう。