Focus on Technology：静かな注目を集める圧縮アルゴリズム「LZMA」

　2001年に開発された可逆圧縮アルゴリズム「LZMA」（Lempel-Ziv-Markov chain-Algorithm）が静かな注目を集めている。LZMAといえば、高い圧縮率を備え、Windowsアーカイバ「7-Zip」に採用されていることでも知られる。

　ZIPやLHAなど、ファイルのアーカイブと圧縮が統合されているWindows由来のプログラムとは異なり、UNIXやLinuxでは伝統的にアーカイブと圧縮が個々のコマンドとして用意されており、それらを組み合わせて利用することになる。現在では、アーカイブがtar、圧縮にはGNU zip（.gz）やbzip2（.bz2）が併用されることが多い。

.gzや.bz2をしのぐ圧縮率が特徴

　ところが最近、LZMAを用いた「tar.xz」という圧縮形式を目にする機会が増えてきた。この圧縮形式は、LZMA UtilsをリリースしてきたTukaani Projectが2009年1月に正式公開したフォーマットで、GNU Coreutilsなどをはじめ、GNUプロジェクトの配布アーカイブでは徐々に使われ始めている。

　この動きは最新のLinuxカーネルにも取り込まれている。先日リリースされたLinuxカーネル2.6.30からは、コンパイル時に、makefileで「CONFIG_KERNEL_LZMA=y」を設定することでカーネルイメージの圧縮にLZMAを利用可能となっている。圧縮回数よりも伸長回数の方が多いと思われるソースコードにLZMAが用いられるのは利用者からするとかなり有用である。

　LZMAが注目されるのは、圧縮率の高さが群を抜いているためだ。圧縮にはそれなりの時間が掛かるものの、伸長は多くのケースでbzip2よりも高速に行えることも大きい。実際、GNU Coreutilsで比較してみると、GNU zipで圧縮されたcoreutils-7.4.tar.gzが9.25Mバイトであるのに対し、LZMAで圧縮されたcoreutils-7.4.tar.xzのサイズは3.86Mバイトと42％程度のサイズに収まっている。

　こうした圧縮率の高さの秘密は圧縮アルゴリズムにある。圧縮処理の最終工程で発生する「符号化」において、これまでの圧縮アルゴリズムで一般に使われていたのは、固定長のパターンに対して可変長符号を割り当てる「ハフマン符号化法」。ハフマン符号化法でパターンに割り当て可能な最短符号は1ビットであるため、データは最大でパターン長分の1までしか圧縮できない。

　これに対し、LZMAでは圧縮対象となるすべてのデータから可変長符号を算出する「算術符号化法」を採用している。正確にいえば、LZMAでは、算術符号の一種であり、整数で算術符号を実現したアルゴリズムをベースとする「Range Coder」が用いられている。Range Coderは出力単位が1ビットである算術符号に対して8ビット単位で処理するため高速に動作するのが特徴。また、算術符号は、基本的なアルゴリズムが特許申請されており、実装が敬遠されることも多いが、Range Coderは特許に抵触しない算術符号としてとらえられており、このことがLZMAの普及につながっている。

Jオプションは活用されるか

　tar.xz形式のアーカイブを展開するにはGNU tarのバージョン1.22以降と、LZMA用ユーティリティ「XZ Utils」が必要となる。環境さえ整っていれば、tarコマンドのオプションに「J」を付加することで展開（または圧縮）が行える。

　開発者であれば、コマンドオプションの入力順にも明確なロジックを持つのが必然であると筆者は考える。tarコマンドのオプションにおける至高の配列としては「xzvf」が最もロジカルなものだと考えるが、今後、「J」オプションもその仲間入りをするのかもしれない。また、LZMAはその圧縮率の高さから、組み込み用途などには重宝されることになるだろう。今後の行方に注目したい。