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 でリリースされました。これにより、ディスクの容量が倍増すると言われました。Stac Electronics がその知的財産が使用されていることに気づいたとき、彼はマイクロソフトを訴えました。マイクロソフトは後に有罪判決を受け、Stac Electronics に対して 1.2 億ドルの損害賠償を支払うよう命じられました。1360 万ドルの反訴の判決を差し引いても、マイクロソフトの侵害は推定されていません [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 は現在最も一般的なデータ圧縮アルゴリズムであり、圧縮のスイスアーミーナイフのような存在です。

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 形式に大きな競争をもたらしました。もう 1 つのオープンソース圧縮プログラムは 1999 年に発表され、7-Zip または.7z 形式です。通常は高い圧縮比と形式のモジュール性とオープン性により、7-Zip は ZIP や RAR の主導的地位に挑戦する最初の形式かもしれません。この形式は 1 つの圧縮アルゴリズムを使用することに制限されず、bzip2、LZMA、LZMA2、PPMd などのアルゴリズムの間で選択できます。最後に、アーカイブソフトウェアの最前線には PAQ * 形式があります。最初の PAQ 形式は 2002 年にマット・マホニーによって発表され、PAQ1 と呼ばれています。PAQ は「コンテキストミキシング」と呼ばれる技術を使用して 2 つ以上の統計モデルを組み合わせることで、PPM アルゴリズムを大幅に改善し、単独のモデルよりも次のシンボルをより良く予測します。

3 未来の発展#

未来は常に不確実ですが、現在の傾向に基づいてデータ圧縮の未来についていくつかの予測を行うことができます。PAQ およびその変種のコンテキストミキシングアルゴリズムは人気が高まり始めており、通常は最高の圧縮比を実現できますが、速度は通常遅いです。ハードウェアの速度が指数関数的に増加し、ムーアの法則に従う中で、コンテキストミキシングアルゴリズムは高圧縮比の状況で大きな成功を収める可能性が高いです。なぜなら、速度のペナルティはより高速なハードウェアによって克服されるからです。PAQ は改良された予測部分一致（PPM）アルゴリズムも新しい変種が登場する可能性があります。最後に、レンプル - ジブマルコフ連鎖アルゴリズム（LZMA）は、優れた速度と高圧縮比のバランスを示しており、さらに多くの変種が生まれる可能性があります。LZMA は 7-Zip 形式で導入されて以来、広く採用されており、多くの競合する圧縮形式で使用されているため、「勝者」となる可能性があります。もう 1 つの潜在的な発展方向は、サブストリング列挙圧縮（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 シャノン - ファノ符号化#

これは最も古い圧縮技術の 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 のもう 1 つの改善点は「次の文字」を排除し、オフセットと長さのペアのみを使用することです。

以下は、与えられた入力「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 アルゴリズムを作成し、「オフセットを減少させるレンプル - ジブ圧縮」の概念を初めて導入しました。LZRW1 は高圧縮比を実現しながら、速度が速く効率的な特性を維持できます。ロン・ウィリアムズはまた、LZRW1 を改善するいくつかの変種（LZRW1-A、2、3、3-A、4 など）を作成しました。

5.1.11 LZJB#

ジェフ・ボンウィックは 1998 年に彼のレンプル - ジブジェフ・ボンウィックアルゴリズムを 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 アルゴリズムを使用し、従来のバイトレベルではなく、出力を生成します。特定の 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 は、2006 年に作成された修正された LZW アルゴリズムであり、単一の文字ではなく音節を使用して圧縮します。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 はその 1 つ）をスマートに組み合わせ、単一のモデルよりも次のシンボルをより良く予測します。PAQ は非常に高い圧縮比と非常に活発な開発を持つため、最も有望なアルゴリズムの 1 つです。誕生以来、20 以上の変種が作成され、その中には記録的な圧縮比を実現したものもあります。PAQ の最大の欠点は、最適な圧縮比を得るために複数の統計モデルを使用するため、速度が遅くなることです。しかし、ハードウェアがますます高速化するにつれて、将来的には標準となる可能性があります。PAQ は徐々に採用されており、Windows 上の PeaZip プログラムで 64 ビットサポートと主要な速度改善を持つ PAQ8O 変種が見つかります。他の PAQ 形式はほとんどがコマンドライン専用です。

6 参考文献#

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

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

3. Ziv J.、Lempel A.、「A Universal Algorithm for Sequential Data Compression」、IEEE Transactions on Information Theory、Vol. 23、No. 3（1977）、337-343 ページ。

4. Ziv J.、Lempel A.、「Compression of Individual Sequences via Variable-Rate Coding」、IEEE Transactions on Information Theory、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. 岩田、K.、有村、M.、島、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 Computing Surveys、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。議事録、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 Transactions on Consumer Electronics、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 Transactions on Communications、Vol. COM-32、No. 4、1984 年 4 月、396-402 ページ。

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

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