LZ77 – ウィキペディア

Posted on September 4, 2022 by lordneo

before-content-x4

LZ77 （Lempel-Ziv 77） ^[初め]1977年にAbraham LempelとJacob Zivによって公開されたデータ圧縮のロスレス手順です。
これは、データレコードでデータのシーケンス全体が数回発生するのを初めて活用する辞書ベースの手順です。以前の手順（Huffman CodingやShannon Fanoコーディングなど）では、個々の文字の頻度のみが使用されました（エントロピーコーディングも参照）。 LZ77も最初のLZプロセスになります LZ1 呼び出されました。

after-content-x4

キャラクターチェーンのLZ77因子化

{displaystyle x}

$x$ 空でない文字列チェーンへの分解です

{displaystyle w_ {1}、w_ {2}、ldots、w_ {k}}

$w_{1},w_{2},ldots ,w_{k}$ 、となることによって ^[2]

${displaystyle x = w_ {1} w_ {2} cdots w_ {k}}$
それぞれのため ${displaystyle w_ {j}}$

個々の文字列

{displaystyle w_ {j}}

$w_j$ なる要因また フレーズ 専用。

定義から直接導き出すことができます

after-content-x4

{displaystyle w_ {1} = x [1]}

$w_{1}=x[1]$ は。説明された

{displaystyle x [idots j]}

$x[idots j]$ キャラクターチェーン

{displaystyle x}

$x$ それは位置から

{displaystyle i}

$i$ すべての文字

{displaystyle x}

$x$ ポジションまでのものまで

{displaystyle j}

$j$ 含む。

{displaystyle x [i]}

$x[i]$ キャラクターチェーンの略語です

{displaystyle x [idots i]}

$x[idots i]$ 。

LZ77圧縮を計算するアルゴリズムのアイデアは、キャラクターチェーンのすでに処理されたプレフィックスを辞書として使用することです。実装のために、この辞書のサイズは、検索期間を制限するために実際には制限されています。したがって、通常はスライド窓です。 スライドウィンドウ ）使用され、考慮される辞書とテキストの抜粋の両方を制限します（プレビューバッファー）。圧縮文字は、プレビューバッファーから辞書に徐々に移動されます。実際には、辞書のバッファには数千文字が含まれており、ネックラインのプレビューバッファーには約100文字（場合によっては少ない場合があります）が含まれています。

アルゴリズムは、元のテキストを回復できる一連のトリプレットを作成します。要因のトリプル

{displaystyle w_ {j}}

$w_j$ 形があります

{displaystyle（pos、len、lambda）}

$(pos,len,lambda )$ 、それによって

辞書にバッファーを使用する場合、

{displaystyle pos}

$pos$ キャラクターチェーンは、バッファの左端または右端に比べて理解されます（実装によって異なる場合があります）、新しい文字を使用する必要があります

{displaystyle（0,0、lambda）}

$(0,0,lambda )$ 紹介されます。圧縮の出力形式により、辞書を明示的に保存せずにテキストを再構築できます。

Table of Contents

擬似コード [ 編集 | ソーステキストを編集します ]

擬似コードは、スライドウィンドウを使用したLZ77圧縮サルゴリズムの複製です。

 その間    プレビューバッファー  いいえ  ファイル  は ;  する  検索  r ü CKW ä RTS    の 彼 rterbuch  後    l ä 鼻  ü 一貫性のある  弦  と  に  プレビューバッファー ;  もしも  一  ü 参照  なりました  見つかった ;  それから  ギブ    トリプル  （ 子孫  のために  ランド  の  の 彼 rterbuch 、  l ä に    見つかった  弦 、  初め  いいえ  ü 一貫性のある  サイン  out  に  プレビューバッファー ））  out ;  延期    窓  一    l ä に + 初め ;  それ以外  ギブ    トリプル  （ 0 、  0 、  初め  サイン  の中に  プレビューバッファー ））  out ;  延期    窓  一  初め ;  終わり  もしも  終わり  その間

例 [ 編集 | ソーステキストを編集します ]

LZ77因数分解の計算は、キャラクターチェーンに基づいています AACTAの乱用 説明します。

