ロスレスデータ圧縮アルゴリズム、パート2

パート1

データ圧縮技術

データ圧縮のために多くの手法が考案されています。 それらのほとんどは、いくつかの圧縮原理を組み合わせて完全なアルゴリズムを作成します。 良い原則でさえ、一緒に組み合わせると、最良の結果が得られます。 ほとんどの手法はエントロピーコーディングの原理を使用しますが、他の手法も一般的です-ランレングスエンコーディングとバロウズウィーラー変換。

シリーズ長コーディング（RLE）

これは非常に単純なアルゴリズムです。 2つ以上の同一の文字のシリーズを、シリーズの長さを示す数字に置き換え、その後にシンボル自体が続きます。 多数の同一ピクセルを持つ画像などの非常に冗長なデータ、またはBWTなどのアルゴリズムとの組み合わせに役立ちます。



簡単な例：



入口：AAABBCCCCDEEEEEEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA



出力：3A2B4C1D6E38A

バローズウィーラー変換（BWT）

1994年に発明されたアルゴリズムは、同一の文字の繰り返しを最大化するために、データブロックを可逆的に変換します。 彼自身はデータを圧縮しませんが、RLEまたは別の圧縮アルゴリズムを使用して、より効率的な圧縮のためにデータを準備します。



アルゴリズム：



-文字列の配列を作成する

-入力データ文字列の可能なすべての変換を作成し、それぞれが配列に格納されます

-配列を並べ替える

-最後の列を返します



このアルゴリズムは、大量の重複文字を含むビッグデータで最適に機能します。 適切なデータ配列で作業する例（＆はファイルの終わりを示します）







同一の文字を交互に使用するため、アルゴリズムの出力はRLE圧縮に最適であり、「3H＆3A」が得られます。 しかし、残念ながら、実際のデータでは、そのような最適な結果は通常得られません。

エントロピーコーディング

この場合のエントロピーとは、文字を表現するのに必要な平均ビット数の平均を意味します。 単純なECは、統計モデルとエンコーダー自体を組み合わせます。 入力ファイルを解析して、特定のキャラクターの出現確率で構成される統計モデルを構築します。 次に、エンコーダは、モデルを使用して、各文字に割り当てるビットまたはバイトエンコーディングを決定します。これにより、最も一般的なエンコーディングが最短エンコーディングで表現され、逆も同様です。

シャノン-Fanoアルゴリズム

最も初期の技術の1つ（1949）。 各文字の出現確率を表すバイナリツリーを作成します。 次に、最も一般的なものがツリーの最上部にあるように並べ替えられ、逆も同様です。



シンボルのコードは、ツリーを検索し、左か右かに応じて0または1を追加することにより取得されます。 たとえば、「A」へのパスは左に2つ、右に1つの分岐であり、コードは「110」になります。 アルゴリズムは、ツリーをボトムアップで構築するための方法論により、常に最適なコードを提供するとは限りません。 そのため、あらゆる入力に適したハフマンアルゴリズムが使用されるようになりました。







1.入力を解析し、すべての文字の出現回数をカウントします

2.それらのそれぞれの確率を決定する

3.出現確率で文字を並べ替える

4.リストを半分に分割し、左側の分岐の確率の合計が右側の合計にほぼ等しくなるようにします

5.左右のノードにそれぞれ0または1を追加します

6.各ノードが「リーフ」になるまで、右および左のサブツリーに対して手順4と5を繰り返します。

ハフマンコーディング

これは前のアルゴリズムと同様に機能するエントロピーコーディングの変形ですが、バイナリツリーは最適な結果を達成するために上から下に構築されます。



1. Parsim入力、文字の繰り返し数をカウントする

2.各キャラクターの出現確率を決定する

3.確率でリストを並べ替えます（最初に最も一般的）

4.各キャラクターのシートを作成し、キューに追加します

5.キューが複数の文字で構成されている場合：

-最も確率の低い2枚のシートをキューから取得します

-最初のコードに0を追加し、2番目のコードに1を追加します

