davirain

引言

歴史

• 法律問題
• 緊縮政策の興隆

現在のアーカイブソフトウェア

未来の発展

圧縮技術

• Run-Length Encoding ランレングスエンコーディング
• Burrow-Length Transform バーロウズ - ウィーラー変換
• Entropy Encoding エントロピー符号化
  • Shannon-Fano Coding シャノン - ファノ符号化
  • Coding 算術符号化

圧縮アルゴリズム

• Sliding Window Algorithm スライディングウィンドウアルゴリズム
  • LZ77
  • LZR
  • DEFLATE
  • DEFLATE64
  • LZSS
  • LZH
  • LZB
  • ROLZ
  • LZP
  • LZRW11
  • LZJB
  • LZS
  • LZX
  • LZO
  • LZMA
  • LZMA2

Dictionary Algorithm 辞書アルゴリズム

• LZ78
• LZW
• ZLC
• LZTL
• ZMW
• LZAP
• LZWL
• LZJ

Non-dictionary Algorithm 非辞書アルゴリズム

• PPM
• bzip2
• PAQ

参考資料

1 はじめに#

圧縮アルゴリズムには主に 2 つの大きなカテゴリがあります： 有損と無損。有損データ圧縮アルゴリズムは、ファイルサイズを削減するために多くの忠実度データを必要とする小さな詳細を削除することによって行われます。有損データ圧縮では、基本データが削除されるため、元のファイルを復元することは不可能です。有損データ圧縮は通常、画像や音声データの保存に使用されますが、データの削除によって非常に高い圧縮比を実現できることがありますが、この記事では扱いません。無損データ圧縮は、ファイルのサイズを減少させるもので、解凍関数によって元のファイルを完全に復元でき、データの損失がありません。無損データ圧縮は、個人用コンピュータのスペースを節約することから、ネットワークを介してデータを送信すること、セキュアシェルを介して通信すること、または PNG や GIF 画像を表示することまで、コンピュータのあらゆるところに存在します。

無損データ圧縮アルゴリズムの動作原理は、非ランダムなファイルには繰り返し情報が含まれており、これらの情報は統計モデル技術を使用して濃縮され、文字やフレーズの出現確率を特定することができるというものです。これらの統計モデルを使用して、特定の文字やフレーズの発生確率に基づいてコードを生成し、最も一般的なデータに最短のコードを割り当てることができます。これらの技術には、エントロピー符号化、ランレングスエンコーディング、および辞書を使用した圧縮が含まれます。これらの技術や他の技術を使用することで、8 ビット文字またはその文字の文字列を数ビットで表現でき、大量の冗長データを削除できます。

2 歴史#

1970 年代、インターネットがますます普及し、レンプル - ジブアルゴリズムが発明され、そこからデータ圧縮がコンピュータ分野で重要な役割を果たすようになりました。しかし、コンピュータの外での歴史ははるかに古いものです。モールス信号は 1838 年に発明され、データ圧縮の最初の例とされています。なぜなら、英語で最も一般的な文字である 'e' や 't' に短いモールス信号が割り当てられたからです。その後、1949 年に大型コンピュータが主導権を握り始めると、クロード・シャノンとロバート・ファノがシャノン - ファノ符号化を発明しました。彼らのアルゴリズムは、出現確率に基づいて、与えられたデータブロック内のシンボルにコードを割り当てます。シンボルの出現確率はコードの長さに反比例するため、データを短い方法で表現します。[1]

2 年後、デビッド・ハフマンはマサチューセッツ工科大学で情報理論を学び、ロバート・ファノと一緒に授業を受けました。ファノは学生に学期論文を書くか期末試験を受けるかを選ばせました。ハフマンは学期論文を選び、その論文は最も効率的な二進法符号化方法を見つけることについてでした。数ヶ月間働いても何も得られなかった後、ハフマンはすべての作業を捨て、期末試験のために勉強を始めることにしました。その時、突然ひらめき、シャノン - ファノ符号化に非常に似ているが、より効率的なカウントを発見しました。シャノン - ファノ符号化とハフマン符号化の主な違いは、前者の確率ツリーが下から上に構築され、生成される結果が最適でないのに対し、後者は上から下に構築されることです。[2]

シャノン - ファノとハフマン符号化の初期の実装は、すべてハードウェアとハードウェア符号化を使用して行われました。1970 年代まで、インターネットとオンラインストレージの出現に伴い、ソフトウェア圧縮が実現しました。ハフマン符号化は、入力データに基づいて動的に生成されました [1]。その後、1997 年にアブラハム・レンプルとヤコブ・ジブが彼らの画期的な LZ77 アルゴリズムを発表しました。これは辞書データを使用する最初のアルゴリズムです。より具体的には、LZ77 はスライディングウィンドウと呼ばれる動的辞書を頻繁に使用します。[3] 1978 年、同じ 2 人が LZ78 アルゴリズムを発表しました。このアルゴリズムも辞書を使用しましたが、LZ77 とは異なり、入力データを解析し、動的に生成するのではなく、静的辞書を生成しました。[4]

2.1 法律問題#

LZ77 および LZ78 アルゴリズムは急速に普及し、図に示すように多くの変種を生み出しました。

これらのアルゴリズムが発明されて以来、大多数のアルゴリズムは消滅し、現在では DEFLATE、LZMA、LZX を含む少数のアルゴリズムのみが広く使用されています。一般的に使用されるアルゴリズムのほとんどは LZ77 アルゴリズムから派生しています。これは技術的な優位性によるものではなく、LZ78 アルゴリズムが 1984 年にスパリーによって派生物 LZW アルゴリズムの特許を申請し、ソフトウェア供給業者、サーバー管理者、さらにはライセンスなしで GIF 形式を使用する端末を訴え始めたためです。その後、特許制限アルゴリズムとなりました [5][6]