この表は、長さ12の辞書と長さ10のプレビューバッファー（0から9のインデックス）を使用したLZ77因数分解の計算を示しています。
右の列では、アルゴリズムの出力（0、0、 a ）、（1、1、 c ）、（3、4、 b ）、（3、3、 a ）および（12、3、 終わり ）。
位置は辞書の右端に対して与えられます。これは、デコード時に同じ方法で行う必要があります。

バッファーは、移動ウィンドウの原則に従って動作します（英語： スライドウィンドウ ）、d。 H.圧縮されるデータストリームは、右からバッファーに押し込まれます。
アルゴリズムに記載されているように、シフトは、辞書の対応する一致の長さと別の位置の長さで行われます。これは、冗長なトリプルが回避されることを意味します。そうしないと、新しい文字は常に辞書で個別に採用されます。例では、3番目のトリプル（0、0、 c ）ただし、記録するには、圧縮率が大幅に悪化します。
マッチは緑色で、描画チェーンは赤で移動します。新しい文字をコーディングする必要がないために、契約で発見されたよりも常にサインが移動されることに注意する必要があります。

スライドウィンドウを使用したLZ77圧縮の例
ライン	12番目	11	十	9	8	7	6	5	4	3	2	初め	0	初め	2	3	4	5	6	7	8	9	出力
初め	ファイル												a	a	c	a	a	c	a	b	c	a	${displaystyle longrightarrow}$
2	ファイル											a	a	c	a	a	c	a	b	c	a	b	${displaystyle longrightarrow}$
3	ファイル									a	a	c	a	a	c	a	b	c	a	b	a	a	${displaystyle longrightarrow}$
4	ファイル				a	a	c	a	a	c	a	b	c	a	b	a	a	a	c	終わり			${displaystyle longrightarrow}$
5	a	a	c	a	a	c	a	b	c	a	b	a	a	a	c	終わり							${displaystyle longrightarrow}$
完了

最初に見られたキャラクターは不明なので、最初のキャラクター a （0、0、 a ）。
できる2行で a 辞書（マークグリーン）からすでに読むことができます。 c 新しいサインとして採用されています。
LZ77アルゴリズムの特殊なケースは、一致する文字列が予防ウィンドウに突き出ているため、3行目であるため、これは緑の赤のセルの色付けによって示されています。
4行目と5行目は最初の2つに相当しますが、最後のトリプル1では例外があります。 終わり – テキストが完全に圧縮されており、次のサインがないため、マークは次のサインとして紹介されます。

実行時間分析 [ 編集 | ソーステキストを編集します ]

アルゴリズムの持続時間は次のとおりです

{displaystyletheta（n）}

$Theta (n)$ テキストは圧縮中に1回のみ渡されるため、指定されています。これは、プレビューと辞書バッファのサイズが一定であり、全会一致のストリングチェーンの検索が大きなテキストでは重要ではない場合に可能です。実際に使用すると、通常の検索（追加のデータ構造なし）を使用した実装はかなり遅いです。

長所と短所 [ 編集 | ソーステキストを編集します ]

LZ77の大きな利点は、テキストの知識なしに圧縮できることであり、特許でも証明されていないことです。 LZ78（LZ77の直接の後継者）は、テキストの再構成のための初期辞書（主にすべてのアイコンが一度ソートされる些細な辞書）を必要とし、2004年まで特許によって部分的に保護されていました。
ただし、LZ77の主な欠点は、特に小規模または非自然な言語テキストの場合、またはデータの量を拡大する場合、非常に圧縮されることです。これは、指定された例で明らかになります。元のテキストには16文字が含まれており、圧縮には15文字が必要であるため、1つのサインの節約のみを意味します。 Burrows Wheelerの変換や前面への移動コードと同様に、他の圧縮方法を使用するために、それは前プロセッサとして非常に適しています。 B.ハフマンコーディングからデータを効果的に圧縮する。

LZ77圧縮ファイルの減圧は、一致するストライキチェーンの検索が行われないため、圧縮よりも大幅に簡単です。この用語は線形であり、元のテキストが長いほど多くのステップがあるので、

{displaystyletheta（n）}

$Theta (n)$ 。

擬似コード [ 編集 | ソーステキストを編集します ]

