新しいマシンをセットアップして、ネットに繋いだら、最初に必要になるものなーんだ、と聞かれたらやはり「圧縮展開ツール」となるだろう。今時のWindowsは大体自前でやってくれるが、昔はそうではなかった。とにかく、パソコン通信でもインターネットでもそうだが、何かのアプリケーションやデータをダウンロードしてくると、たいていは圧縮が掛けられている。従ってこれを解除しなきゃいけない。時にはその展開ツール自体が圧縮されていて「どうすりゃいいんだ…」と途方に暮れる事もあったが、ほとんどの場合圧縮展開ツールは自己解凍形式というもので圧縮されていて、これはつまり展開ツールを内包した圧縮データで、実行するだけで自分自身を展開してくれる。後はそれを使えば良い。
　なぜ、ダウンロードされるファイルが何でもかんでも圧縮されているかと言うと、サイズが小さくなった方がダウンロード時間も短くなるし、サーバ上のスペースも少なくて済むからだ。それから、セットになっている複数のファイルが一つにまとまっていた方がいいというアーカイバとしての働きもある。
　そういう事で、ネットワーク文明社会で生きるには、データの圧縮及び展開と言う概念とうまくつきあっていかなければいけない。

　情報の圧縮、展開は情報科学の重要なテーマである。それこそ、コンピュータが開発された黎明期から、研究課題として挙げられている。
　データの圧縮については、大きく分けて可逆圧縮と、非可逆圧縮がある。可逆というのは、展開した後完全に元のデータに戻るという事だ。非可逆は、元に戻らない。つまり、圧縮時にある程度元の情報を捨ててしまい、圧縮しやすいデータに変換してしまう。その性質上、バイナリデータやテキストデータは可逆圧縮じゃないと困る。1ビットでも変更されたら困るしね。
　非可逆圧縮は、画像や音声に良く使われる。これらは、1ビットくらい情報が欠けても大した問題ではない事が多いので、その代わりに圧縮率を大幅に引き上げるのである。

　データ圧縮の原理は、「冗長性」と呼ばれるものがデータにある、という事を前提にしている。例えば、データの出現頻度に差があり、あまり出てこないデータがあるだとか、同じデータが連続する部分があるとか、似たようなデータが何度も出現するとか、意味を持つデータなら大抵は持っている偏りを利用するのである。
　従って、全く偏りを持たない、完全にランダムな情報で構成されたデータは、可逆圧縮ではほとんどサイズが小さくならないばかりか、かえって大きくなるケースが多い。理屈としては、「その圧縮方式ではかえって大きくなる」というデータが存在するからこそ、小さくなるデータも出てくるわけで、こればかりは仕方がない。
　よって、どのようにして冗長性を発見し、どのようにデータ化するかが、圧縮アルゴリズムの要点である。そしてまた、コンピュータで行う以上、圧縮及び展開の処理にかかる時間が短い方が良い。その兼ね合いである。

　可逆圧縮アルゴリズムの花形は、なんと言ってもLZ法である。イスラエルのLempelさんとZivさんが1977年に論文で発表した方式で、その頭文字をとってLZ法と呼ぶ。
　内容は簡単である。例えば、ある文章に何度も「Algorithm」という言葉が出てきたとしよう。最初に出てきた時は、そのままの形でデータ化するが、2回目に出てきた時は、「152文字前の位置から9文字分」という意味の情報に変換する。以後、Algorithmという文字が出てくるたびに、「○○文字前の位置から9文字分」という形にする。こうすると、何文字前からか、何文字分なのかという2つの数値で文字列を表せる。「次の情報は置き換え文字ですよ〜」という符号を挟んだとしても、3つ分で済む。長い文字列が繰り返される文章では、かなりの圧縮効率を発揮する。
　これは、文章などのデータでは、一定のパターンが何度も繰り返されるという冗長性を利用したもので、実際にはテキストデータ以外でもそのような「一定のパターンの繰り返し」は意味を持つデータなら持っている可能性が高く、ほとんどのデータに有効なので、LZ法は汎用の圧縮法として使われている。一般的なファイル圧縮フォーマットとして知られているZIPやLZHファイルもLZ法で作られているし、Windowsでは標準と言う事になっているCABもLZ法の派生である。
　実際、原理を見ると単純で、「そりゃ俺が圧縮方法考えても思いつくアイデアだよ」と思うかも知れない。確かに発想は簡単なものである。ただ、じゃあ実際どうやって一致する文字列を見つけるのか、どう圧縮展開プログラムを実装するかとなると、色々と工夫を凝らさないといけない。その工夫のバリエーションにより、元々のLempelとZivが提示したLZ77、LZ78方式から派生して、LZSS、LZX、LZW、LZMAなど様々な方式が発明されている。
　ま、考えが単純なだけあって、LZ法は抜群の圧縮率を誇るというものではないのだけども、何しろ繰り返しパターンを置き換えるだけだから、少なくとも展開プログラムは非常に高速なものが作れるという事と、LempelとZivはこの方式に対して特許を取っていないため、単純なLZ法自体はライセンス無しで使用できる。そのために人気なのだ。そう、圧縮法を考える技術者には、それは特許との戦いでもあるのだ。

