Lempel-Ziv-Markov 連鎖アルゴリズム

Lempel –Ziv–Markov連鎖アルゴリズム（LZMA）は、ロスレスデータ圧縮に使用されるアルゴリズムです。1996年または1998年からIgor Pavlovによって開発され^{[要出典] 、} 7-Zipアーカイバの7z形式で初めて使用されました。このアルゴリズムは、 1977年にAbraham LempelとJacob Zivによって公開されたLZ77アルゴリズムに似た辞書圧縮方式を使用しており、高い圧縮率（一般にbzip2よりも高い）^{[1] [2]}と可変の圧縮辞書サイズ（最大4  GB）^[3]を特徴としながら、一般的に使用されている他の圧縮アルゴリズムと同様の解凍速度を維持しています。^[4]

LZMA2は、非圧縮データとLZMAデータの両方を含むことができるシンプルなコンテナフォーマットで、複数の異なるLZMAエンコードパラメータを持つこともできます。LZMA2は、任意にスケーラブルなマルチスレッド圧縮と解凍、および部分的に圧縮できないデータの効率的な圧縮をサポートします。^[5]

LZMAは辞書圧縮アルゴリズム（巨大な辞書サイズと繰り返し使用される一致距離の特別なサポートを備えたLZ77の変種）を使用し、その出力は範囲エンコーダでエンコードされ、複雑なモデルを使用して各ビットの確率予測が行われます。辞書コンプレッサーは洗練された辞書データ構造を使用して一致を見つけ、リテラルシンボルとフレーズ参照のストリームを生成します。これは範囲エンコーダによって一度に1ビットずつエンコードされます。多くのエンコードが可能であり、動的プログラミングアルゴリズムを使用して特定の近似の下で最適なものを選択します。^[6]

LZMA 以前は、ほとんどのエンコーダ モデルは純粋にバイトベースでした (つまり、同じバイトの前のビットへの依存関係を表すために、コンテキストのカスケードのみを使用して各ビットをコード化していました)。LZMA の主な革新は、一般的なバイトベース モデルではなく、LZMA のモデルでは、リテラルまたはフレーズの各表現のビットフィールドに固有のコンテキストを使用することです。これは一般的なバイトベース モデルとほぼ同じくらい単純ですが、無関係なビットが同じコンテキストに混在するのを防ぐため、はるかに優れた圧縮を実現します。さらに、従来の辞書圧縮 ( zip形式やgzip形式で使用されるものなど) と比較すると、辞書のサイズははるかに大きくすることができ、通常ははるかに大きくなります。これは、現代のシステムで利用可能な大量のメモリを活用しています。^[6]

LZMA 圧縮では、圧縮ストリームは、適応バイナリ範囲コーダを使用してエンコードされたビットのストリームです。ストリームはパケットに分割され、各パケットは 1 バイト、または長さと距離が暗黙的または明示的にエンコードされた LZ77 シーケンスを記述します。各パケットの各部分は独立したコンテキストでモデル化されるため、各ビットの確率予測は、同じタイプの以前のパケットのそのビットの値 (および同じフィールドの関連ビット) と相関します。lzip ^[7]と LZMA SDK ドキュメントの両方で、このストリーム形式について説明しています。^[6]

パケットには7つの種類があります: ^[7]

LONGREP[*]はLONG​​REP[0–3]パケットを参照し、*REPはLONG​​REPとSHORTREPの両方を参照し、*MATCHはMATCHと*REPの両方を参照します。

LONGREP[n]パケットは、最新の距離のリストから使用された距離を削除し、無駄な繰り返しエントリを回避するために先頭に再挿入しますが、MATCHは、リストにすでに存在する場合でも距離を先頭に追加するだけであり、SHORTREPとLONGREP[0]はリストを変更しません。

長さは次のようにエンコードされます。

LZ77 と同様に、辞書からのコピーは、距離を一定に保ちながらバイトごとにコピーが実行されるかのように定義されているため、長さは距離によって制限されません。

距離は論理的には 32 ビットであり、距離 0 は辞書に最後に追加されたバイトを指します。