擬似コードは、スライドウィンドウを使用したLZ77減圧サルゴリズムの複製です。

 ために  毎日  トリプル  （ オフセット 、  長さ 、  シンボル ））  もしも  長さ  >  0 ;  それから  実行  r ü CKW ä RTS    前  出力  と  ギブ  に限って  サイン  out  それまで  一  l ä に  から  長さ  到達した  は 、  で  a  ü へそ  始める  新しい  で  オフセット ;  終わり  もしも  ギブ  シンボル  out ;  終わり  ために

例 [ 編集 | ソーステキストを編集します ]

LZ77コーディングの減圧には追加の辞書は必要ありません。発行されたトリプルは、テキストを再構築するために明確です。
赤い貯蔵細胞は、次の線の再構築に使用される細胞です。

スライドウィンドウを使用したLZ77減圧の例
ライン	入力	16	15	14	13	12番目	11	十	9	8	7	6	5	4	3	2	初め
初め	${displaystyle longrightarrow}$	ファイル															a
2	${displaystyle longrightarrow}$	ファイル													a	a	c
3	${displaystyle longrightarrow}$	ファイル								a	a	c	a	a	c	a	b
4	${displaystyle longrightarrow}$	ファイル				a	a	c	a	a	c	a	b	c	a	b	a
5	${displaystyle longrightarrow}$	a	a	c	a	a	c	a	b	c	a	b	a	a	a	c	終わり
完了

トリプルの最初のエントリが同じ0の場合、トリプルの最後のエントリがテキストに添付されます（1行目を参照）。
入力を使用した2行目（1、1、 c ）、1行目から再構築されたテキストの最初のエントリ（位置1のトリプルの最初のエントリと長さ1のトリプルの2番目のエントリ）
使用してからサイン c 後ろに添付されています。
3行目では、再使用された文字チェーンの長さは辞書の保存されたデータよりも長く（長さ4ですが、ストレージセル3から3つのセルのみが利用可能です）。 a 出力。そうなります b 処理するトリプルの最後のエントリとして。
4行目と5行目は同様に理解されるべきです。エンドサインは、テキストの終わりとしてグローバルに理解されるため、再構築では無視されます。
完全に再構築されたテキストはです AACTAの乱用 。

キャラクターチェーンのLZ77-factorizationのよりランタイム効率の計算のために、完全な文字列の因数分解を以下で計算し、スライドウィンドウの原理を放棄します。最後に、文字列全体のLZ77圧縮もいくつかのアプリケーションで使用されます（セクションを参照）。

追加のデータ構造の助けを借りて、用語に関しては、文字チェーンのLZ77因数分解の効率的な計算が可能です。
キャラクターチェーンの場合

{displaystyle x}

$x$ 指定

{displaystyleSa}

$SA$ 接尾辞アレイと

{displaystyle isa}

$ISA$ 逆の接尾辞車から

{displaystyle x}

$x$ 、d。 H.そうです

{displaystyle isa [i] = j}

$ISA[i]=j$ 正確にいつ

{displaystyle sa [j] = i}

$SA[j]=i$ 。また、説明してください

{displaystyle lcp（i、j）}

$lcp(i,j)$ 文字列チェーンの最も長い一般的な接頭辞の長さ

{displaystyle x [sa [i] .. n]}

$x[SA[i]..n]$ と

{displaystyle x [sa [j] .. n]}

$x[SA[j]..n]$ 、それによって

{displaystyle n = | x |}

$n=|x|$ は。

計算では、要因に対してそれを使用します

{displaystyle w_ {j}}

$w_j$ から

{displaystyle x}

$x$ と

{displaystyle | w_ {j} |> 1}

$|w_{j}|>1″></span>位置を決定するため <span class=$

{displaystyle pos}

$pos$ Tupelのみのテキスト位置のみ

{displaystyle sa [nsv [isa [j]]]}

$SA[NSV[ISA[j]]]$ と

{displaystyle sa [psv [isa [j]]}}

$SA[PSV[ISA[j]]]$ 考慮する必要があります。ある

