テキストのみの圧縮アルゴリズムの現在の状態は何ですか？

Question

ハッター賞を称えて、 テキスト圧縮のトップアルゴリズム（およびそれぞれの簡単な説明）は何ですか？

注：この質問の目的は、圧縮プログラムではなく、圧縮アルゴリズムの説明を取得することです。

Answer 1

バウンダリプッシングコンプレッサーは、非常識な結果を得るためのアルゴリズムを組み合わせています。一般的なアルゴリズムは次のとおりです。

• Burrows-Wheeler Transform およびこちら-予測可能なアルゴリズムで文字（またはその他のビットブロック）をシャッフルし、繰り返しブロックを増やしてソースを圧縮しやすくします。解凍は通常どおり行われ、結果は逆変換でシャッフルされません。注：BWTだけでは、実際には何も圧縮されません。ソースを圧縮しやすくするだけです。
• 部分一致による予測（PPM）-の進化算術コーディングでは、ソースに関する統計をクランチすることにより、静的確率を使用して予測モデル（コンテキスト）が作成されます。そのルーツは算術コーディングにありますが、結果は算術コーディングと同様にハフマン符号化または辞書で表すことができます。
• コンテキストミキシング-算術コーディングは予測に静的コンテキストを使用し、PPMは単一のコンテキストを動的に選択し、コンテキストミキシングは多くのコンテキストを使用して結果を比較します。 PAQはコンテキストミキシングを使用します。 こちらの概要です。
• 動的マルコフ圧縮-PPMに関連しますが、ビットレベルのコンテキストとバイト以上を使用します。
• さらに、ハッター賞の出場者は、一般的なテキストを外部辞書のスモールバイトエントリに置き換え、大文字と小文字のテキストを特別な記号で区別し、2つの異なるエントリを使用する場合があります。そのため、テキスト（特にASCIIテキスト）の圧縮には非常に優れており、一般的な圧縮にはあまり役立ちません。

最大圧縮は、非常にクールなテキストおよび一般的な圧縮ベンチマークサイトです。 Matt Mahoneyは別のベンチマークを公開しています。 Mahoneyはエントリごとに使用される主要なアルゴリズムをリストするため、特に興味深い場合があります。

Answer 2

常に lzip があります。

冗談はさておき：

• 互換性が懸念される場合でも、PKZIP（ DEFLATE アルゴリズム）が優先されます。
• bzip2は、比較的幅広いインストールベースを使用することと、かなり良い圧縮率を実現することとの最適な妥協案ですが、個別のアーカイバが必要です。
• 7-Zip （ LZMA アルゴリズム）は非常によく圧縮されており、 LGPLの下で。ただし、サポートが組み込まれたオペレーティングシステムはほとんどありません。
• rzip はbzip2の変形であり、私の意見ではもっと注目に値します。長期間のアーカイブを必要とする巨大なログファイルの場合、特に興味深い可能性があります。また、個別のアーカイバが必要です。

Answer 3

PAQをプログラムとして使用する場合、Debianベースのシステムに zpaq パッケージをインストールできます。使用法は（ man zpaq も参照）

zpaq c archivename.zpaq file1 file2 file3

圧縮は、 zipファイルのサイズの1/10程度まででした。 （1.9M対15M）