-2つのノードの確率の合計に等しい確率でノードを作成します

-最初のノードを左側に、2番目のノードを右側に

-受信したノードをキューに追加します

6.キューの最後のノードがバイナリツリーのルートになります。

算術コーディング

メインフレームで使用するために1979年にIBMによって開発されました。 通常はハフマンの圧縮率よりも非常に高い圧縮率を実現しますが、以前の圧縮率と比較すると比較的複雑です。



確率をツリーに分割する代わりに、アルゴリズムは入力を0から1の単一の有理数に変換します。



一般的に、アルゴリズムは次のとおりです。



1.入力で一意の文字の数をカウントします。 この番号は、表記法bの基礎を表します（b = 2-バイナリなど）。

2.入力の全長を計算する

3. 0〜bの「コード」を、出現する順序で一意の各文字に割り当てます。

4.文字をコードに置き換え、ベースbの番号システムで番号を取得します

5.結果の数値をバイナリに変換します



例。 入力行「ABCDAABD」で



1. 4つの一意の文字、ベース= 4、データ長= 8

2.コードを割り当てます：A = 0、B = 1、C = 2、D = 3

3.数値「0.01230013」を取得します

4.「0.01231123」を4進数から2進数に変換：0.01101100000111



8ビット文字を扱っていると仮定すると、入力で8x8 = 64ビット、出力で15ビット、つまり圧縮率は24％になります。

アルゴリズム分類

スライディングウィンドウ法を使用したアルゴリズム

それはすべて、LZ77アルゴリズム（1977）で始まりました。このアルゴリズムは、「スライディングウィンドウ」という新しい概念を導入し、データ圧縮を大幅に改善しました。 LZ77は、オフセット、系列の長さ、および不一致記号のデータのトリプルを含む辞書を使用します。 オフセット-フレーズがファイルの先頭からどれくらい離れているか。 シリーズの長さ-オフセットから数えて、フレーズに属する文字数。 不一致記号は、この記号を除いて、オフセットと長さで示されるフレーズに類似した新しいフレーズが見つかったことを示します。 スライドウィンドウを使用してファイルが解析されると、辞書が変更されます。 たとえば、ウィンドウサイズを64 MBにすると、辞書には入力データの最後の64メガバイトのデータが含まれます。



たとえば、入力「abbadabba」の場合、結果は「abb（0,1、 'd'）（0,3、 'a'）」になります。







この場合、結果は入力よりも長くなりますが、通常はもちろん短くなります。

Lzr

1981年にマイケルロードによって提案されたLZ77アルゴリズムの修正。 LZ77とは異なり、線形時間で動作しますが、より多くのメモリが必要です。 通常、圧縮するとLZ78になります。

空気を抜く

1993年にPhil Katzによって発明され、現代のほとんどのアーカイバーによって使用されています。 これは、LZ77またはLZSSとハフマンコーディングの組み合わせです。

Deflate64

最大64 Kbの辞書拡張を備えた特許取得済みのDEFLATEバリエーション。 圧縮率が向上しますが、どこでも使用されません。 開いていません。

Lzss

Lempel-Ziv-Storere-Zimanskiアルゴリズムは1982年に導入されました。 LZ77の改良版。元のデータをエンコードされたデータで置き換えることにより、結果のサイズが増加するかどうかを計算します。



RARなどの一般的なアーカイバで引き続き使用されています。 時々-ネットワークを介した送信中にデータを圧縮します。

Lh

1987年に開発されたLempel-Ziv-Huffmanの略です。 LZSSのバリエーションで、ハフマンコーディングを使用してポインターを圧縮します。 圧縮は少し良くなりますが、かなり遅くなります。

Lzb

LZSSのオプションとして、1987年にTimothy Bellによって開発されました。 LZと同様に、LZBはポインターを効率的にエンコードすることにより、結果のファイルサイズを削減します。 これは、スライディングウィンドウのサイズを大きくしながら、ポインターのサイズを徐々に大きくすることで実現されます。 圧縮はLZSSおよびLZHよりも高くなりますが、速度ははるかに低くなります。