{displaystyle nsv [j] = min {iin {j+1、ldots、n}、|、sa [i]

$NSV[j]=min{iin {j+1,ldots ,n},|,SA[i]<SA[j]}$ （NSVは略です 次の小さな値 ）と

{displaystyle psv [j] = max {iin {1、ldots、j-1}、|、sa [i]

${displaystyle PSV[j]=max{iin {1,ldots ,j-1},|,SA[i]<SA[j]}}$ （PSVは略です 以前の小さな値 ）。 ^[3]

擬似コード [ 編集 | ソーステキストを編集します ]

アルゴリズム lz_factor（i、psv、nsv） リターンとして、次の要因の開始位置が配信されます

 アルゴリズム  LZ_Factor （ 私 、  PSV 、  ソ連 ）） ：  もしも  LCP （ 私 、  PSV ））  >  LCP （ 私 、  ソ連 ）） ;  それから  （ Pos 、  それだけ ））  < -   （ PSV 、  LCP （ 私 、  PSV ）））  それ以外  （ Pos 、  それだけ ））  < -   （ ソ連 、  LCP （ 私 、  ソ連 ）））  終わり  もしも  もしも  それだけ  =  0 ;  それから  Pos  < -   私  終わり  もしも  もしも  私  +  それだけ  >  n ;  それから  印刷  要素 （ Pos 、  それだけ 、  '終わり' ））  それ以外  印刷  要素 （ Pos 、  それだけ 、  バツ [ 私 + それだけ ]））  終わり  もしも  戻る  私  +  マックス （ それだけ 、  初め ））

2つの配列

{displaystyle nsv}

$NSV$ と

{displaystyle psv}

$PSV$ 接尾辞マージンから缶

{displaystyleSa}

$SA$ 線形時間に計算：

 ために  私  < -   2  に  n + 初め ;  する  j  < -   私  -  初め  その間  定義されています （ j ））  と  の上 [ 私 ]  <  の上 [ j ] ;  する  ソ連 [ j ]  < -   私  j  < -   PSV [ j ]  終わり  その間  PSV [ 私 ]  < -   j  終わり  ために

最後に、アルゴリズムが続き、キャラクターチェーンのLZ77因数分解を計算します

{displaystyle x}

$x$

 計算します  の上 、  一 、  ソ連  と  PSV  f ü r  バツ  k  < -   初め  その間  k  <= =  n ;  する  PSV  < -   の上 [ PSV [ 一 [ k ]]]  ソ連  < -   の上 [ ソ連 [ 一 [ k ]]]  k  < -   LZ_Factor （ k 、  PSV 、  ソ連 ））  終わり  その間

実行時間分析 [ 編集 | ソーステキストを編集します ]

文字列のLZ77因数分解の計算は、アルゴリズムを使用しています

{displaystyle {mathcal {o}}（n）}

${mathcal {O}}(n)$ 可能な時間、それによって

{displaystyle n = | x |}

$n=|x|$ 入力記号チェーンの長さ

{displaystyle x}

$x$ は。
メソッドLZ_Factorが必要です

{displaystyle {mathcal {o}}（1）}

${mathcal {O}}(1)$ の計算の時間

{displaystyle lcp（i、j）}

$lcp(i,j)$ 範囲の最小クエリを介して実現されます。配列の計算

{displaystyle nsv}

$NSV$ と

{displaystyle psv}

$PSV$ 入っています

{displaystyle {mathcal {o}}（n）}

${mathcal {O}}(n)$ 計算のためのアルゴリズム全体が可能な時間

{displaystyle {mathcal {o}}（n）}

${mathcal {O}}(n)$ 時間が必要です（これには、接尾辞アレイの線形時間構造が必要です）。 ^[3]

用語とメモリ要件が異なる文字列のLZ77圧縮を計算するためのさまざまな実装があります。比較のために、完全な文字チェーンのLZ因数分解は

{displaystyle x}

$x$ 長さで

{displaystyle | x | = n}

$|x|=n$ 見た。メモリ要件の分析は、32または64ビットの単語のストレージに基づいています。アルファベットの文字

{displaystyle sigma}

$Sigma$ メモリワードの4分の1と整数全体のメモリワード。 ^[2]

次の表には、LZ77因数分解をその期間、そのストレージ要件、および使用したデータ構造を計算するためのいくつかの実装があります。

表にリストされているアルゴリズムのいくつかは、LPFアレイを使用しています（LPFは 最長の以前の要因 ）。 LPFアレイは次のように定義されています。 ^[2]すべての位置について

{displaystyle i}

$i$ キャラクターチェーンの

{displaystyle x}

$x$ は

{displaystyle lpf [i]}

$LPF[i]$ の最長係数の長さとして定義されています

{displaystyle x}

$x$ それは位置にあります

{displaystyle i}

$i$ 始まり、ポジションの前に

{displaystyle i}

$i$ の

{displaystyle x}

$x$ 登場した、d。 H.

{displaystyle lpf [i] = max（{0} cup {l、|、x [idots i+l-1] {text {ist ein fake fake von}} x [1dots i+l-2]}}}}

$LPF[i]=max({0}cup {l,|,x[idots i+l-1]{text{ ist ein Faktor von }}x[1dots i+l-2]})$ 。 LPFアレイは、線形時間に文字チェーンのLZ77因数分解から計算できます。
LPFアレイは、とりわけ、上記のNSVおよびPSVアレイを使用して計算できます。 ^[3]

{displaystyle lpf [i] = max（lcp（i、sa [nsv [i]]）、lcp（i、sa [psv [i]]）}）}）}