当時、UNIX 圧縮ユーティリティは LZW アルゴリズムに非常に小さな変更を加えた LZC を使用していましたが、後に特許問題のために使用が停止されました。他の UNIX 開発者も LZW アルゴリズムの使用を避け、オープンソースアルゴリズムに切り替え始めました。これにより、UNIX コミュニティは deflate ベースの gzip と Burrows-Wheeler 変換に基づく bzip2 形式を採用しました。長期的には、これは UNIX コミュニティにとって利益となりました。なぜなら、gzip と bzip2 はほぼ常に LZW 形式よりも高い圧縮比を実現するからです。LZW アルゴリズムの特許が 2003 年に期限切れになったことで、LZW に関する特許問題は収束しました [5]。それにもかかわらず、LZW アルゴリズムは大部分のプログラムで置き換えられ、GIF 圧縮で一般的に使用されるのみとなりました。その後、いくつかの LZW 派生品も登場しましたが、広く使用されることはありませんでした。LZ77 アルゴリズムは依然として主導的な地位を占めています。

LZS アルゴリズムに関する別の法律戦争は 1993 年に勃発し、Stac Electronics 社がディスク圧縮ソフトウェア、例えば Stacker のために開発しました。マイクロソフトは LZS アルゴリズムを使用してディスク圧縮ソフトウェアを開発し、このソフトウェアは MS-DOS 6.0 でリリースされました。ディスクの容量を 2 倍にすることができると言われています。Stac Electronics がその知的財産が使用されていることに気づいたとき、彼はマイクロソフトを訴えました。マイクロソフトは後に有罪判決を受け、Stac Electronics に対して 1.2 億ドルの損害賠償を支払うよう命じられました。反訴の判決を差し引くと、マイクロソフトの侵害は推定されませんでした [7]。Stac Electronics がマイクロソフトを訴えた事件は大きな判決を得ましたが、LZW 特許紛争のようにレンプル - ジブアルゴリズムの発展を妨げることはありませんでした。唯一の結果は、LZS が新しいアルゴリズムに割り当てられなかったことのようです。

2.2 DEFLATE の台頭#

レンプル - ジブアルゴリズムが発表されて以来、企業や他の大規模な組織はデータ圧縮を使用してきました。なぜなら、彼らのストレージニーズが増加し、データ圧縮がそれらのニーズを満たすのに役立つからです。しかし、インターネットが台頭し始めるまで、データ圧縮は広く使用されることはありませんでした。1980 年代末にはデータ圧縮の需要が高まりました。帯域幅は制限されているか高価であり、データ圧縮はこれらのボトルネックを緩和するのに役立ちました。ワールドワイドウェブが開発されると、圧縮は特に重要になりました。なぜなら、人々はより多くの画像や他のフォーマットを共有し始め、これらのフォーマットはテキストよりもはるかに大きいからです。需要を満たすために、ZIP、GIF、PNG などの新しいファイル形式がいくつか開発され、圧縮技術が含まれています。

1985 年、トム・ヘンダーソンは彼の会社 System Enhancement Associates を通じて最初の商業的に成功したアーカイブ形式 ARC を発表しました。ARC はファイルをパッケージ化し圧縮することができる最初のプログラムの 1 つであるため、BBS コミュニティで特に人気があり、オープンソースでもありました。ARC 形式は LZW アルゴリズムの修正版を使用してデータを圧縮します。フィル・カッツは ARC の人気に気づき、アセンブリ言語を使用して圧縮および解凍プログラムを作成することを決定しました。彼は 1987 年に PKARC プログラムを共有ソフトウェアとしてリリースしましたが、著作権侵害でヘンダーソンに訴えられました。彼は有罪判決を受け、ロイヤリティやその他の罰金を支払うことを余儀なくされ、クロスライセンス契約の一部として支払いました。彼は PKARC が ARC の明らかなコピーであるため有罪判決を受けました。場合によっては、注釈のスペルミスさえも同じでした。[8]

クロスライセンス契約の制約により、フィル・カッツは 1988 年以降 PKARC を販売できなくなりました。したがって、彼は 1989 年に調整された PKARC バージョンを作成し、現在は ZIP 形式と呼ばれています。LZW を使用しているため、特許制限があると見なされ、後にカッツは新しい IMPLODE アルゴリズムに切り替えることを選択しました。1993 年、カッツは PKZIP 2.0 をリリースし、DEFLATE アルゴリズムやボリュームの分割などの他の機能を実装しました。すでに長い時間が経過していますが、今日ほぼすべての.zip ファイルは PKZIP 2.0 形式に従っているため、この ZIP 形式のバージョンは至る所に存在します。

GIF、すなわち Graphics Interchange Format は、1987 年に CompuServe によって開発されたグラフィックス交換形式であり、ビットマップが転送中にデータを失わないようにすることを目的としています（ただし、この形式は各フレームで 256 色に制限されています）。同時に、ダイヤルアップモデムで転送するためにファイルサイズを大幅に削減します。しかし、ZIP 形式と同様に、GIF も LZW アルゴリズムに基づいています。特許制限があるにもかかわらず、ユニシスはこの形式の普及を阻止するために特許を十分に行使しませんでした。20 年以上後でも、GIF は広く使用され続け、特にアニメーションを作成できるため人気があります。[9]

