圧縮アルゴリズム(連長符号) - UUUMエンジニアブログ

おはこんばんちは尾藤 a.k.a. BTO です。

先日社内の勉強会で圧縮アルゴリズムについてやりました。データ圧縮は身近でよく使われているものですが、中身について知らない方も多いのではないのでしょうか。

今回は、連長符号について書こうと思います。今では使われることはほとんどなくなりましたが、圧縮アルゴリズムの基礎とも言えるもので、覚えておいて損はないと思います。

圧縮とは

データを圧縮するということは、どういうことでしょうか。データを圧縮するということは、サイズが小さくなることですが、より短い情報量で元のデータを表現できれば良いわけです。また必ずしも元のデータを再現する必要はなく、同じ効果を得られてより短い情報量で表現できれば、圧縮効率は上がります。つまりデータ圧縮は、元のデータをより短い情報で表現し必要な情報を得られること、言えることができると思います。

データを圧縮するには、必ずしも元のデータが復元できる必要があるとは限りません。しかし、元のデータが復元できないと困ることも多くあります。ですので、この2つは明確に区別してやる必要があり、それぞれ 可逆圧縮 と 非可逆圧縮 と呼ばれます。

可逆圧縮

その名の通り、元のデータが完全に復元できる圧縮を可逆圧縮と言います。我々が普段使っている圧縮は、元のデータが復元できないと困るので、可逆圧縮が使われます。

非可逆圧縮

対して、元のデータを完全に復元できないものの、目的を達成することができるデータ圧縮を非可逆圧縮と言います。元のデータが復元できなくても、目的が達成できるので、基本的には特定の環境下でのみの適用となります。

一番身近な例だと、jpeg や mpeg などの画像・音声データの圧縮で使われているアルゴリズムです。これらのデータの高周波成分(高すぎる音、色変化の激しい部分)は、切り捨てたり、ざっくしとした数値に丸めてしまっても知覚にそれほど大きな影響はありません。なので、元のデータはなくなりますが、高周波成分を削ってデータ量を少なくします。

Webエンジニアだと、CSS や Javascript を minify したり、obfuscate したりすると思いますが、これらも非可逆圧縮と言えるでしょう。 minification では、元のスペースがどうなってたかは復元することはできませんし、obfuscation では、変数名や関数名が変わったりするので、元のソースコードを復元することはできません。ですが、ブラウザで実行する分には、余計なスペースはいりませんし、変数名や関数名は同じである必要はありませんので、使用に全く問題はありません。かつ、元のソースコードから比べてもデータは少なくなっているので、圧縮されています。

なぜ圧縮できるのか

なぜデータを圧縮することができるのでしょうか。データの中には、冗長なデータや、法則性のあるデータがあります。これらのデータはその冗長性や法則性を利用して、より短いデータで表現することができます。

符号化

データ圧縮の話をする前に、まず符号化について考えます。

情報に対して割り当てられたコードのことを符号と言います。例えば、ASCII Code では A に 0x41、B に 0x42 というコードが割り当てられています。

A -> 0x41
B -> 0x42

この割当てられた符号を使って情報に対してコードを割り当てることを符号化と言います。ちなみに符号化の逆は復号です。よく復号化と間違える人がいるので気をつけましょう。

連長符号

では、具体的に連長符号について見ていきます。連長符号、Run Length Compression(RLE)とも呼ばれます。 記号 + 長さで符号化する非常に単純なアルゴリズムです。

次のようなデータを連長符号で圧縮するのを考えてみましょう。

abbcccddddeeeeeffffffggggggg -> 28バイト

アルファベットが28文字ありますから、データ量は28バイトです。これを記号 + 長さ(1バイト)で符号化すると、次のようになります。

a1b2c3d4e5f6g7 -> 14バイト

ちょっと紛らわしいですが、ここの数字は文字ではなく、数値になってます。連長符号化後のデータ量は14バイトになっていますので、圧縮率は50%になっています。

ところが、このアルゴリズムでは必ずしもデータ量が短くなるとは限りません。例えば次のようなデータを圧縮することを考えてみます。

abcdefg -> 7バイト

これを連長符号で圧縮するとこうなります。

a1b1c1d1e1f1g1 -> 14バイト

圧縮率は200%!! データ量が逆に増えてしまいました。これでは全然圧縮になっていません。

連長符号は連続したデータがないと圧縮できないことから、いわゆるベタ絵の圧縮などに使われます。ベタ絵は同じ色が連続することが多いので、連長符号でうまく圧縮することができるのです。

PackBits

連長符号は今では使われることはほとんどないのですが、昔 PackBits という連長符号が Mac で使われていました。 Packbits では次のようなアルゴリズムで符号化していきます。

8ビット単位で符号化する
繰り返さない文字列
- (記号数-1) + 記号列で符号化する
繰り返す文字列
- -(記号数-1) + 記号で符号化する

繰り返さない文字列数を (記号数-1) で表現するのは、0 という数値を有効活用するためです。つまり 0-127 の範囲で、1-128の繰り返さない文字列数を表現します。

繰り返す文字列数を -(記号数-1) で表現するのは、繰り返す文字列は必ず2文字以上になるので、1から始まらずに2から始まるためです。つまり 1-127 の範囲で、2-128の繰り返す文字列数を表現します。

では、次のようなデータを PackBits で符号化してみましょう。

aaaaabcccde -> 11バイト

最初に a が5つ連続していますので、(-4)a を出力します。次に不連続な b に対して、0b を出力します。次は c が3つ連続するので、(-2)c を出力します。最後に不連続は de に対して、1de を出力します。

符号化の結果は次のようになります。

(-4)a0b(-2)c1de -> 9バイト

圧縮率は 82% になりました。 PackBits は最初に紹介した連長符号のアルゴリズムと比べて、不連続なデータの表現が効率よくできるようになっているので、連続したデータがそんなに多くなくてもデータ量があまり増えないように工夫されています。しかしながら、連続データがないとデータ量が増えることには変わりありませんので、適用できるデータは限定的です。実際 PackBits は画像データの圧縮という限定的な用途にのみ使用されています。