Lempel-Ziv-Markov chain-Algorithm

Lempel-Ziv-Markov chain-Algorithm︵略してLZMA︶は、2001年から開発されているデータ圧縮アルゴリズムで、7-Zipアーカイバの7zフォーマットやXZ Utilsのxzフォーマットで使用されている。LZMAは、LZ77に少々類似した辞書式圧縮法︵英語版︶を使用し、通常bzip2以上の高い圧縮率と伸張速度、および最大4GBのサイズ可変な圧縮辞書を特徴とする。 LZMA2は、圧縮されていないデータとLZMAデータの両方を含むことができ、複数の異なるLZMAエンコーディングパラメータを含むことができる単純なコンテナ形式である。 LZMA2は、任意にスケーラブルなマルチスレッドの圧縮と展開と、部分的に非圧縮データの効率的な圧縮をサポートする。

概要

LZMAは、改良LZ77圧縮アルゴリズムと、バックエンドにレンジコーダー︵Range Coder︶を使用している。辞書圧縮アルゴリズムは、巨大な辞書サイズと、繰り返し使用される一致距離の特別なサポートを持つLZ77の変種を使用し、その出力はレンジコーダーで符号化され、複雑なモデルを使用して各ビットの確率予測を行う。辞書圧縮で洗練された辞書データ構造を使用して一致列を見つけ、レンジコーダーにより一度に1ビットずつリテラルシンボルとフレーズリファレンスのストリームを生成する。 LZMAより前のほとんどのエンコーダモデルは純粋にバイトベースだった。 LZMAの主な革新は、一般的なバイトベースのモデルの代わりに、リテラルまたはフレーズの各表現のビットフィールドに固有のコンテキストを使用する。これは、一般的なバイトベースのモデルほど簡単だが、関連性のないビットを同じコンテキストで混在させないようにするためである。さらに、古典的な辞書圧縮︵zipやgzip形式で使用されているものなど︶と比べて、辞書のサイズは、現代のシステムで利用可能な大量のメモリを利用することができる。

LZMA形式

LZMA圧縮では、圧縮ストリームは、適応バイナリレンジコーダを使用して符号化されたビットストリームである。ストリームはパケットに分割され、各パケットは1バイトまたはLZ77シーケンスの長さと距離が暗黙的または明示的にエンコードされている。各パケットの各部分は独立したコンテキストでモデル化されるので、各ビットの確率予測は、同じタイプの以前のパケットのそのビット（および同じフィールドからの関連ビット）の値と相関がある。

LZMA2形式

LZMA2コンテナは、複数の圧縮LZMAデータと非圧縮データをサポートする。それぞれのLZMA圧縮されたラン（データの塊）は、異なるLZMA構成と辞書を持つことができる。これにより、部分的または完全な非圧縮ファイルの圧縮が改善され、並列に独立して圧縮または展開することができるようにファイルをランに分割しマルチスレッドで処理することが可能になる。

xz形式と7z形式

LZMA2データを含むことができるxz形式はtukaani.org^[1]に記載されている。また、LZMAまたはLZMA2データを含むことができる.7zファイル形式は、LZMA SDK^[2]に含まれる7zformat.txtファイルに記載されている。

LZMA SDK

LZMAを圧縮・伸長するためのSDKが公開されている[1]。ドキュメント、サンプル、ヘッダファイル、ソースコードなどを含む。ライセンスはバージョン4.62以降パブリックドメインとなった。 C++、ANSI-C、C#、Javaで実装されている。伸長アルゴリズムは全ての32ビット CPUで実装可能であり、制約をつければ16ビットCPUでも実装可能である。

速度

圧縮速度 - 1GHzのCPUで0.5MB/s
伸長速度 - 1GHzのPentium IIIで8~12MB/s。100MHzのARMで0.5~1MB/s。

7-Zipリファレンス実装

LZMAのリファレンス実装は、7zや7-Zipツールセットの一部に含まれる。ソースコードはGNU LGPLライセンスで配布されている。オープンソースのリファレンス実装であるLZMA圧縮ライブラリは、 C++で記述されていて、以下の特性がある。 ●圧縮速度: 2GHz CPUで約1MB/秒 ●伸長速度: 2GHz CPUで10~20MB/秒 ●マルチスレッドとPentium 4マイクロプロセッサのハイパースレッディング機能をサポート 7-Zip実装には、ハッシュチェイン、二分木、基数木を辞書検索アルゴリズムの基礎とする、複数の変種がある。 LZMAの伸長専用コードはC言語で記述されていて、通常5kB前後にコンパイルされる。また、伸長に必要なRAMの量は、主に圧縮時のスライド窓の大きさによって決定する。小さいコードサイズと、辞書を小さくすることにより比較的少量になるメモリ消費量は、LZMA伸長アルゴリズムをアプリケーションに組み込むのに適するものとしている。最近では、XZ Embeddedとして、特に組み込みシステム向けに特化されたライブラリが提供されている。これはLinuxカーネルに統合する事を目的としているが、独自のシステムにも容易に組み込みが可能である。

リファレンス実装の移植性

ソースコードには、広範囲でMicrosoft Windows特有の機能が使用され、しかも分離されていない。このため、リファレンス実装がフリーソフトウェアであるにもかかわらず、UNIX互換用バージョンが登場するまでに時間がかかった。現在、Unix系プラットフォームで動く移植版が2つある: ●p7zip、これは7-Zipの7zと7zaコマンドラインツールの移植版である。p7zipは、標準7zアーカイブストリームを生成する。これはLZMAに組み合せることができる追加フィルタで使用されている。フィルタは、たとえば、実行ファイルのジャンプやサブルーチン呼び出し命令の相対アドレス前処理などである。 ●LZMA Utils、これはLZMAコードだけからなる移植版である。これは生のLZMAストリームを、gzipやbzip2圧縮ユーティリティと同様に扱えるように設計されている。lzmaツールで、.tarのように複数のファイルをアーカイブできる。出力は、ヘッダ情報のない生のLZMAである。現在ではXZ Utilsがメインストリームとなり、LZMA Utilsの開発は終息している。 ●XZ Embedded、XZ Utilsの伸張コードだけを抜き出して整理したライブラリで、主にLinuxカーネルのブート時に使用する前提で設計されている。但し、他の独自のシステムにも容易に移植可能となっている。注意‥7-ZipとLZMAで生成されるLZMAストリームは異なる。つまり非互換である。基本的に、一方のツールで生成したファイルはもう一方で扱うことはできない。ただし7-Zipはバージョン4.58でLZMAストリームの伸張をサポートした。7-Zipは非圧縮時のファイルサイズを含む64ビットヘッダエントリを付加するが、LZMA Utilsではこれがない。

参照

^ “The .xz File Format” (2009年8月27日). 2018年4月22日閲覧。
^ Igor Pavlov (2013年). “LZMA SDK (Software Development Kit)”. 2018年4月22日閲覧。

外部リンク

7-Zipホームページ
7-Zip 日本語ホームページ
p7zipホームページ
PyLZMAホームページ

[1] “The .xz File Format” (2009年8月27日). 2018年4月22日閲覧。

[LZMA_SDK-2] Igor Pavlov (2013年). “LZMA SDK (Software Development Kit)”. 2018年4月22日閲覧。

[1]

[2]

概要