距離のエンコードは 6 ビットの「距離スロット」から始まり、これによってさらに必要なビット数が決まります。距離は、次の表に従って、距離スロットに応じて上位から下位までの 2 ビット、固定 0.5 の確率でエンコードされたビット、およびコンテキストでエンコードされたビットのバイナリ連結としてデコードされます (距離スロット 0〜3 は距離 0〜3 を直接エンコードします)。

以下のテキストで試みられているもの以外に、圧縮形式の完全な自然言語仕様は存在しないようです。

以下の説明は、Linuxカーネルソース^{[8]に含まれるLasse Collinによるコンパクトな}XZ Embeddedデコーダに基づいています。このデコーダから、LZMAおよびLZMA2アルゴリズムの詳細を比較的簡単に推測できます。したがって、ソースコードを参照として引用することは理想的ではありませんが、どのプログラマーでも数時間の作業で以下の主張を確認できるはずです。

LZMA データは、LZMA デコーダーの指示に従って、範囲デコーダーによって 1 ビットずつデコードされる最下位レベルです。

コンテキストベースの範囲デコードは、LZMA アルゴリズムによって呼び出され、「コンテキスト」への参照を渡します。コンテキストは、ビットが 0 になる予測確率を表す符号なし 11 ビット変数prob (通常は 16 ビットのデータ型を使用して実装されます) で構成され、範囲デコーダーによって読み取られて更新されます (確率 0.5 を表す⁠ ⁠${\displaystyle 2^{10}}$に初期化される必要があります)。

固定確率範囲デコードでは、代わりに 0.5 の確率を想定しますが、コンテキストベースの範囲デコードとは少し異なる動作をします。

範囲デコーダーの状態は、範囲(範囲のサイズを表す) とコード(範囲内のエンコードされたポイントを表す) の 2 つの符号なし 32 ビット変数で構成されます。

範囲デコーダーの初期化は、範囲を2 ³² − 1に設定し、コードをビッグエンディアンとして解釈されたストリームの 2 番目のバイトから始まる 32 ビット値に設定することから構成されます。ストリームの最初のバイトは完全に無視されます。

正規化は次のように進行します。

1. 範囲とコードの両方を8ビット左にシフトします
2. 圧縮ストリームから1バイトを読み込む
3. コードの下位8ビットを読み取ったバイト値に設定する

prob確率変数を使用したビットのコンテキストベースの範囲デコードは次のように進行します。

1. 範囲が⁠ ⁠${\displaystyle 2^{24}}$未満の場合は正規化を実行します
2. バインドを設定する⁠ ⁠${\displaystyle \lfloor range/2^{11}\rfloor \times prob}$
3. コードが境界より小さい場合:
   1. 範囲を境界に設定
   2. prob をprob +に設定⁠ ⁠${\displaystyle \lfloor 2^{11}-prob\rfloor /2^{5}}$
   3. ビット0を返す
4. それ以外の場合（コードが境界以上の場合）：
   1. 範囲を範囲−境界に設定する
   2. コードをコードに設定−バインド
   3. 問題を⁠ ⁠に設定${\displaystyle prob-\lfloor prob/2^{5}\rfloor }$
   4. ビット1を返す

ビットの固定確率範囲のデコードは次のように進行します。

1. 範囲が⁠ ⁠${\displaystyle 2^{24}}$未満の場合は正規化を実行します
2. 範囲を⁠ ⁠に設定${\displaystyle \lfloor range/2\rfloor }$
3. コードが範囲より小さい場合:
   1. ビット0を返す
4. それ以外の場合（コードが範囲より大きいか等しい場合）：
   1. コードをコード−範囲に設定する
   2. ビット1を返す

の固定確率デコードの Linux カーネル実装ではrc_direct()、パフォーマンス上の理由から、条件分岐は含まれず、代わりに無条件にcodeからrangeが減算されます。結果の符号ビットは、返すビットを決定するためと、 codeと組み合わせてrangeに追加されるマスクを生成するために使用されます。

ご了承ください：

1. 境界演算と床演算を計算するときの⁠ ⁠${\displaystyle 2^{11}}$による除算は、乗算の後ではなく前に行われます（明らかに、64 ビットの結果を持つ 32 ビット乗算に高速なハードウェアサポートが必要になるのを避けるため）
2. 固定確率デコードは、コンテキストベースの範囲デコードと厳密には同等ではありません。コンテキストベースの範囲デコードでは、前述のように範囲の下位11ビットを破棄してから確率を掛け算しますが、固定確率デコードでは最後のビットのみを破棄するためです。

