lzma (xz) っていうのは、圧縮アルゴリズムの中でも、圧縮にかかる時間は長いけど、圧縮率がbzip2より高くて伸長にかかる時間が比較的短いっていう特徴があります。tarのバージョン1.22からは対応しているらしい。

GNU tar 1.22リリース gzipより圧縮効率が大きく向上した「xz」をサポート:CodeZine

普通にコマンドラインから利用するだけなら

sudo aptitude install lzma lzma-dev 

でインストールされて、コマンドラインからは使えると思う。

プログラムから利用するときは lzma.hが欲しいのだけど、調べたら

$ sudo apt-get install xz-utils liblzma-dev

でいけるらしい。でも、自分の使ってるubuntuサーバ(8.04)ではそんなパッケージがないみたいなので、ソースからインストールした。

wget http://tukaani.org/xz/xz-5.0.0.tar.gz
tar zxvf xz-5.0.0.tar.gz 
cd xz-5.0.0/
./configure
make
make check
sudo make install

/usr/local/include/以下にlzma.h がインストールされます。

lzma.hを利用したプログラムは
XZ Utils の使い方
に詳しい説明があるので、参考になります。

関連: ・XZ UtilsLZMA SDK (Software Development Kit)