LZ77とLZ78

LZ77とLZ78 は、1977 年^[1]と 1978 年^[2]にAbraham LempelとJacob Zivが論文で発表した2 つの可逆データ圧縮 アルゴリズムです。これらはそれぞれLZ1とLZ2 とも呼ばれます。^[3]これら 2 つのアルゴリズムは、LZW、LZSS、LZMAなど多くのバリエーションの基礎となっています。学術的な影響以外にも、これらのアルゴリズムは、 GIFやPNGおよびZIPで使用されるDEFLATEアルゴリズムなど、広く普及しているいくつかの圧縮方式の基礎となっています。

どちらも理論的には辞書コーダです。LZ77 は圧縮中にスライディング ウィンドウを維持します。これは後にLZ78 によって構築された明示的な辞書と同等であることが示されましたが、データ全体を解凍する場合のみ同等になります。

LZ77 は、以前に見た文字をスライディングウィンドウからエンコードおよびデコードするため、解凍は常に入力の先頭から開始する必要があります。概念的には、辞書全体が事前にわかっていれば、LZ78 解凍により入力へのランダムアクセスが可能になります。ただし、実際には、辞書はエンコードおよびデコード中にトークンが出力されるたびに新しいフレーズを作成することによって作成されます。^[4]

このアルゴリズムは2004年にIEEEマイルストーンに指定されました^。[5] 2021年にジェイコブ・ジヴは開発への貢献によりIEEE名誉賞を受賞しました。 ^[6]

これらのアルゴリズムを紹介した 2 つの論文のうち 2 つ目の論文では、有限状態マシンによって定義されたエンコーダとして分析されています。情報エントロピーに類似した尺度が、個々のシーケンス (確率的アンサンブルとは対照的) に対して開発されています。この尺度は、達成可能なデータ圧縮率の上限を示します。次に、シーケンスの長さが無限に増えてもこの上限を達成する有限のロスレス エンコーダがすべてのシーケンスに対して存在することを示します。この意味で、このスキームに基づくアルゴリズムは、漸近的に最適なエンコードを生成します。この結果は、たとえばPeter Shorのノートのように、より直接的に証明できます。^[7]

正式には、（定理13.5.2 ^[8]）。

同様の定理が LZ アルゴリズムの他のバージョンにも適用されます。

LZ77 アルゴリズムは、データの繰り返し出現を、非圧縮データ ストリーム内の前のデータ コピーへの参照に置き換えることで圧縮を実現します。一致は、長さと距離のペアと呼ばれる 1 組の数字でエンコードされます。これは、「次の長さの文字のそれぞれは、非圧縮ストリーム内でその文字からちょうどdistance文字後ろにある文字に等しい」というステートメントに相当します (距離はオフセットと呼ばれることもあります)。

一致を見つけるために、エンコーダーは、最後の 2 KB、4 KB、または 32 KBなどの最新のデータの一部を追跡する必要があります 。このデータが保持される構造はスライディング ウィンドウと呼ばれ、これが LZ77 がスライディング ウィンドウ圧縮と呼ばれる理由です。エンコーダーは一致を探すためにこのデータを保持する必要があり、デコーダーはエンコーダーが参照する一致を解釈するためにこのデータを保持する必要があります。スライディング ウィンドウが大きいほど、エンコーダーが参照を作成するために検索する範囲が広がります。

長さと距離のペアで、実際に距離を超える長さを指定できるようにすることは、許容されるだけでなく、多くの場合役立ちます。コピー コマンドとして、これは不可解です。「4文字戻って、その位置から10文字を現在の位置にコピーします。」 実際には 4 文字しかバッファーにない場合、10 文字をコピーするにはどうすればよいでしょうか。 一度に 1 バイトずつ処理すれば、この要求に問題なく対応できます。バイトがコピーされると、コピー コマンドへの入力として再度入力される可能性があるためです。コピー元の位置が最初の宛先の位置に到達すると、コピー元の位置の先頭から貼り付けられたデータが結果として入力されます。したがって、この操作は、「与えられたデータをコピーし、収まるまで繰り返し貼り付ける」というステートメントと同じです。 このタイプのペアは 1 つのデータのコピーを複数回繰り返すため、柔軟で簡単な形式のランレングス エンコーディングを組み込むために使用できます。

別の見方をすると、次のようになります。エンコード中に、検索ポインタが検索ウィンドウの終わりを超えて一致したペアの検索を継続するには、オフセットDの最初の一致から検索ウィンドウの終わりまでのすべての文字に一致する入力が必要です。これらは、長さL _Rの単一の実行単位を構成する (前に見た) 文字であり、 Dに等しくなければなりません。次に、検索ポインタが検索ウィンドウを超えて進むと、実行パターンが入力内で繰り返される限り、検索ポインタと入力ポインタは同期し、実行パターンが中断されるまで文字を一致させます。すると、合計でL文字が一致し、 L > Dとなり、コードは [ D、L、c ] になります。