　LZ法はパターンの繰り返しに目をつけた圧縮法だが、もう一つの軸として良く使われているのが、データの出現頻度に注目した符号化の方法である。
　有名なのは、Huffmanさんが1952年に発表したハフマン符号である。
　今普通に英文のテキストをデータ化すると、文字はそれぞれ8ビット(＝1バイト)で表現される。どの文字にも、均等に8ビットである。文字「A」は、「01000001」という8ビットになる。
　しかし、実際には文字の出現頻度には偏りがある。そこで、8ビットという固定長を全文字に割り当てるのではなく、可変長ビットにすればいいのではないかとなる。例えば、その文章に「A」という文字がたくさん出る場合、「A」は「01」という2ビットで表す事にする。そのかわり、「Z」という文字があまり出ないのであれば、「Z」には「0000000000001」という12ビットの数値を割り当てたりする。元の8ビットより短くなる文字もあれば、長くなる文字もある。しかし、その文章がAばかりでZという文字が出てこないのであれば、全体を平均すると1文字あたり8ビットを切り、元よりもサイズが小さくなる。
　このような符号の置き換えは割と基本なのだが、ハフマン符号化は、プログラム内部にハフマン木というツリー構造を作りながら文字の出現頻度を記録する事が可能で、コンピュータのプログラムと非常に相性が良い。そして何より、Huffmanはこの方式について特許を取らないと言っているので、使い放題なのだ。だから人気がある。
　この手の符号化については、究極的な「算術符号」という方式もある。数学的には完全な符号化で(だから算術とついている)、ハフマン符号のような他の方式が、文字の出現頻度と、各ビットの小ささの割り当ての比率が完全には一致しないのに対し、算術符号は出現頻度を実数で(つまり小数点以下全ての数値を考慮して)求めてそのまま割り当てるので、理論上もっとも小さい圧縮になる。ただ、これはただの理論であって、実際には小数点以下全てと言っても無限に続くケースがあるので、そのままではコンピュータでは実装できない。これについて長年研究が続いており、やがて実用的な手法が開発されたのだが、何しろ算術符号の技術はすでに特許が抑えられまくっているので、他のフリーの手法に比べて全く実装技術が開発されず、普及していない。

　日本で普及した可逆圧縮方式としては、LHAが有名である。1988年に吉崎さんと言う人が開発した方式で、上記のLZ法とハフマン法を組み合わせている。説明してきた通り、LZ法とハフマン法は両方コンピュータのプログラムで実装するのが簡単で、高速に処理する事ができ、しかも特許問題に直接は抵触しないので、ベストな組み合わせである。
　同様にLZ法とハフマン法を組み合わせた、海外では主流になりつつあったZIPという形式もあったが、当初はZIPは有料(シェアウェア)だったので、LHAが普及した。よって、90年代くらいは、パソコン通信を中心に日本のネット上のデータはとにかく「.lzh」という拡張子のファイルだった。
　このLHAのドキュメントの中で、圧縮されたファイルを展開する事を「解凍」、複数のファイルをまとめたアーカイブの事を「書庫」と書いていた事から、今でも日本でもその両方の用語は使われている(ただしアーカイブは元の単語の意味から言って、書庫と書くのは別段特別な事ではないが)。
　やがて、ZIPフォーマットの圧縮展開もフリーソフトになり、最終的にはWindowsでも標準的に読み書きできるようになっていったので、主流はLHAからZIPに移っていった。似たような方式ではあるが、LHAはいわゆる静的ハフマン木を使っており、圧縮前にデータをサーチして完全なハフマン木を構築するが、ZIPは動的ハフマン木で、ファイルを圧縮しながら同時にハフマン木を構築していく。その結果、圧縮率はLHAが勝り、処理速度はZIPが勝る。