GIF が阻止されることはありませんでしたが、CompuServe は特許制限のない形式を求め、1994 年に Portable Network Graphics（PNG）形式を発表しました。ZIP と同様に、PNG 標準は圧縮に DEFLATE アルゴリズムを使用します。DEFLATE はカッツによって特許を取得されていますが [10]、この特許は決して行使されなかったため、PNG や他の DEFLATE ベースの形式は特許侵害を回避しました。LZW は圧縮の初期に広く採用されましたが、ユニシスの訴訟の性質により、歴史の舞台から徐々に退場し、より高速で効率的な DEFLATE アルゴリズムに取って代わられました。DEFLATE は現在最も一般的なデータ圧縮アルゴリズムであり、圧縮におけるスイスアーミーナイフのような存在です。

PNG や ZIP 形式で DEFLATE が使用されるだけでなく、DEFLATE はコンピュータ分野の他の場所でも非常に一般的です。たとえば、gzip（.gz）ファイル形式は DEFLATE を使用しています。なぜなら、これは本質的に ZIP のオープンソース版だからです。DEFLATE の他の用途には、HTTP、SSL、およびネットワーク上で効率的なデータ圧縮を実現することを目的とした他の技術が含まれます。

残念ながら、フィル・カッツは彼の DEFLATE アルゴリズムがコンピュータの世界を征服するのを生きて見ることはありませんでした。彼は何年もアルコール依存症に苦しみ、1990 年代末には彼の生活が崩壊し始め、飲酒運転や他の違反行為で何度も逮捕されました。2000 年 4 月 14 日、37 歳のカッツはホテルの部屋で死亡しているのが発見されました。死因は急性膵臓出血で、彼の遺体のそばには多くの空の酒瓶が見つかりました。[11]

2.3 現在のアーカイブソフトウェア#

1990 年代中頃には、新しいより良い形式が登場し、ZIP 形式や他の DEFLATE ベースの形式はもはや主導的な地位を占めていませんでした。1993 年、ユージン・ロシャルは彼の圧縮ソフトウェア WinRAR を発表し、独自の RAR 形式を使用しました。RAR の最新バージョンは PPM と LZSS アルゴリズムの組み合わせを使用していますが、より早い実装状況は知られていません。RAR はインターネット上でファイルを共有する標準形式となり、特に海賊版メディアの配布において人気があります。bzip2 という名前のオープンソースのバーロウズ - ウィーラー変換の実装が 1996 年に発表され、UNIX プラットフォーム上で DEFLATE ベースの gzip 形式に大きな競争をもたらしました。もう一つのオープンソース圧縮プログラムは 1999 年にリリースされ、7-Zip または.7z 形式です。通常、7-Zip は高い圧縮比と形式のモジュール性およびオープン性により、ZIP や RAR の主導的地位に挑戦する最初の形式かもしれません。この形式は、単一の圧縮アルゴリズムを使用するのではなく、bzip2、LZMA、LZMA2、PPMd などのアルゴリズムの間で選択できます。最後に、アーカイブソフトウェアの最前線には PAQ * 形式があります。最初の PAQ 形式は 2002 年にマット・マホニーによって発表され、PAQ1 と呼ばれています。PAQ は、コンテキストミキシングと呼ばれる技術を使用して、2 つ以上の統計モデルを組み合わせることにより、PPM アルゴリズムを大幅に改善し、単一のモデルが次のシンボルを予測するよりも優れた予測を生成します。

3 未来の発展#

未来は常に不確実ですが、現在の傾向に基づいてデータ圧縮の未来についていくつかの予測を行うことができます。PAQ およびその変種のコンテキストミキシングアルゴリズムが人気を集め始めており、通常は最高の圧縮比を実現できますが、速度は通常遅いです。ハードウェアの速度が指数関数的に増加し、ムーアの法則に従う中で、コンテキストミキシングアルゴリズムは高圧縮比の状況で大きな成功を収める可能性が高いです。なぜなら、速度のペナルティはより高速なハードウェアによって克服されるからです。PAQ は改良された予測部分一致（PPM）アルゴリズムを改善する新しい変種も登場する可能性があります。最後に、レンプル - ジブマルコフ連鎖アルゴリズム（LZMA）は、優れた速度と高圧縮比のバランスを示しており、さらに多くの変種を生み出す可能性があります。LZMA は 7-Zip 形式で導入されて以来、競合する多くの圧縮形式で広く採用されており、「勝者」となる可能性すらあります。もう一つの潜在的な発展方向は、部分列列挙圧縮（CSE）の使用です。これは新興の圧縮技術であり、まだ多くのソフトウェア実装が見られません。その素朴な形式では、bzip2 や PPM に似たパフォーマンスを示し、研究者たちはその効率を向上させるために努力しています。[12]

4 圧縮技術#

データを圧縮するために多くの異なる技術が使用されます。ほとんどの圧縮技術は独立して存在することはできず、圧縮アルゴリズムを形成するために組み合わせる必要があります。独立して存在できる圧縮技術は、他の圧縮技術と組み合わせると、通常はより効果的です。これらの技術のほとんどはエントロピーエンコーダに属しますが、ランレングスエンコーディングやバーロウズ - ウィーラー変換などの他の一般的な技術もあります。

4.1 ランレングスエンコーディング#

ランレングスエンコーディングは非常にシンプルな圧縮技術で、同じ文字の連続出現回数を数字で表し、その後にその文字を続けます；単一の文字は 1 回の連続出現としてエンコードされます。RLE は、高度に冗長なデータ、同じ色のピクセル行のインデックス画像、または他の圧縮技術（バーロウズ - ウィーラー変換など）と組み合わせて使用するのに非常に便利です。

以下は RLE の簡単な例です：

入力：AAABBCCCCDEEEEEEAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