[ D , L , c ] をデコードすると、再びD = L _Rになります。最初のL _R文字が出力に読み込まれると、これは出力バッファに追加された単一の実行単位に対応します。この時点で、読み取りポインタは、その単一のバッファリングされた実行単位の先頭に int( L / L _R ) + ( L mod L _{R ≠ 0 の場合は 1) 回返し、} L _R文字 (または最後の戻りでより少ない文字数)を読み取り、合計L文字が読み取られるまで繰り返すだけでよいと考えられます。ただし、エンコード プロセスを反映して、パターンが反復的であるため、読み取りポインタは、合計L文字が出力にコピーされる まで、実行長L _Rに等しい固定距離だけ書き込みポインタと同期して追跡するだけで済みます。

上記を考慮すると、特にデータ ランの圧縮が優勢になると予想される場合は、ウィンドウ検索はウィンドウの最後から開始して逆方向に進む必要があります。これは、ラン パターンが存在する場合は、それが最初に検出され、検索を終了できるためです。これは、現在の最大一致シーケンス長が満たされている場合は絶対に、十分な長さが満たされている場合は慎重に、そして最後に、データがより新しいため次の入力との相関性が高くなる可能性があるという単純な可能性に基づいています。

次の疑似コードは、LZ77 圧縮アルゴリズムのスライディング ウィンドウを再現したものです。

入力が空でない間は
    一致:=ウィンドウ内で始まる入力の最長繰り返し出現
    
    一致するものが存在する場合
        d := 試合開始までの距離
        l := マッチの長さ
        c := 入力内の一致後の文字
    それ以外
        d := 0
        0 := 0 です
        c := 入力の最初の文字
    終了の場合
    
    出力（d、l、c）
    ウィンドウの先頭からl + 1 文字
    を削除します
    s :=入力の先頭からl + 1 文字を取り出す
    ウィンドウの後ろに s を追加する
繰り返す

すべての LZ77 アルゴリズムは定義上は同じ基本原理に基づいて動作しますが、圧縮されたデータをエンコードする方法は大きく異なり、長さと距離のペアの数値範囲を変えたり、長さと距離のペアに消費されるビット数を変更したり、長さと距離のペアをリテラル(長さと距離のペアの一部としてではなく、それ自体としてエンコードされた生データ) と区別したりします。次に例をいくつか示します。

• Lempel と Ziv の 1977 年のオリジナル論文で説明されているアルゴリズムは、すべてのデータを 3 つの値 (バッファー内で見つかった最長一致の長さと距離、およびその一致に続くリテラル) で一度に出力します。入力ストリーム内の連続する 2 つの文字をリテラルとしてのみエンコードできる場合、長さと距離のペアの長さは 0 になります。
• LZSS は、1 ビットのフラグを使用して次のデータ チャンクがリテラルであるか、長さと距離のペアであるかを示すことで LZ77 を改良し、長さと距離のペアの方が長くなる場合はリテラルを使用します。
• PalmDoc 形式では、長さと距離のペアは常に 2 バイトのシーケンスでエンコードされます。この 2 バイトを構成する 16 ビットのうち、11 ビットは距離のエンコードに、3 ビットは長さのエンコードに使用され、残りの 2 ビットはデコーダーが最初のバイトをそのような 2 バイト シーケンスの始まりとして識別できるようにするために使用されます。
• エレクトロニック・アーツの多くのゲームで使用されている実装では、^[9]長さと距離のペアのバイトサイズは、長さと距離のペアの最初のバイト自体で指定できます。最初のバイトが 0、10、110、または 111 のいずれで始まるか (ビッグエンディアンビット方向で読み取った場合) に応じて、長さと距離のペア全体の長さは 1 バイトから 4 バイトになります。
• 2008年現在^{[アップデート]}、最も人気のあるLZ77ベースの圧縮方法はDEFLATEで、LZSSとハフマン符号化を組み合わせたものです。^[10]リテラル、長さ、および現在のデータブロックの終了を示す記号はすべて1つのアルファベットにまとめられています。距離は別のアルファベットに安全に配置できます。距離は長さの直後にのみ出現するため、他の種類の記号と間違われることはありませんし、その逆も同様です。