範囲デコーダーは、ビットツリー、逆ビットツリー、および固定確率整数デコード機能も提供します。これらは整数をデコードするために使用されるもので、上記の単一ビットデコードを一般化します。limit未満の符号なし整数をデコードするために、 ( limit − 1) 個の 11 ビット確率変数の配列が提供されます。これは、 limit 個の葉を持つ完全なバイナリツリーの内部ノードとして概念的に配置されます。

非逆ビットツリー デコードは、ルートから始まる変数のツリーへのポインターを保持することで機能します。ポインターがリーフを指していない限り、ビットはポインターによって示される変数を使用してデコードされ、ビットが 0 か 1 かに応じてポインターは左または右の子に移動されます。ポインターがリーフを指している場合は、リーフに関連付けられた番号が返されます。

したがって、非逆ビットツリーのデコードは、最上位ビットから最下位ビットまで行われ、有効な範囲内で 1 つの値のみが可能になった時点で停止します (これにより、概念的には 2 の累乗ではない範囲サイズが可能になりますが、LZMA ではこれを使用しません)。

逆ビットツリーデコードでは、代わりに最下位ビットから最上位ビットにデコードするため、2 の累乗の範囲のみがサポートされ、常に同じ数のビットがデコードされます。これは、2 の累乗 limit を使用して非逆ビットツリーデコードを実行し、結果の 最後のlog ₂ ( limit )ビットを逆にすることと同じです。

Linux カーネルのrc_bittree関数では、実際には[ limit , 2 × limit )の範囲の整数が返され (概念的な値にlimitが加算されます)、配列のインデックス 0 の変数は未使用ですが、インデックス 1 の変数はルートであり、左と右の子のインデックスは 2 iと 2 i + 1として計算されます。 rc_bittree_reverse関数は、代わりに[0, limit )の範囲の整数を呼び出し元が指定した変数に追加します。ここで、limit は暗黙的にその対数で表され、効率上の理由から独自の独立した実装があります。

固定確率の整数デコードは、単純に固定確率のビットデコードを繰り返し実行し、最上位から最下位のビットを読み取ります。

LZMA デコーダーは、lclppb「プロパティ」バイトと辞書サイズによって構成されます。lclppb バイトの値は、lc + lp × 9 + pb × 9 × 5です。ここで、

• lc は、リテラルエンコードのコンテキストとして使用する前のバイトの上位ビットの数です (LZMA SDK で使用されるデフォルト値は 3 です)
• lp は、literal_pos_stateに含める辞書位置の下位ビットの数です(LZMA SDK で使用されるデフォルト値は 0 です)
• pb は、 pos_stateに含める辞書位置の下位ビットの数です(LZMA SDK で使用されるデフォルト値は 2 です)

非 LZMA2 ストリームでは、lc は8 より大きくてはならず、lpとpb は4 より大きくてはなりません。LZMA2 ストリームでは、( lc + lp )とpb は4 より大きくてはなりません。

7-zip LZMA ファイル形式では、設定は「プロパティ」バイトとそれに続く 32 ビットのリトルエンディアン辞書サイズ (バイト単位) を含むヘッダーによって実行されます。LZMA2 では、プロパティ バイトは LZMA2 LZMA パケットの開始時にオプションで変更できますが、辞書サイズは後述のとおり LZMA2 ヘッダーで指定されます。

LZMA パケット形式については既に説明しましたが、このセクションでは、LZMA が LZ エンコードされたストリームを統計的にモデル化する方法、つまり、各ビットをデコードするために範囲デコーダーに渡される確率変数を指定します。

これらの確率変数は多次元配列として実装されます。それらを導入する前に、これらの多次元配列のインデックスとして使用されるいくつかの値が定義されます。

状態値は、概念的には、次の表のパターンのどれが最新の 2 ～ 4 個のパケットタイプに一致するかに基づいており、パケットが出力されるたびに、表にリストされている遷移表に従って更新されるステート マシン状態として実装されます。

初期状態は 0 であるため、開始前のパケットは LIT パケットであると見なされます。