出力：3A2B4C1D6E38A

4.2 バーロウズ - ウィーラー変換#

バーロウズ - ウィーラー変換は 1994 年に発明された圧縮技術で、入力データブロックを可逆的に変換し、同じ文字の繰り返し出現数を最大化することを目的としています。BWT 自体は圧縮操作を実行せず、入力をランレングスエンコーダや他の二次圧縮技術でより効率的にエンコードできる形式に変換するだけです。

BWT のアルゴリズムは非常にシンプルです：

1. 文字列配列を作成します。
2. 入力文字列のすべての可能な回転を生成し、各回転を配列に保存します。
3. 配列を辞書順でソートします。
4. 配列の最後の列を返します。[13]

BWT は、同じ文字が交互に多く出現する長い入力で最も効果的です。以下は理想的な入力でこのアルゴリズムを実行した例です。注意してください、＆はファイル終了文字です：

その交互に同じ文字のため、この入力に BWT を実行すると最適な結果が得られ、他のアルゴリズムがさらに圧縮することができます。例えば RLE は「3H＆3A」を生成します。この例は最適な結果を生成しましたが、ほとんどの実際のデータでは最適な結果を生成しません。

4.3 エントロピー符号化#

データ圧縮におけるエントロピーは、シンボルまたは文字を表現するのに必要な平均最小ビット数を指します。基本的なエントロピーエンコーダは、統計モデルとエンコーダを組み合わせたものです。入力ファイルは解析され、統計モデルを生成するために使用されます。このモデルは、与えられたシンボルの出現確率で構成されます。次に、エンコーダは統計モデルを使用して、各シンボルにどのビットまたはバイトコードを割り当てるかを決定し、最も一般的なシンボルには最短のコードを、最も一般的でないシンボルには最長のコードを割り当てます。

4.3.1 シャノン - ファノ符号化#

これは最も初期の圧縮技術の一つで、クロード・シャノンとロバート・ファノによって 1949 年に発明されました。この技術は、各シンボルの出現確率を表す二分木を生成することを含みます。これらのシンボルは、最も一般的なシンボルが木の上部に、最も出現しにくいシンボルが下部に来るように並べ替えられます。

与えられたシンボルの符号化は、シャノン - ファノ木の中でそのシンボルを検索し、各左または右の分岐の値（0 または 1）を追加することによって取得されます。例えば、「A」が 2 つの左分岐と 1 つの右分岐である場合、その符号化は「0012」となります。下から上に二分木を構築する方法のため、シャノン - ファノ符号化は常に最適なコードを生成するわけではありません。したがって、通常はハフマン符号化が使用されます。なぜなら、ハフマン符号化は任意の与えられた入力に対して最適なコードを生成できるからです。

シャノン - ファノ符号化を生成するアルゴリズムは非常にシンプルです：

1. 入力を解析し、各シンボルの出現回数を計算します。
2. シンボルのカウントを使用して、各シンボルの確率を決定します。
3. 確率に基づいてシンボルを並べ替え、最も可能性の高いシンボルを前に配置します。
4. 各シンボルの葉ノードを生成します。
5. リストを 2 つの部分に分割し、左分岐の確率が右分岐の確率とほぼ等しくなるようにします。
6. それぞれの左および右ノードのコードの前に 0 と 1 を追加します。
7. 各ノードが木の葉であるまで、ステップ 5 と 6 を左および右の部分木に再帰的に適用します。

4.3.2 ハフマン符号化#

ハフマン符号化はエントロピー符号化の別の変種で、シャノン - ファノ符号化と非常に似た動作をしますが、二分木は上から下に構築され、最適な結果を生成します。

ハフマン符号化を生成するアルゴリズムは、シャノン - ファノといくつかの最初のステップを共有します：

1. 入力を解析し、各シンボルの出現回数を計算します。

2. シンボルのカウントを使用して、各シンボルの確率を決定します。シンボルを確率に基づいて並べ替え、最も可能性の高いものを前に配置します。

3. 各シンボルの葉ノードを生成し、P を含めて、それらをキューに追加します。

4. キュー内のノード数が > 1 のとき、次の操作を実行します：

   • キューから確率が最も低い 2 つのノードを削除します。
   • 左右のノードのコードの前にそれぞれ 0 と 1 を追加します。
   • 2 つのノードの確率の合計に等しい新しいノードを作成します。
   • 最初のノードを左分岐に、2 番目のノードを右分岐に割り当てます。
   • ノードをキューに追加します。

5. キューに残っている最後のノードがハフマン木の根ノードです。[16]

4.3.3 算術符号化#

この方法は 1979 年に IBM 社によって開発され、同社はその大型コンピュータのデータ圧縮技術を研究していました。もし目標が最適な圧縮比を得ることであれば、算術符号化は最も優れたエントロピー符号化技術と言えるでしょう。なぜなら、通常はハフマン符号化よりも良い結果を得るからです。しかし、他の符号化技術に比べて算術符号化ははるかに複雑です。

算術符号化は、シンボルの確率をツリー構造に分割するのではなく、基数を変更し、0 から基数の間の各ユニークシンボルに単一の値を割り当てることによって、入力データを 0 から 1 の間の有理数に変換します。次に、それは固定小数位数の二進数に変換され、これが符号化結果です。この値は、基数を二進数から元の基数に戻し、値をそれに対応するシンボルに置き換えることによって元の出力にデコードできます。

算術符号化の一般的なアルゴリズムは次のようになります：