ロルツ

「Lempel-Ziv with offset」として復号化すると、オフセットを減らしてオフセットと長さのペアをエンコードするのに必要なデータ量を減らすことにより、LZ77アルゴリズムが改善されます。 1991年にRoss WilliamsのLZRW4アルゴリズムで初めて導入されました。 他のバリエーションは、BALZ、QUAD、およびRZMです。 最適化されたROLZは、LZMAとほぼ同じ圧縮率を達成しますが、人気はありません。

Lzp

「レンペルジブと予言。」 オフセット= 1のROLZバリエーション。いくつかのオプションがあり、圧縮速度を目的としたものもあれば、その程度のものもあります。 LZW4アルゴリズムは、最適な圧縮のために算術コーディングを使用します。

LZRW1

1991年にRon Williamsが開発したアルゴリズムで、彼は最初にオフセット削減の概念を導入しました。 適切な速度で高い圧縮率を実現します。 その後、ウィリアムズは、LZRW1-A、2、3、3-A、および4のバリエーションを作成しました

Lzjb

1998年のジェフボンウィック（したがって「JB」）のバリエーションで、Solaris Zファイルシステム（ZFS）ファイルシステムで使用するためのもの。 ファイルシステムの使用とディスク操作の速度に応じて、高速用に再設計されたLZRW1アルゴリズムの変形。

Lzs

Lempel-Ziv-Stac。1994年にStac Electronicsがディスク圧縮プログラムで使用するために開発しました。 文字と長さとオフセットのペアを区別するLZ77の変更に加えて、次に検出された文字を削除します。 LZSSに非常に似ています。

Lzx

1995年にAmigaのためにJ. ForbesとT. Potanenによって開発されました。 フォーブスは1996年にアルゴリズムをマイクロソフトに売却し、そこで仕事を得ました。その結果、改善されたバージョンがファイルCAB、CHM、WIM、およびXbox Liveアバターで使用されました。

ルゾ

1996年にMarcus Oberhumerによって設計され、圧縮と解凍の速度に注目しました。 圧縮レベルを調整でき、メモリをほとんど消費しません。 LZSSのように見えます。

LZMA

1998年に7-zipアーカイバに登場した「Lempel-Ziv Markov chain Algorithm」は、ほとんどすべてのアーカイバよりも優れた圧縮を実証しました。 このアルゴリズムは一連の圧縮方法を使用して、最高の結果を達成します。 最初に、ビットレベルで動作するわずかに変更されたLZ77が（バイトを処理する通常の方法とは異なり）データを解析します。 その出力には算術コーディングが適用されます。 その後、他のアルゴリズムを適用できます。 その結果、すべてのアーカイバの中で最高の圧縮が得られます。

LZMA2

2009年以降のLZMAの次のバージョンでは、マルチスレッドを使用し、非圧縮データをもう少し効率的に保存します。

Lempel-Ziv統計アルゴリズム

2001年に作成されたこの概念は、LZ77と組み合わせてデータの統計分析を提案し、辞書に保存されているコードを最適化します。

辞書アルゴリズム

Lz78

1978年のアルゴリズム、著者-LempelおよびZiv。 スライドウィンドウを使用して辞書を作成する代わりに、辞書はファイルからデータを解析してコンパイルされます。 辞書のサイズは通常、数メガバイトで測定されます。 このアルゴリズムのバリアントの違いは、辞書がいっぱいになったときにどうするかによって異なります。



ファイルを解析するとき、アルゴリズムはそれぞれの新しい文字またはそれらの組み合わせを辞書に追加します。 入力の各文字に対して、辞書フォームが出力に作成されます（インデックス+不明な文字）。 文字列の最初の文字が既に辞書にある場合、この文字列の部分文字列を辞書で探し、最も長い文字列を使用してインデックスを作成します。 インデックスが指すデータは、不明なサブストリングの最後の文字に追加されます。 現在の文字が見つからない場合、インデックスは0に設定され、これがディクショナリ内の単一文字の出現であることを示します。 エントリはリンクリストを形成します。