pos_state値とliteral_pos_state値は、それぞれ辞書位置 (辞書サイズを法として最後の辞書リセット以降にコード化されたバイト数) の最下位ビットの pb と lp (LZMA ヘッダーまたは LZMA2 プロパティ パケットから最大 4) で構成されます。辞書サイズは通常、2 の大きな累乗の倍数であるため、これらの値は、最後の辞書リセット以降に確認された非圧縮バイト数の最下位ビットとして同等に記述されることに注意してください。

prev_byte_lc_msbs値は、前の非圧縮バイトのlc (LZMA ヘッダーまたは LZMA2 プロパティ パケットからの最大 4) の最上位ビット に設定されます。

is_REP値は、長さを含むパケットが MATCH ではなく LONGREP であるかどうかを示します。

match_byte値は、 SHORTREP パケットが使用されていた場合にデコードされるバイト (つまり、最後に使用された距離の辞書で見つかったバイト) であり、*MATCH パケットの直後にのみ使用されます。

literal_bit_modeは、0～2 の範囲の 8 つの値の配列で、バイト内の各ビット位置に 1 つずつ対応します。前のパケットが *MATCH で、それが最上位ビット位置であるか、エンコード/デコードするリテラル内の上位ビットすべてがmatch_byte内の対応する位置のビットと等しい場合は 1 または 2 になり、それ以外の場合は 0 になります。1 または 2 の値の選択は、 match_byte内の同じ位置のビットの値によって決まります。

リテラル/リテラル​​変数セットは、ビットツリーに似た「疑似ビットツリー」として見ることができますが、各ノードに 1 つではなく 3 つの変数があり、ノードによって示されるビットツリー コンテキストの後にデコードする次のビットのビット位置の literal_bit_mode 値 に応じて選択されます。

いくつかの情報源で見られる、*MATCH の後のリテラルは、バイト値とmatch_byteの XOR としてコード化されるという主張は誤りです。代わりに、それらは、先ほど説明した疑似ビットツリーと、以下の表にリストされている追加のコンテキストを使用して、単純にバイト値としてコード化されます。

LZMA で使用される確率変数グループは次のとおりです。

LZMA2 コンテナは、圧縮された LZMA データと非圧縮データの複数の実行をサポートします。各 LZMA 圧縮実行は、異なる LZMA 構成と辞書を持つことができます。これにより、部分的にまたは完全に圧縮できないファイルの圧縮が改善され、ファイルを並列で独立して圧縮または解凍できる実行に分割することで、マルチスレッド圧縮とマルチスレッド解凍が可能になります。LZMA に対する LZMA2 の変更点に対する批判には、ヘッダー フィールドが CRC でカバ​​ーされないこと、並列解凍が実際には不可能であることなどがあります。^[5]

LZMA2 ヘッダーは、辞書のサイズを示すバイトで構成されます。

• 40は4GB−1の辞書サイズを示す
• 40未満の値でも、辞書のサイズは2 ^{v /2 + 12}バイトであることを示します。
• 40未満の奇数値は3×2 ^{( v − 1)/2 + 11}バイトの辞書サイズを示す。
• 40 を超える値は無効です

LZMA2 データは、次の値を持つ制御バイトで始まるパケットで構成されます。

• 0はファイルの終わりを表します
• 1は辞書のリセットとそれに続く非圧縮チャンクを示す
• 2は辞書リセットのない非圧縮チャンクを示す
• 3～0x7fは無効な値です
• 0x80～0xffはLZMAチャンクを示し、下位5ビットは非圧縮サイズのビット16～20から1を引いたものとして使用され、ビット5～6はリセットすべきものを示します。

LZMA チャンクのビット 5 ～ 6 は次のようになります。

• 0: 何もリセットされない
• 1: 状態リセット
• 2: 状態リセット、プロパティバイトを使用したプロパティのリセット
• 3: 状態のリセット、プロパティ バイトを使用したプロパティのリセット、辞書のリセット

LZMA 状態リセットにより、辞書を除くすべての LZMA 状態がリセットされます。具体的には、次のようになります。

• レンジコーダー
• 状態値​
• 繰り返し試合の最後の距離
• すべてのLZMA確率

圧縮されていないチャンクは次のもので構成されます。