1. 入力中のユニークシンボルの数を計算します。
2. この数字は算術符号化の基数 b を示します（例えば、基数 2 は二進数）。
3. 出現順に、各ユニークシンボルに 0 から b の値を割り当てます。
4. ステップ 2 の値を使用して、入力中のシンボルをそれらの符号で置き換えます。
5. ステップ 3 の結果を基数 b から十分に長い固定小数位の二進数に変換し、精度を保持します。
6. 入力文字列の長さを結果に記録します。これはデコードプロセスに必要です。

以下は、入力「ABCDAABD」に対する例示的な符号化操作です：

1. 入力中に 4 つのユニークシンボルがあることを発見し、したがって基数は 4 です。
   長さは 8 です。
2. シンボルに値を割り当てます：A=0、B=1、C=2、D=3
3. コードを使用して入力を置き換えます：「0.012300134」、前の 0 はシンボルではありません。
4. 「0.012311234」を基数 4 から基数 2 に変換します：「0.011011000001112」
5. 結果を見つけます。結果には、入力の長さが 8 であることに注意してください。

8 ビット文字を仮定すると、入力の長さは 64 ビットですが、その算術符号化はわずか 15 ビットで、優れた圧縮比 24％をもたらします。この例は、限られた文字セットが与えられたときに、算術符号化がどのように良好な圧縮を行うかを示しています。

5 圧縮アルゴリズム#

5.1 スライディングウィンドウアルゴリズム#

5.1.1 LZ77#

1977 年に発表された LZ77 アルゴリズムは、画期的なアルゴリズムです。これは「スライディングウィンドウ」の概念を初めて導入し、より原始的なアルゴリズムよりも大きな圧縮比の改善をもたらしました。LZ77 は三元組を使用して辞書を維持し、これらの三元組はオフセット、ランレングス、および偏差文字を表します。オフセットは、与えられたフレーズがファイルの先頭から始まる距離を示し、ランレングスはオフセットからオフセット + 長さまでの文字数を示します。偏差文字は、新しいフレーズが見つかったことを示すだけで、そのフレーズはオフセットからオフセット + 長さに偏差文字を加えたものと等しいです。使用される辞書は、ファイルを解析する際にスライディングウィンドウの変化に応じて動的に変化します。例えば、スライディングウィンドウは 64MB である可能性があり、これは辞書が過去 64MB の入力データのエントリを含むことを意味します。

与えられた入力「abbadabba」の出力は「abb (0,1,'d')(0,3,'a')」のようになります。以下の例に示します：

この置換のサイズは入力よりわずかに大きいですが、通常は入力データが長い場合により小さな結果を得ることができます。[3]

5.1.2 LZR#

LZR は 1981 年にマイケル・ロデによって改良された LZ77 アルゴリズムです。このアルゴリズムは LZ77 の線形時間代替手段となることを目的としています。しかし、エンコーディングポインタはファイル内の任意のオフセットを指すことができるため、LZR は大量のメモリを消費します。さらに、圧縮比が悪いため（LZ77 が通常より優れている）、LZR は実行可能な変種とはなりませんでした。[18][19]

5.1.3 DEFLATE#

DEFLATE は 1993 年にフィル・カッツによって発明され、今日のほとんどの圧縮タスクの基礎となっています。これは単純に LZ77 または LZSS の前処理器と後端のハフマン符号化を組み合わせて、短時間で適度な圧縮結果を実現します。

5.1.4 DEFLATE64#

DEFLATE64 は DEFLATE アルゴリズムの独自の拡張で、辞書サイズを 64KB に増加させ（そのためこの名前が付けられました）、スライディングウィンドウ内でより大きな距離を許可します。DEFLATE と比較して、性能と圧縮比を向上させました。しかし、DEFLATE64 の独自性と DEFLATE に対する穏やかな改善により、この形式の採用は制限されました。代わりに、通常は LZMA のようなオープンソースアルゴリズムが使用されます。

5.1.5 LZSS#

LZSS（Lempel-Ziv-Storer-Szymanski）アルゴリズムは、1982 年にジェームズ・ストレイザーとトーマス・シマンスキーによって最初に発表されました。LZSS は LZ77 を改善し、置換がファイルサイズを小さくするかどうかを検出できます。サイズが小さくならない場合、入力はリテラルとして出力に保持されます。そうでない場合、入力の一部は（オフセット、長さ）のペアに置き換えられ、オフセットは入力の先頭から何バイト離れているかを示し、長さはその位置から何文字を読み取るかを示します。LZ77 と比較して、LZSS のもう一つの改善点は「次の文字」を排除し、オフセットと長さのペアのみを使用することです。

以下は短い例で、入力「these theses」が与えられ、「these (0,6) s」を生成し、1 バイトだけ節約しましたが、より大きな入力ではより多くのスペースを節約します。

LZSS は、最も有名な RAR を含む多くの人気アーカイブ形式で使用されています。時にはネットワークデータ圧縮にも使用されます。

5.1.6 LZH#

LZH は 1987 年に開発された「Lempel-Ziv Huffman」の略です。これは LZSS の変種で、Huffman 符号化を利用してポインタを圧縮し、わずかに良い圧縮効果を得ます。しかし、Huffman 符号化による改善は微々たるものであり、圧縮効果は Huffman 符号化に伴う性能コストに見合うものではありません。

5.1.7 LZB#

LZB は 1987 年にティモシー・ベルらによって開発された LZSS の変種です。LZH と同様に、LZB は LZSS ポインタをより効率的にエンコードすることによって圧縮ファイルのサイズを減少させることを目的としています。これは、ポインタのサイズを徐々に増加させ、スライディングウィンドウが大きくなるにつれてポインタも大きくなることによって実現されます。LZSS や LZH と比較して、より高い圧縮率を実現できますが、ポインタの追加のエンコーディングステップのため、LZSS よりも遅くなります。

