☰

LZMA/LZMA2 アルゴリズム ( xz, 7z)

tag-icon • tag-icon linux compression gzip
LZMA/LZMA2 アルゴリズム ( xz, 7z)

重複したファイルを含む tar アーカイブを作成して圧縮されるかどうかを調べるというちょっとした実験をしてみましたが、驚いたことに圧縮されませんでした。詳細は以下の通りです (読みやすいように結果はインデントされています)。

$ dd if=/dev/urandom bs=1M count=1 of=a
  1+0 records in
  1+0 records out
  1048576 bytes (1.0 MB) copied, 0.114354 s, 9.2 MB/s
$ cp a b
$ ln a c
$ ll
  total 3072
  -rw-r--r-- 2 guido guido 1048576 Sep 24 15:51 a
  -rw-r--r-- 1 guido guido 1048576 Sep 24 15:51 b
  -rw-r--r-- 2 guido guido 1048576 Sep 24 15:51 c
$ tar -c * -f test.tar
$ ls -l test.tar 
  -rw-r--r-- 1 guido guido 2109440 Sep 24 15:51 test.tar
$ gzip test.tar 
$ ls -l test.tar.gz 
  -rw-r--r-- 1 guido guido 2097921 Sep 24 15:51 test.tar.gz
$

まず、ランダム データの 1MiB ファイル (a) を作成しました。次に、それをファイル b にコピーし、さらに c にハードリンクしました。tarball を作成するときに、tar はハードリンクを認識したようで、tarball は ~3Mib ではなく ~2MiB しかありませんでした。

ここで、a と b は重複しており、tarball 内に 1MiB の連続データが繰り返されるはずなので、gzip によって tarball のサイズが約 1MiB に縮小されると予想しましたが、これは起こりませんでした。

これはなぜでしょうか? このような場合に tarball を効率的に圧縮するにはどうすればよいでしょうか?

答え1

Gzip gzip は、LZ77 とハフマン コーディングを組み合わせた DEFLATE アルゴリズムに基づいています。これはロスレス データ圧縮アルゴリズムで、オンザフライで構築された辞書を使用して入力ストリームを圧縮シンボルに変換し、重複を監視することで機能します。ただし、32K 以上離れた重複を見つけることはできません。1MB 離れた重複を見つけることを期待するのは現実的ではありません。

答え2

ニコール・ハミルトンは正しく指摘しているgzip辞書のサイズが小さいため、遠く離れた重複データは見つかりません。

bzip2メモリが 900 KB に制限されているので、同様です。

代わりに、次のことを試してください。

LZMA/LZMA2 アルゴリズム ( xz, 7z)

LZMA アルゴリズムは Deflate と同じファミリーですが、はるかに大きな辞書サイズを使用します (カスタマイズ可能、デフォルトは約 384 MB)。xz最新の Linux ディストリビューションのほとんどにデフォルトでインストールされているこのユーティリティは、LZMA に似ておりgzip、LZMA を使用します。

LZMA は長距離の冗長性を検出するため、ここでデータの重複を排除できます。ただし、Gzip よりも低速です。

もう 1 つのオプションは 7-zip (パッケージ7zではp7zip) です。これは、(シングル ストリーム コンプレッサーではなく) デフォルトで LZMA を使用するアーカイバです (LZMA の作者によって作成されました)。7-zip アーカイバは、その形式にアーカイブするときに、ファイル レベルで独自の重複排除を実行します (同じ拡張子を持つファイルを参照) 。つまり、を に.7z置き換えてもかまわない場合は、重複排除された同一のファイルが得られます。ただし、7z はナノ秒のタイムスタンプ、権限、または xattr を保持しないため、ニーズに合わない可能性があります。tar7z

lrzip

lrzipは、データを Gzip/Deflate、bzip2、lzop、LZMA などの従来のアルゴリズムに渡す前に、データを前処理して長距離冗長性を削除する圧縮プログラムです。ここで示すサンプル データの場合、これは必要ありません。入力データがメモリに収まるサイズよりも大きい場合に便利です。

この種のデータ (重複した圧縮不可能なチャンク) の場合は、lzopによる圧縮 (非常に高速)を使用する必要がありますlrzip。重複が排除された後は、完全にランダムなデータを圧縮しようとしてもメリットがないためです。

バップとオブナム

質問にタグを付けたのでここでの目標がデータのバックアップである場合は、次のような重複排除バックアッププログラムの使用を検討してください。バップまたはオブナム。

答え3

gzip辞書のサイズが巨大であっても、重複は見つかりませんxz。 を使用すればmksquashfs、重複のスペースを節約できます。

3 つのランダムなバイナリ ファイル (64 MB) のうち 2 つが同じものを使用した簡単なテスト結果をxz以下に示します。mksquashfs

設定：

mkdir test
cd test
dd if=/dev/urandom of=test1.bin count=64k bs=1k
dd if=/dev/urandom of=test2.bin count=64k bs=1k
cp test{2,3}.bin
cd ..

スカッシュ：

mksquashfs test/ test.squash
> test.squash - 129M

: ...

XZ_OPT='-v --memlimit-compress=6G --memlimit-decompress=512M --lzma2=preset=9e,dict=512M --extreme -T4 ' tar -cJvf test.tar.xz test/
> test.tar.xz - 193M

答え4

「機械のカタツムリ」の回答への追加:

圧縮されていない単一ファイルのファイル サイズ (または、より正確には、重複間の距離) が辞書のサイズを超える場合、xz (または lzma) でも重複を見つけることはできません。xz (または lzma) は、最高設定でも、-9eこれに 64 MB しか予約しません。

幸いなことに、オプションを使用して独自の辞書サイズを指定できます--lzma2=dict=256MB （--lzma1=dict=256MBコマンドにlzmaエイリアスを使用する場合にのみ許可されます）

残念ながら、上記の例のようにカスタム圧縮チェーンで設定を上書きすると、他のすべてのパラメータのデフォルト値は -9e と同じレベルに設定されません。そのため、単一ファイルの圧縮密度はそれほど高くありません。

関連情報