|
|
ある日のこと，ぼーっとした頭で仕事をしていると，同僚がそれはもう満面の笑みを浮かべて「プログラムで使っている画像データを圧縮するためにLZSS＊1を実装してみたんですよ。ふふん，どうよ」と話しかけてきました。「ぬあ?」とそれがどうした的に返事をしつつも，ふと気づいたのは，何らかの圧縮プログラムやアルゴリズムを作った経験を持つプログラマは意外に多いということです。すでにzlibなどの著名な圧縮ライブラリが公開されていますが，「ブロックソート」や「PPM」などの新しい圧縮方法が日夜開発されています。
どうも圧縮というのは，プログラマ心をそそる何かがあるようです。今回はそんな圧縮アルゴリズムの不思議で魅力的なところを紹介します。パズルのような圧縮アルゴリズムの楽しさを感じていただければと思います。
ルールに従って元のデータを
短いデータに置き換える
「ジュゲムジュゲム…」と長い名前の代名詞であるジュゲムを人に何回も伝えることを想像してみてください。とんでもなく面倒そうですね。ですが，ジュゲムを“あ”という1文字で表すと決めたらどうでしょう。伝える相手には，「“あ”というのは“ジュゲム…”のことだよ」とあらかじめ1回だけ教えておきます。そうすれば，以後「“あ”ですよ“あ”」と言うだけで，相手は「ジュゲム…ですよジュゲム…」と言っていることがわかります。「ジュゲム…」という長い文字列を“あ”という1文字に置き換えることで，文章全体を短くできたわけです。
圧縮の基本となる考え方は，このように「長いデータを短いデータに置き換える」ことです。つまり，データの中を調べ，何度も出てくるデータをもっと短いデータに置き換えて，全体のサイズを小さくする方法が圧縮アルゴリズムです。以下では圧縮アルゴリズムの例を三つ見てみることにしましょう。
連続した文字を「文字×個数」に置き換える
ランレングス法
図1を眺めてみると“@”や“-”などの文字が横に連続して何度も出てきます。何となくもったいないように感じます。ここへ「同じ文字が連続して出ていたらそれを『文字×連続した個数』に置き換える」というルールを適用してみます。
いちばん下のラインを取り出して試してみましょう。行頭からスペースの文字が16個連続しています。これを[ ×16]に置き換えます。その先にある“=”も9個あるので[=×9]と置き換えて…とこれを行末まで繰り返します。すると，
[ ×16]`#@*[=×9]@[ ×4]`@[ ×4]`@[ ×7]-8[ ×12]
という文字列になりました。見た目でもだいぶ短くなった感じがします。元に戻すときは，[ ×16]というのがあったら，スペースを16個ぶん置くようにします。これを全部の文字について実行すれば，乾燥麺がお湯を吸って膨らむがごとく元の文字列に戻ります。
これは，ランレングス法と呼ばれる最も基本的な圧縮方法です。実際にプログラムとして実装する場合には，[ ×16]などの部分をデータとしてどう表すかを決めなくてはなりません。簡単なのは，圧縮データの目印となる値（例えば0xff＊2）を決め，その後ろに「連続する文字」と「個数」並べる方法です。圧縮対象となるデータがASCII文字だけを含むなら，ASCIIが使わない最上位ビットをフラグとして利用する手もあります。
何度も出現する文字列を
1カ所への参照に置き換えるLZ77
先のランレングス法では文字単位でデータを見ました。今度は見方を少し変えて，データの「固まり」で考えてみましょう。図1のデータを見ると“@---”といった文字列が何度か現れていることがわかります。このようなデータは，「ある文字列が以前に出ていたら，その部分に対する参照で置き換える」ことで圧縮することができます。これはLZ77＊3と呼ばれる圧縮アルゴリズムです。
この方法は，圧縮よりもまず，展開する場合を先に考えてみるとわかりやすいでしょう。すでに現れた文字列を参照する場合には，目印となるマークに続いて，参照する文字列の相対的な位置と文字列長を書き込むことにします。今仮に，展開先バッファに「 @=**-」と出力した段階で，「相対位置＝8，文字列長＝2」という参照情報に出会ったとします。この場合は，現在位置から8文字ぶん前の位置から2文字だけコピーして展開先バッファに出力します。この例では「 @=**- 」となってスペースが二つ増えることになります。
圧縮する際には，これから圧縮する文字列が，どの位置から何文字ぶん一致しているかを調べなくてはなりません。何度も文字列を比較するため，単に先頭から順に調べていくやり方だと処理が非常に遅くなってしまいます。そこで，比較を始める位置とその最初の1文字をまとめて管理したり，それらをツリー構造で管理してそこから探索したりするといった工夫をするのが一般的です。