5.1.8 ROLZ#

ROLZ は「Reduced Offset Lempel-Ziv」を指し、オフセット長を制限することによって LZ77 の圧縮率を向上させることを目的としています。この LZ77 の派生アルゴリズムは、ロス・ウィリアムズの LZRW4 アルゴリズムに最初に登場し、他の実装には BALZ、QUAD、RZM が含まれます。高度に最適化された ROLZ は、LZMA とほぼ同じ圧縮比を実現できますが、広範な適用がないため、ROLZ の人気は低いです。

5.1.9 LZP#

LZP は「Lempel-Ziv + Prediction」の略です。これは ROLZ アルゴリズムの特例で、オフセットが 1 に減少します。異なる技術を使用して、より高速な操作やより良い圧縮比を実現するためのいくつかの異なる変種があります。LZW4 は最適な圧縮比を得るために算術エンコーダを実装しましたが、その代償として速度が遅くなります。[22]

5.1.10 LZRW1#

ロン・ウィリアムズは 1991 年に LZRW1 アルゴリズムを作成し、「Lempel-Ziv 圧縮のオフセット削減」概念を初めて導入しました。LZRW1 は高圧縮比を実現しながら、速度が速く効率的な特徴を維持できます。ロン・ウィリアムズは、LZRW1 を改善するいくつかの変種（LZRW1-A、2、3、3-A、4 など）も作成しました。

5.1.11 LZJB#

ジェフ・ボンウィックは 1998 年に彼の Lempel-Ziv Jeff Bonwick アルゴリズムを Solaris Z ファイルシステム（ZFS）用に作成しました。これは LZRW アルゴリズムの変種、特に LZRW1 の変種と見なされ、最大の圧縮速度を実現することを目的としています。ファイルシステムで使用されるため、速度は特に重要であり、圧縮アルゴリズムがディスク操作のボトルネックにならないようにします。

5.1.12 LZS#

Lempel-Ziv-Stac アルゴリズムは、1994 年に Stac Electronics によってディスク圧縮ソフトウェアのために開発された改良型 LZ77 アルゴリズムです。出力内でリテラルシンボルとオフセット長のペアを区別し、次に遭遇したシンボルを省略します。LZS アルゴリズムは機能的に LZSS アルゴリズムと最も類似しています。

5.1.13 LZX#

LZX アルゴリズムは、1995 年にジョナサン・フォーブスとトミ・ポウタネンによってアミガコンピュータのために開発されました。LZX の X には特別な意味はありません。フォーブスは 1996 年にこのアルゴリズムをマイクロソフトに売却し、マイクロソフトのために働き、Microsoft のキャビネット（.CAB）形式で使用するためにさらに改良しました。このアルゴリズムは、マイクロソフトが圧縮された HTML ヘルプ（CHM）ファイル、Windows Imaging Format（WIM）ファイル、および Xbox Live アバターの圧縮にも使用されました。

5.1.14 LZO#

LZO は 1996 年にマルクス・オーバーハマーによって開発され、迅速な圧縮と解凍を実現することを目的としています。圧縮レベルを調整でき、最高の圧縮レベルはわずか 64KB の追加メモリを必要とし、解凍には入力と出力バッファのみが必要です。LZO の機能は LZSS アルゴリズムと非常に似ていますが、圧縮比率ではなく速度を重視しています。[26]

5.1.15 LZMA#

レンプル - ジブマルコフ連鎖アルゴリズムは、1998 年に 7-Zip 圧縮ソフトウェアのリリースとともに公開され、.7z ファイル形式に使用されます。通常、bzip2、DEFLATE、他のアルゴリズムよりも良い圧縮効果を得ることができます。LZMA は、データをビットレベルで解析するために修正された LZ77 アルゴリズムを使用し、従来のバイトレベルではなく、算術符号化を通じて LZ77 アルゴリズムの出力を生成します。特定の LZMA 実装に応じて、さらに多くの技術が適用される場合があります。結果は通常、他のほとんどの LZ 変種よりも良好な圧縮比を示します。これは主に、バイトレベルの圧縮ではなくビットレベルの圧縮方法を採用しているためです。

5.1.16 LZMA2#

LZMA2 は、元の LZMA アルゴリズムの漸進的な改良であり、最初は 2009 年に 7-Zip アーカイブソフトウェアの更新を通じて導入されました [28]。LZMA2 は LZMA アルゴリズムのマルチスレッド能力と性能を改善し、圧縮できないデータをより良く処理することで、わずかに優れた圧縮を実現します。

5.1.17 統計的レンプル - ジブ#

統計的レンプル - ジブは、2001 年にサム・クウォン博士とユ・ファン・ホーによって提案された概念です。その基本原則は、データの統計分析を LZ77 変種アルゴリズムと組み合わせて、辞書に保存されるエンコーディングをさらに最適化することです。[29]

5.2 辞書アルゴリズム#

5.2.1 LZ78#

LZ78 アルゴリズムは、レンプルとジブによって 1978 年に作成されました。したがって、略称には「78」が含まれています。スライディングウィンドウを使用して辞書を生成する方法とは異なり、入力データは辞書を生成するために前処理されるか、ファイルを解析する際に辞書が形成されます。LZ78 は後者の戦略を採用しています。辞書のサイズは通常数メガバイトに制限されるか、すべてのコードが一定のバイト数（例えば 8 バイト）であるように制限されます。これはメモリ要件を減少させるためです。ほとんどの LZ78 タイプのアルゴリズムは、辞書が満杯になったときの処理方法が異なります。