$LPF[i]=max(lcp(i,SA[NSV[ISA[i]]]),lcp(i,SA[PSV[ISA[i]]]))$

テーブルにリストされているいくつかのアルゴリズムの実装のために

{displaystyleS}

$S$ 追加のメモリが必要です。テーブルでは、スタックの使用がメモリ要件に取り付けられています

{displaystyle +}

$+$ 表示されています。スタックメモリのサイズは制限されます

{displaystyle | s | = n}

$|S|=n$ – これは、文字列が形状をチェーンする場合に当てはまります

{displaystyle x = alpha ^{n}}

$x=alpha ^{n}$ と

{sigmaのdisplaystyle alpha}

$alpha in Sigma$ 持っている。期待されています

{displaystyle | s | in o（log _ {| sigma |} n）}

$|S|in O(log _{{|Sigma |}}n)$ 。 ^[2]

今日、LZ77圧縮とa。 Game Boy Advance、AutoCAD DWG形式、その他の組み込みシステムでまだ使用されています。 Huffman Codingと組み合わせて、LZ77は非常によく知られた圧縮プログラムとグラフィック形式PNGで使用される、非常に使用されているDERGLATEアルゴリズムで使用されます。 LZ77が特許で証明されていないという事実は、1年後に公開された後継LZ78よりもプロセスがまだ好まれている理由であるはずです。

文字鎖のアルゴリズム処理では、LZ77-factorizationが文字列の規則性の計算に使用されます。因数分解は、スライドウィンドウ内だけでなく、文字列全体で常に考慮されます。さらに、元の文字列がアプリケーションで使用可能であり、再構築する必要がないため、出力を簡素化できます。 LZ77因数分解を使用できる問題の選択は、次のリストに記載されています。

圧縮品質は、辞書のサイズに直接依存します。したがって、良好な圧縮速度を取得するためには、スライディングウィンドウは一定の最小サイズを達成する必要があります。アルゴリズムで圧縮されるテキストは、レキシコンの各エントリ（セクションアルゴリズムを参照）と比較する必要があるため、圧縮に必要な時間は、ウィンドウのサイズが直線的に増加します。したがって、純粋な形のLZ77アルゴリズムは、最初はほとんど注目されませんでした。 James StorerとThomas Szymanskiは、1982年に現在Lempel-Ziv-Storer-Szymanski（LZSS）と呼ばれるアルゴリズムでいくつかの問題を改善しました。
レキシコンのすべてのエントリと圧縮されるテキストの比較は、効率的な構築のためのセクションのように効率的な実装には適用されません。

オフセットレンペルZIVの減少（ロルツも Lempel Ziv Ross Williams 、ロス・ウィリアムズ、1991年）およびLempel-Ziv-Markow-Algorithm（LZMA、Igor Pavlov、1998）、彼はより有名で現代の後継者を見つけました。

LZ77 – ウィキペディア

擬似コード [ 編集 | ソーステキストを編集します ]

例 [ 編集 | ソーステキストを編集します ]

実行時間分析 [ 編集 | ソーステキストを編集します ]

長所と短所 [ 編集 | ソーステキストを編集します ]

擬似コード [ 編集 | ソーステキストを編集します ]

例 [ 編集 | ソーステキストを編集します ]

擬似コード [ 編集 | ソーステキストを編集します ]

実行時間分析 [ 編集 | ソーステキストを編集します ]

関連するアルゴリズム [ 編集 | ソーステキストを編集します ]

Recent Posts

Recent Comments

Archives

Categories

Meta