compression - テキストのみの圧縮アルゴリズムの現状は?

Question

ハッター賞を記念して、テキスト圧縮のトップ アルゴリズム (およびそれぞれの簡単な説明) は何ですか?

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

Answer 1

限界を押し上げるコンプレッサーは、非常識な結果を得るためにアルゴリズムを組み合わせます。一般的なアルゴリズムは次のとおりです。

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

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

Answer 2

常にlzipがあります。

冗談はさておき：

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