出力の入力「abbadabbaabaad」は「（0、a）（0、b）（2、a）（0、d）（1、b）（3、a）（6、d）」を与えます



「abbadabbaabaad」などの入力は、出力「（0、a）（0、b）（2、a）（0、d）（1、b）（3、a）（6、d）」を生成します。 これがどのように派生したかは、次の例で確認できます。

Lzw

Lempel-Ziv-Welch、1984年。 特許を取得しているにもかかわらず、LZ78の最も人気のあるバージョン。 アルゴリズムは出力の余分な文字を取り除き、データはポインターのみで構成されます。 また、圧縮前に辞書のすべての文字を保存し、他のトリックを使用して圧縮を改善します。たとえば、前のフレーズの最後の文字を次のフレーズの最初の文字としてエンコードします。 GIF、ZIPの初期バージョン、およびその他の特別なアプリケーションで使用されます。 非常に高速ですが、新しいアルゴリズムへの圧縮が失われます。

Lzc

Lempel-Zivの圧縮。 UNIXユーティリティで使用されるLZW変更。 圧縮率を監視し、指定された制限を超えるとすぐに、辞書は再びやり直されます。

Lzt

レンペルジブティッシャー。 辞書がいっぱいになると、使用頻度の低いフレーズがすべて削除され、新しいフレーズに置き換えられます。 人気を獲得していません。

Lzmw

ビクター・ミラーとマーク・ウェグマン、1984年。 LZTとして機能しますが、辞書の類似データではなく、最後の2つのフレーズを組み合わせます。 その結果、辞書はより速く成長し、めったに使用されないフレーズをより頻繁に取り除く必要があります。 また人気がありません。

Lzap

ジェームズ・ストアー、1988年。 LZMWの変更。 「AP」は「すべての接頭辞」を意味します-反復ごとに1つのフレーズを保存する代わりに、すべての変更が辞書に保存されます。 たとえば、最後のフレーズが「last」で、現在のフレーズが「next」の場合、「lastn」、「lastne」、「lastnex」、「lastnext」が辞書に保存されます。

Lzwl

単一の文字ではなく文字の組み合わせで動作するLZWの2006バージョン。 XMLなど、頻繁に繰り返される文字の組み合わせを含むデータセットで正常に動作します。 データを組み合わせに分割するプリプロセッサで一般的に使用されます。

Lzj

1985年、マティジェイコブソン。 LZWとは異なる数少ないLZ78バリアントの1つ。 すでに処理された入力データの各一意の行を保存し、それらすべてに一意のコードを割り当てます。 ディクショナリに記入すると、単一のオカレンスが削除されます。

非辞書アルゴリズム

PPM

部分一致予測-すでに処理されたデータを使用して、シーケンス内の次の文字を予測します。これにより、出力のエントロピーが削減されます。 通常、算術エンコーダーまたは適応型ハフマンコーディングと組み合わせます。 RARおよび7-zipで使用されるPPMdバリエーション

bzip2

BWTのオープンソース実装。 実装が容易であるため、速度と圧縮率の間の適切な妥協点を達成しているため、UNIXで人気があります。 最初に、データはRLE、次にBWTを使用して処理され、次にデータが特別な方法でソートされて同一の文字の長いシーケンスが取得され、その後RLEが再度適用されます。 そして最後に、ハフマンエンコーダーがプロセスを完了します。

PAQ

マット・マホニー、2002 PPMの改善（d）。 「コンテキストミキシング」と呼ばれる興味深い手法を使用して、それらを改善します。 この手法では、いくつかの予測アルゴリズムを組み合わせて、次のシンボルの予測を改善します。 現在、これは最も有望なアルゴリズムの1つです。 最初の実装以来、20個のオプションがすでに作成されており、その一部は圧縮レコードを設定します。 マイナス-いくつかのモデルを使用する必要があるため低速。 PAQ80と呼ばれるバリアントは64ビットをサポートし、速度の大幅な改善を示します（特にWindows用のPeaZipプログラムで使用）。