ファイルを解析する過程で、LZ78 アルゴリズムは遭遇した各新しい文字や文字列を辞書に追加します。入力中の各シンボルに対して、辞書インデックスと未知のシンボルの形式で辞書エントリが生成されます；シンボルがすでに辞書に存在する場合、辞書は現在のシンボルとその後のシンボルの部分文字列を検索します。最長部分文字列一致のインデックスが辞書インデックスとして使用されます。辞書インデックスが指すデータは、未知の部分文字列の最後の文字に追加されます。現在のシンボルが未知の場合、辞書インデックスは 0 に設定され、これは単一文字エントリであることを示します。これらのエントリは、リンクリストのようなデータ構造を形成します。

例えば、入力「abbadabbaabaad」は出力「(0,a)(0,b)(2,a)(0,d)(1,b)(3,a)(6,d)」を生成します。以下の例は、どのようにしてそれが得られたかを示しています：

5.2.2 LZW#

LZW は Lempel-Ziv-Welch アルゴリズムで、テリー・ウェルチによって 1984 年に作成されました。深刻な特許問題が存在するにもかかわらず、LZW は LZ78 アルゴリズムファミリーの中で最も広く使用されているアルゴリズムです。LZ78 と同様に、LZW は出力中の冗長な文字を排除し、出力を完全にポインタで構成することによって LZ78 を改善します。圧縮を開始する前に、辞書内の各文字を含め、各新しいフレーズの最後の文字を次のフレーズの最初の文字としてエンコードするなど、圧縮効果を向上させるための他の技術を採用しています。LZW は、グラフィックス交換形式（GIF）や ZIP 形式の初期仕様、他の専用アプリケーションで非常に一般的に見られます。LZW は非常に高速ですが、ほとんどの新しいアルゴリズムと比較して圧縮効果が劣り、一部のアルゴリズムはより高速で、より良い圧縮効果を実現できます。

5.2.3 LZC#

LZC（Lempel-Ziv Compress）は、UNIX 圧縮ユーティリティで使用される LZW アルゴリズムの軽微な修正です。LZC と LZW の主な違いは、LZC が出力の圧縮比を監視することです。比率がある閾値を超えると、辞書は破棄され再構築されます。[19]

5.2.4 LZT#

レンプル - ジブティッシャーアルゴリズムは LZC の改良版で、辞書が満杯になると、最近最少使用のフレーズを削除し、新しいエントリで置き換えます。他にもいくつかの漸進的な改善がありますが、LZC と LZT は今日あまり使用されていません。

5.2.5 LZMW#

LZMW アルゴリズムは、1984 年にビクター・ミラーとマーク・ウェグマンによって発明され、LZT と同様に最近未使用のフレーズ置き換え戦略を採用しています。しかし、LZMW は辞書内の類似エントリを統合するのではなく、最後の 2 つのエンコードされたフレーズを統合し、その結果を新しいエントリとして保存します。したがって、辞書のサイズは急速に拡大し、LRU をより頻繁に破棄する必要があります。LZT と比較して、LZMW は通常より良い圧縮を実現しますが、これもまたあまり一般的ではないアルゴリズムです。[19]

5.2.6 LZAP#

LZAP は、1988 年にジェームズ・ストーラーによって LZMW アルゴリズムを修正して作成されました。AP は「すべての接頭辞」を意味し、辞書は単一のフレーズだけでなく、各組み合わせを保存します。例えば、前のフレーズが「last」で、現在のフレーズが「next」である場合、辞書は「lastn」、「lastne」、「lastnex」、「lastnext」を保存します。[30]

5.2.7 LZWL#

LZWL は修正された LZW アルゴリズムで、2006 年に作成され、音節を使用して単一の文字を圧縮します。LZWL の設計は、XML データのような特定のデータセットで多くの一般的な音節を処理するのに適しています。通常、このようなアルゴリズムは前処理器と共に使用され、入力データを音節に分解します。

5.2.8 LZJ#

マッティ・ヤコブソンは 1985 年に LZJ アルゴリズムを発表しました [32]。これは LZW とは異なる唯一の LZ78 アルゴリズムの一つです。このアルゴリズムは、処理された入力内の各ユニークな文字列（任意の最大長を超えない）を辞書に保存し、各文字列にコードを割り当てることによって機能します。辞書が満杯になると、1 回だけ出現したすべてのエントリが削除されます。[19]

5.3 非辞書アルゴリズム#

5.3.1 PPM#

部分一致による予測は、入力中の一連の以前のシンボルを使用して次のシンボルを予測し、出力データのエントロピーを減少させる統計モデル技術です。これは辞書とは異なり、PPM は次のシンボルを予測し、辞書内で次のシンボルを見つけようとはしません。通常、PPM は算術符号化や適応ハフマン符号化などのエンコーダと組み合わせて使用されます。PPM またはその変種 PPMd は、7-Zip や RAR を含む多くのアーカイブ形式で実装されています。

5.3.2 bzip2#

bzip2 はバーロウズ - ウィーラー変換のオープンソース実装です。その動作は非常にシンプルですが、速度と圧縮比の間で非常に良いバランスを実現しており、bzip2 形式は UNIX 環境で非常に人気があります。最初にデータにランレングスエンコーディングを適用します。次に、バーロウズ - ウィーラー変換を適用します。次に、前方移動変換を適用し、他のランレングスエンコーダが使用するために同じシンボルのランを形成することを目的とします。最後に、結果はハフマン符号化され、ヘッダーファイルにパッケージ化されます。

5.3.3 PAQ#