• データサイズから1を引いた16ビットのビッグエンディアン値
• 辞書にそのままコピーされるデータと出力

LZMA チャンクは次のものから構成されます。

• 圧縮されていないサイズの下位16ビットから1を引いた値をエンコードした16ビットのビッグエンディアン値
• 圧縮サイズから1を引いた値をエンコードした16ビットのビッグエンディアン値
• 制御バイトのビット6が設定されている場合、プロパティ/lclppbバイト
• LZMA 圧縮データ。範囲コーダを初期化するために使用される 5 バイト (最初の 1 バイトは無視されます) から始まります (圧縮サイズに含まれます)

LZMA2データを含めることができる.xz形式はtukaani.org[9]で文書化されていますが^、 LZMAまたはLZMA2データを含めることができる.7zファイル形式はLZMA SDKに含まれる7zformat.txtファイルで文書化されています。^[10]

7-Zipから抽出されたLZMA実装は、LZMA SDKとして入手可能です。これはもともとGNU LGPLとCommon Public Licenseの両方の下でデュアルライセンスされていましたが^[11]、リンクされたバイナリに対する追加の特別な例外がありましたが、2008年12月2日にバージョン4.62がリリースされ、Igor Pavlovによってパブリックドメインになりました。 ^[10]

LZMAの改良版であるLZMA2圧縮^[12]は、 2012年10月26日のバージョン9.30から、.7z形式のデフォルトの圧縮方式になりました。^[13]

オープンソースの参照LZMA圧縮ライブラリはもともとC++で書かれていましたが、 ANSI C、C#、Javaに移植されています。^{[10] C++ライブラリ用のサードパーティの}Pythonバインディングや、Pascal、Go、AdaへのLZMAの移植版もあります。^{[14] [15] [16] [17]}

7-Zip の実装では、辞書検索アルゴリズムの基礎として、 ハッシュ チェーン、バイナリ ツリー、パトリシア ツリーのいくつかのバリエーションを使用します。

LZMA に加えて、SDK と 7-Zip は、単純なデルタ エンコーディング(画像用)から実行可能コード用の BCJ まで、圧縮を向上させるための複数の前処理フィルターも実装しています。また、7z で使用されるその他の圧縮アルゴリズムもいくつか提供しています。

LZMA の解凍専用コードは、通常約 5 KB にコンパイルされ、解凍中に必要な RAM の量は、主に圧縮中に使用されるスライディング ウィンドウのサイズによって決まります。コード サイズが小さく、特に辞書の長さが短い場合のメモリ オーバーヘッドが比較的低く、ソース コードが無料であるため、LZMA 解凍アルゴリズムは組み込みアプリケーションに適しています。

7-Zip リファレンス実装に加えて、以下も LZMA 形式をサポートしています。

• xz : gzip のようなコマンドラインツールを含むストリーミング実装で、 xz ファイル形式で LZMA と LZMA2 の両方をサポートしています。これは、その高いパフォーマンス ( bzip2と比較して) と小さいサイズ ( gzipと比較して)により、Unix 系の世界のいくつかのソフトウェアに採用されました。 ^[1] Linuxカーネル、dpkg、RPMシステムにはxzコードが含まれており、 kernel.org、Debian ^[18]、Fedoraなどの多くのソフトウェアディストリビューターは現在、リリースの圧縮にxzを使用しています。
• lzip : 主にUnix系システム向けのLZMA実装で、xzと直接競合します。^[19]主にファイル形式がシンプルなため、エラー回復が容易です。
• ZIPX : WinZipバージョン12.1以降で作成されたZIP圧縮形式の拡張。BZipやPPMdなど、他のさまざまな圧縮方法も使用できます。 [ ^20]

LZHAM（LZ、ハフマン、算術、マルコフ）は、LZMAに似た実装で、圧縮スループットを犠牲にして非常に高い比率と高い解凍スループットを実現しています。 2020年9月15日に作者によってパブリックドメインになりました^。[21]

• 公式ホームページ
• Lzip フォーマット仕様
• XZフォーマット仕様
• LZMA SDK (ソフトウェア開発キット)
• LZMA ユーティリティ = XZ ユーティリティ
• XZ Utils の Windows バイナリ
• データ圧縮、コンプレッサー、アーカイバ