達成できるランダムバイナリデータの最適なファイル圧縮は何ですか？

Question

具体的には、どのようなプログラムがあり、最も高い圧縮率がありますか？私はグーグルでそれを試みたが、それは経験が検索結果よりも勝っていると思われるので、私は尋ねる。

Answer 1

ファイルサイズをビットに対して正確に指定できる場合、任意のファイルサイズNに対して、正確にはNビット以下の2 ^（N + 1）-1個のファイルが存在する可能性があります。サイズXのファイルをより小さいサイズYにマップするには、サイズY以下のファイルをサイズX以上のファイルにマップする必要があります。ロスレス圧縮が機能する唯一の方法は、ある可能性のあるファイルが他のファイルよりも可能性が高いと識別できるかどうかです。そのシナリオでは、可能性の高いファイルが縮小され、その可能性の低いファイルは増加します。

単純な例として、ビットがランダムで独立しているファイルを無損失で保存したいとしますが、ビットの50％が設定されているのではなく、33％のみが保存されているとします。そのようなファイルを圧縮するには、ビットの各ペアを取り、両方のビットがクリアであれば "0"を書き、第1ビットがセットされていれば "10"、第2ビットがセットされていれば "110"両方のビットがセットされていれば "111"となる。その効果は、ビットの各対が時間の1ビット44％、時間の2ビット22％、および時間の3ビット33％になることである。いくつかのデータ列は成長しますが、他のデータ列は縮小します。確率分布が予想どおりになった場合、収縮したペア数は成長する人数を上回ります（4/9ファイルは少し小さくなりますが、2/9は同じままになり、3/9は大きくなるためペアがオンになります）。平均は1/9ビット縮小し、ファイルは平均で1/18に縮小します[1/9数字はペアあたりのビット数であるため）。

実際にビットが50％の分布を持つ場合、ペアの25％のみが1ビットになり、25％は2ビットに留まり、50％は3ビットになります。したがって、ビットの25％が縮小し、50％が増加するため、平均でペアが25％、ファイルが12.5％増加します。ブレーク・イーブン・ポイントは、設定されているビットの約38.2％（2つのゴールデン・ミディアム）であり、ビット・ペアの38.2％が縮小し、同じ割合が増加する。

Answer 2

普遍的に最良の圧縮アルゴリズムはありません。異なるデータを扱うために、異なるアルゴリズムが発明されています。

たとえばJPEG圧縮では、画像の赤が0xFFまたは0xFE（通常）の場合はあまり重要ではないので、画像をかなり圧縮できます。ただし、テキストドキュメントを圧縮しようとすると、このような変更は悲惨です。

また、同じ種類のデータを扱うように設計された2つの圧縮アルゴリズムの間でも、結果はデー​​タによって異なります。

例：時にはgzipを使用するtarballが小さく、bzip tarballを使用することがより小さいことがあります。

最後に、十分な長さの本当にランダムなデータの場合、データは元のデータとほとんど同じサイズ（またはそれ以上）になる可能性があります。

Answer 3

ファイルアーカイバ7zは現在、最も圧縮率の高い若い圧縮アルゴリズムであるLZMA（Lempel Ziv Markow Algorithm）を使用しています（Linux Compression Comparison参照）。

高い圧縮率の横にあるもう一つの利点：

• 速い展開、約10
圧縮よりも早く20倍に小さなメモリフットプリント