PAQ は 2002 年にマット・マホニーによって作成され、古い PPM（d）アルゴリズムを改善することを目的としています。これは、コンテキストミキシングと呼ばれる革命的な技術を使用して、複数の統計モデル（PPM はその一つ）をインテリジェントに組み合わせ、単一のモデルよりも次のシンボルをより良く予測します。PAQ は非常に高い圧縮比と非常に活発な開発を持つため、最も有望なアルゴリズムの一つです。誕生以来、20 以上の変種が作成され、その中には記録的な圧縮比を実現したものもあります。PAQ の最大の欠点は、最適な圧縮比を得るために複数の統計モデルを使用するため、速度が遅くなることです。しかし、ハードウェアがますます高速化するにつれて、将来的には標準となる可能性があります。PAQ は徐々に採用されており、Windows 上の PeaZip プログラムで 64 ビットサポートと主要な速度改善を持つ PAQ8O 変種が見つかります。他の PAQ 形式はほとんどがコマンドライン専用です。

6 参考文献#

1. ウォルフラム、スティーブン。新しい科学の種類。シャンペーン、IL：ウォルフラムメディア、2002 年。1069。印刷。

2. ケン・ハフマン。プロフィール：デビッド・A・ハフマン、サイエンティフィックアメリカン、1991 年 9 月、54-58 ページ。

3. Ziv J.、Lempel A.、「逐次データ圧縮のための普遍的アルゴリズム」、IEEE 情報理論トランザクション、Vol. 23、No. 3（1977）、337-343 ページ。

4. Ziv J.、Lempel A.、「可変レート符号化による個々のシーケンスの圧縮」、IEEE 情報理論トランザクション、Vol. 24、No. 5、530-536 ページ。

5. USPTO 特許 #4814746。http://www.theregister.co.uk/1999/09/01/unisys_demands_5k_licence_fee を参照。

6. blog [Fedora & Linux Tips]

7. http://www.msversus.org/archive/stac.html

8. ARC 情報

9. comp.compression よくある質問（パート 1/3）セクション - [8] データ圧縮アルゴリズムの特許についてはどうですか？

10. USPTO 特許 #5051745

11. フィル・カッツの死

12. Iwata, K., Arimura, M., and Shima, Y., "部分列列挙による無損データ圧縮の改善"、2011 IEEE/ACIS 第 10 回国際コンピュータおよび情報科学会議（ICIS）。

13. バーロウズ M.、ウィーラー D. J. 1994。ブロックソート無損データ圧縮アルゴリズム。SRC 研究報告 124、デジタルシステム研究センター。

14. http://www.cs.tau.ac.il/~dcor/Graphics/adv-slides/entropy.pdf

15. シャノン、C.E.（1948 年 7 月）。「通信の数学的理論」。ベルシステム技術ジャーナル 27：379–423。

16. ハフマン、D. A. 1952。最小冗長符号の構築方法。電気およびラジオエンジニア協会の会議録 40、9（9 月）、1098-1101 ページ。

17. リッサネン、J.、およびランドン、G. G. 1979。算術符号化。IBM J. Res. Dev. 23、2（3 月）、149-162 ページ。

18. ロデ、M.、プラット、V. R.、およびエヴン、S. 1981。文字列マッチングによるデータ圧縮の線形アルゴリズム。J. ACM 28、1（1 月）、16-24 ページ。

19. ベル、T.、ウィッテン、I.、クリアリー、J.、「テキスト圧縮のためのモデリング」、ACM コンピューティングサーベイ、Vol. 21、No. 4（1989）。

20. DEFLATE64 ベンチマーク

21. ストレイザー、J. A.、およびシマンスキー、T. G. 1982。テキスト置換によるデータ圧縮。J. ACM 29、4（10 月）、928-951 ページ。

22. ブルーム、C.、「LZP：新しいデータ圧縮アルゴリズム」、データ圧縮会議、1996 年。DCC '96。プロシーディングス、p。425 10.1109/DCC.1996.488353。

23. ドクター・ロスの圧縮暗号

24. 「データ圧縮方法 - 情報交換のためのスライディングウィンドウによる適応符号化」、情報システムのためのアメリカ国立標準、1994 年 8 月 30 日。

25. LZX はマイクロソフトに売却されました。

26. LZO 情報

27. LZMA は 2011 年 12 月 10 日にアクセスされました。

28. LZMA2 リリース日

29. クウォン、S.、ホー、Y.F.、「個人デジタルアシスタント（PDA）用の統計的レンプル - ジブ圧縮アルゴリズム」、IEEE トランザクションズ・オン・コンシューマーエレクトロニクス、Vol. 47、No. 1、2001 年 2 月、154-162 ページ。

30. デビッド・サロモン、データ圧縮 - 完全なリファレンス、4 版、212 ページ。

31. チェルニク、K.、ランスキー、J.、ガランボス、L.、「XML ドキュメントの音節ベースの圧縮」、Dateso 2006、21-31 ページ、ISBN 80-248-1025-5。

32. ヤコブソン、M.、「適応辞書による文字列の圧縮」、BIT コンピュータサイエンスおよび数値数学、Vol. 25 No. 4（1985）。doi>10.1007/BF01936138

33. クリアリー、J.、ウィッテン、I.、「適応符号化と部分文字列マッチングを使用したデータ圧縮」、IEEE トランザクションズ・オン・コミュニケーション、Vol. COM-32、No. 4、1984 年 4 月、396-402 ページ。

34. シュワード、J.、「bzip2 および libbzip2」、bzip2 マニュアル、2000 年 3 月。

35. マホニー、M.、「無損データ圧縮のためのコンテキストモデルの適応重み付け」、不明、2002 年。