　また、画像フォーマットもいくつかは可逆圧縮になっている。例えば#0045に挙げたPICなどは可逆圧縮である(ただし、最初のやなぎさわ氏のpic.rは65536色画像でも32768色に1ビット減色するので、厳密には非可逆圧縮である。後のapic.rはこれを行わないので完全に可逆圧縮である)。
　また、同じくやなぎさわ氏が作った、PC-9801などで主流の16色画像に特化したPIフォーマットも、可逆圧縮である。PIは基本的にPICと似ているのだが、PC-9801の16色画像はタイリングと呼ばれる、複数の色を交互に並べて「遠くから見ると中間の色に見える」という効果を多用しているため、単純にランレングス系の圧縮は効き辛い。そこで、横2つ分の16色ピクセルを内部的にまとめて256色のピクセル1個と見なし、またその2ピクセルの組み合わせも奇数ラインと偶数ラインで1つずつずらす。そうすると、例えば2色の市松模様だった絵は完全に1色のデータになるわけで、そうしてからPICと同じような圧縮をかけるというものである。何とも頭いいね。

　可逆圧縮画像で有名なものとしては、GIFがある。最高256色だが、圧縮率が高く、人気のフォーマットである。LZ法を使用しているため、パターンの繰り返しに強く、PIC同様同じ色が続く画像や、タイリングのような一定のパターンが繰り返される画像に対して高い圧縮率を誇った。
　ただし、GIFは特許の問題が発生したため、一時的にあまり使用されなくなった。元々GIFはCompuServeというアメリカのパソコン通信上で作られたフォーマットで、それ自体はフリーソフトであった。しかし、そのGIFの圧縮アルゴリズムであるLZW法は、アメリカのUNISYS社に特許を取られていた。UNISYSは当初、一般ユーザには特許料を求めないという態度を見せていたのだが、インターネットの普及とともにGIFが定着しつつあった1996年に、突如として自分のサイトにGIF画像を掲載しただけの人からも特許料を徴収します、GIF画像を作成するツール(フリーソフトであっても)を開発した人からは当然の事、閲覧できるビューアを作った人からも徴収しますと発表した。これは大反発を招いたが、特許を取っているのは事実なので、この時期多くのソフトでGIF画像が見れなくなった。その名残は今でもあり、GIF画像を扱えないツールは色々ある。
　そのような状況なので、その反発から汎用に使える完全フリーの可逆圧縮フォーマットであるPNGがその年に開発された。これはZIPでも使われているDeflate(中身はLZ法の一つであるLZSS法)を使った圧縮フォーマットで、GIFでは扱えなかったフルカラー画像も扱う事ができた。
　しかし、PNGはいまいちGIFを置き換えるほどの普及はしていない。一つは、GIFにあった「複数の画像データを持つ」という機能が無い事にある。GIFはこれを利用して、アニメーションGIFと呼ばれる動画を作る事が可能だが、PNGはそれが出来ない。また、個人的に問題だと思っているのが、PNGは欲張りすぎたなあと言うのがある。PNGは、あらゆる要求に答えようとして、例えば16ビットのアルファチャンネルを持っていたり、ガンマコントロールが可能だったりする。そのおかげで、それらの解釈の違いで正しく表示できなかったりした。ブラウザによっては16ビットのアルファの重ね合わせなど行わないし、またガンマ値も基準がおかしかった。PhotoShop4.0以前で作ったPNG画像は、ガンマ値がおかしいか、あるいはMacintosh準拠にしてしまうか何かで、その画像をInternetExplorerで見ると真っ黒になってしまう。万事こんな感じであった。
　そのうち、2004年になって、アメリカのUNISYSもついに反省したのか、LZW法の特許の更新手続きを行わない事にしたので、特許が切れ、晴れてGIFはフリーのフォーマットになった。これによりGIFを扱えるツールも再び多くなったし、我々もGIF画像をサイトに載せてしまい「特許料の徴収に参りました」とUNISYSのエージェントがやってくるのに怯えなくてすむようになったので、今もって可逆圧縮の画像フォーマットの筆頭はGIFである。

　なんか非常に長くなったな。
　元々、圧縮についてちょこっと書いてみようと思ったくらいなんだけど、予定よりかなり長くなったので、可逆圧縮と非可逆圧縮に分けて掲載する。よって次回は非可逆圧縮で。