LZ78 アルゴリズムは、入力からトークン シーケンスの辞書を作成し、データ ストリーム内の 2 番目以降のシーケンスを辞書エントリへの参照に置き換えることによって、シーケンシャル データを圧縮します。繰り返しシーケンスの数は、シーケンスの非ランダム性を測る良い指標であることがわかります。アルゴリズムは、辞書を n 項ツリーとして表します。ここで、n はトークン シーケンスを形成するために使用されるトークンの数です。各辞書エントリは の形式です。dictionary[...] = {index, token}ここで、インデックスは、以前に表示されたシーケンスを表す辞書エントリへのインデックス、トークンは、このエントリを辞書内で一意にする入力からの次のトークンです。アルゴリズムが貪欲であるため、一意になるトークンが見つかるまでテーブルに何も追加されないことに注意してください。アルゴリズムは、最後の一致インデックス = 0、次の使用可能なインデックス = 1 に初期化し、次に、入力ストリームの各トークンについて、辞書で一致を検索します。{last matching index, token}一致が見つかった場合、最後の一致インデックスは一致エントリのインデックスに設定され、何も出力されず、最後の一致インデックスがこれまでの入力を表すままになります。入力は一致するものが見つからなくなるまで処理されます。その後、新しい辞書エントリが作成され、dictionary[next available index] = {last matching index, token}アルゴリズムは最後に一致するインデックスを出力し、その後トークンを出力し、最後に一致するインデックスを0にリセットして、次の利用可能なインデックスを増分します。例として、トークンのシーケンスを考えてみましょう。アッバ辞書を組み立てることになります。

0 {0,_}
1 {0,A}
2 {1,B}
3 {0,B}

圧縮データの出力順序は次のようになる。0A1B0B最後のAはまだ表現されていないことに注意してください。アルゴリズムは次に何が来るか分からないからです。実際には、EOFマーカーが入力に追加されます。ああ、ああ例えば、この場合の出力は0A1B0B1$元の入力よりも長くなりますが、辞書が大きくなるにつれて圧縮率が大幅に向上し、バイナリではインデックスを最小ビット数以上で表現する必要はありません。^[11]

解凍は、圧縮されたシーケンスから辞書を再構築することから成ります。シーケンスから0A1B0B1$最初のエントリは常にターミネータです0 {...}、そしてそのシーケンスの最初のものは1 {0,A}。あ出力に追加されます。入力からの2番目のペアは1B辞書のエントリ番号2に結果が表示されます。{1,B}トークン「B」が出力され、その前に辞書エントリ1で表されるシーケンスが続きます。エントリ1は「A」（その後に「エントリ0」が続く）なので、AB出力に追加されます。次に0B次のエントリとして辞書に追加されます。3 {0,B}、B（何も付かない）が出力に追加されます。最後に、1ドル作成され、オーストラリアドル出力結果はA AB BA$またはアッバスペースと EOF マーカーを削除します。

LZW は、すべての可能な文字 (記号) で事前に初期化された辞書、または事前に初期化された辞書のエミュレーションを使用する LZ78 ベースのアルゴリズムです。LZW の主な改善点は、一致するものが見つからない場合、現在の入力ストリーム文字が辞書内の既存の文字列の最初の文字であると想定されることです (辞書はすべての可能な文字で初期化されるため)。そのため、最後に一致するインデックスのみが出力されます (これは、前の (または最初の) 入力文字に対応する、事前に初期化された辞書のインデックスである可能性があります)。実装の詳細については、 LZW の記事を参照してください。

BTLZ は、リアルタイム通信システム (元々はモデム) で使用するために開発され、CCITT/ITU によってV.42bisとして標準化された LZ78 ベースのアルゴリズムです。トライ構造の辞書がいっぱいになると、辞書が変化するデータに適応し続けることができるように、単純な再利用/回復アルゴリズムが使用されます。カウンターが辞書内を循環します。新しいエントリが必要な場合、カウンターはリーフ ノード (従属ノードのないノード) が見つかるまで辞書内を移動します。リーフ ノードは削除され、そのスペースが新しいエントリ用に再利用されます。これは、LRU や LFU よりも実装が簡単で、同等のパフォーマンスを実現します。

• レンペル・ジヴ・スタック(LZS)

• ウィキメディア・コモンズの LZ77 アルゴリズムに関連するメディア
• ウィキメディア・コモンズの LZ78 アルゴリズムに関連するメディア
• 「LZ77 アルゴリズム」。データ圧縮リファレンス センター: RASIP ワーキング グループ。ザグレブ大学電気工学・コンピューティング学部。1997 年。2013 年 1 月 7 日時点のオリジナルからアーカイブ。2012年6 月 22 日閲覧。

• 「LZ78 アルゴリズム」。データ圧縮リファレンス センター: RASIP ワーキング グループ。ザグレブ大学電気工学・コンピューティング学部。1997 年。2013 年 1 月 7 日時点のオリジナルからアーカイブ。2012年6 月 22 日閲覧。

• 「LZW アルゴリズム」。データ圧縮リファレンス センター: RASIP ワーキング グループ。ザグレブ大学電気工学・コンピューティング学部。1997 年。2013 年 1 月 7 日時点のオリジナルからアーカイブ。2012年6 月 22 日閲覧。