Loading article…
LZ77とLZ78は、 1977年[ 1 ]と1978年[ 2 ]にAbraham LempelとJacob Zivによって発表された2つの可逆データ圧縮アルゴリズムです。 これらはそれぞれLempel-Ziv 1（LZ1）とLempel-Ziv 2 （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 ]）。
LZ78は普遍的でエントロピー的である—もし定常かつエルゴード的なバイナリソースである場合、確率1で。これは、情報源のエントロピー率です。
同様の定理は、LZアルゴリズムの他のバージョンにも適用される。
LZ77アルゴリズムは、データの繰り返し出現箇所を、非圧縮データストリーム内で既に存在するそのデータの単一コピーへの参照に置き換えることで圧縮を実現します。一致は、長さと距離のペアと呼ばれる2つの数値によって符号化されます。これは、「次の長さの各文字は、非圧縮ストリーム内でその文字からちょうど距離だけ後ろにある文字と等しい」という記述に相当します。（距離はオフセットと呼ばれることもあります。）
一致する箇所を検出するために、エンコーダは直近のデータの一部（例えば、最後の2KB 、 4KB 、または32KB）を追跡する必要があります。このデータを保持する構造はスライディングウィンドウと呼ばれ、そのため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 l := 0 c := 入力の最初の文字 endif出力（d、l、c） ウィンドウの先頭からl + 1 文字 を破棄する s :=入力の先頭からl + 1 文字をポップする ウィンドウの背面にsを追加する 繰り返す
LZ77アルゴリズムはすべて定義上同じ基本原理に基づいて動作しますが、圧縮データのエンコード方法によって長さと距離のペアの数値範囲を変更したり、長さと距離のペアに消費されるビット数を変更したり、長さと距離のペアをリテラル（長さと距離のペアの一部としてではなく、それ自体としてエンコードされた生データ）と区別したりする方法が大きく異なります。いくつかの例を挙げます。
LZ78 アルゴリズムは、入力からトークン シーケンスの辞書を作成し、データ ストリーム内のシーケンスの 2 回目以降の出現を辞書エントリへの参照に置き換えることで、シーケンス データを圧縮します。繰り返しシーケンスの数は、シーケンスの非ランダム性の良い尺度であることがわかります。アルゴリズムは、辞書をn進木として表現します。ここで、nはトークン シーケンスを形成するために使用されるトークンの数です。各辞書エントリは の形式です。dictionary[...] = {index, token}ここで、indexは以前に見られたシーケンスを表す辞書エントリのインデックスであり、 はtoken入力からこのエントリを辞書内で一意にする次のトークンです。アルゴリズムが貪欲であるため、一意にするトークンが見つかるまでテーブルに何も追加されないことに注意してください。アルゴリズムは、最後に一致したインデックスを 0、次に使用可能なインデックスを 1 に初期化し、入力ストリームの各トークンに対して、辞書で一致を検索します。{last matching index, token}一致が見つかった場合、最後に一致したインデックスは一致したエントリのインデックスに設定され、何も出力されず、最後に一致したインデックスは、これまでの入力を表すままになります。入力は一致するものが見つからないまで処理されます。その後、新しい辞書エントリが作成され、dictionary[next available index] = {last matching index, token}アルゴリズムは最後に一致したインデックス、続いてトークンを出力し、最後に一致したインデックスを 0 にリセットして、次に使用可能なインデックスをインクリメントします。例として、トークンのシーケンスを考えてみましょう。AABBA辞書を組み立てるもの。
0 {0,_} 1 {0,A} 2 {1,B} 3 {0,B} 圧縮データの出力シーケンスは次のようになります。0A1B0B最後のAアルゴリズムは次に何が来るか分からないため、まだ表現されていません。実際には、入力にEOFマーカーが追加されます。AABBA$例えば、この場合の出力も0A1B0B1$元の入力よりも長くなりますが、辞書が大きくなるにつれて圧縮率が大幅に向上し、バイナリではインデックスは最小限のビット数で表現するだけで済みます。[ 11 ]
解凍とは、圧縮されたシーケンスから辞書を再構築することです。0A1B0B1$最初のエントリは常に終端文字です0 {...}、そしてシーケンスの最初のものは1 {0,A}.Aが出力に追加されます。入力からの2番目のペアは1Bそして辞書の2番目の項目として、{1,B}トークンBが出力され、その前に辞書エントリ 1 で表されるシーケンスが続きます。エントリ 1 はA(エントリ 0 – 何も続かない) なのでAB出力に追加されます。次へ0B次のエントリとして辞書に追加されます。3 {0,B}、そしてB（何も前に付かない）が出力に追加されます。最後に、の辞書エントリが追加されます。1ドル作成され、オーストラリアドル出力結果A AB BA$、 またはAABBAスペースとEOFマーカーを削除します。
LZWは、LZ78をベースとしたアルゴリズムで、すべての可能な文字（記号）で事前に初期化された辞書、または事前に初期化された辞書のエミュレーションを使用します。LZWの主な改良点は、一致する文字が見つからない場合、現在の入力ストリームの文字は、辞書内の既存の文字列の最初の文字であると想定されることです（辞書はすべての可能な文字で初期化されているため）。そのため、最後に一致したインデックスのみが出力されます（これは、前の（または最初の）入力文字に対応する、事前に初期化された辞書のインデックスである可能性があります）。実装の詳細については、LZWの記事を参照してください。
BTLZは、リアルタイム通信システム（元々はモデム）で使用するために開発され、CCITT/ITUによってV.42bisとして標準化されたLZ78ベースのアルゴリズムです。トライ構造の辞書がいっぱいになると、辞書が変化するデータに適応し続けることができるように、単純な再利用/回復アルゴリズムが使用されます。カウンタが辞書を巡回します。新しいエントリが必要な場合、カウンタはリーフノード（依存ノードを持たないノード）が見つかるまで辞書を順にたどります。リーフノードは削除され、その領域は新しいエントリのために再利用されます。これはLRUやLFUよりも実装が簡単で、同等のパフォーマンスを実現します。
ウィキメディア・コモンズにあるLZ77アルゴリズム関連のメディアウィキメディア・コモンズにあるLZ78アルゴリズム関連のメディア{{cite web}}: CS1メンテナンス: アーカイブサービスは非推奨になりました (リンク){{cite web}}: CS1メンテナンス: アーカイブサービスは非推奨になりました (リンク){{cite web}}: CS1メンテナンス: アーカイブサービスは非推奨になりました (リンク)