-3

データ圧縮のバイトペアリングについて質問です。バイト ペアリングが 2 つのバイト値を 1 つのバイト値に変換し、ファイルを半分に分割した場合、gig ファイルを取得して 16 回再利用すると、ファイルは 62,500,000 に縮小されます。私の質問は、バイトペアリングは本当に効率的ですか? 5,000,000 回の反復ループの作成は、保守的で効率的ですか? フィードバックと鋭い意見をお願いします。

デイブ、私が読んだ
のは、「米国特許庁はもはや永久機関の特許を付与していませんが、最近、数学的に不可能なプロセスに関する少なくとも 2 つの特許を付与しました: 真にランダムなデータの圧縮です。」
私は、特許庁が私が問い合わせていることを実際に検討していると推測したわけではありません。私は単に「数学的に不可能なプロセス」の概念についてコメントしただけです。誰かが、8 バイトのデータのプレースホルダーとして「1 つの」データ バイトを持つ方法を何らかの方法で作成した場合、それは特許の考慮事項になります。さて、8対1の圧縮方式の数学的な不可能性については、数学的な不可能性というよりは、一連のルールと条件を作成することができます。データをメディアに格納する際の 8 ビットまたは 16 ビット表現のルールがあれば、現在の方法を反映したデータの操作方法や、新しい考え方による作成方法があります。

4

1 に答える 1

5

一般に、あなたが説明した「再帰的圧縮」は蜃気楼です。圧縮は実際にはそのようには機能しません。

まず、すべての圧縮アルゴリズムには、入力ファイルを圧縮する代わりに拡張する可能性があることを理解する必要があります。これは、単純なカウント引数によって実証できます。ファイルの圧縮バージョンは、他のファイルの圧縮バージョンとは異なる必要があることに注意してください (そうしないと、そのファイルを適切に解凍できなくなります)。また、任意のファイル サイズ についてN、サイズ の可能なファイルの固定数があります<=N。size のファイルが size> Nまで圧縮できる<= N場合、同数の size のファイルを「圧縮」したとき<= Nに size まで拡大する必要があります。>N

第二に、「完全にランダムな」ファイルは圧縮できません。圧縮アルゴリズムは、特定の種類の予測可能な規則性を備えたファイルを受け取ることを想定しているため、圧縮が機能します。ただし、「真にランダムな」ファイルは定義上、予測不可能です。すべてのランダム ファイルは、同じ長さの他のすべてのランダム ファイルと同様に圧縮されないため、圧縮されません。

事実上、いくつかのファイルを他のファイルよりも可能性が高いものとして扱うモデルがあります。このようなファイルを圧縮するには、入力ファイルに対してより短い出力ファイルを選択する必要があります。 情報理論によると、ファイルを圧縮する最も効率的な方法は、確率Pの各入力ファイルに長さ~ log2(1/P)ビットの出力ファイルを割り当てることです。これは、理想的には、「真にランダムな」ファイルと同様に、特定の長さのすべての出力ファイルの確率がほぼ等しいことを意味します。

与えられた長さの完全にランダムなファイルの中で、それぞれの確率は(0.5)^(#original bits)です。上からの最適な長さ~ log2(1/ 0.5^(#original bits) ) = (#original bits)は、つまり元の長さがベストです。

優れた圧縮アルゴリズムの出力はほぼランダムであるため、圧縮ファイルを再圧縮してもほとんどまたはまったく得られません。それ以上の改善は、最適化されていないモデリングとエンコーディングによる事実上の「漏れ」です。また、圧縮アルゴリズムは、利用しない規則性を混乱させる傾向があり、そのような「漏れ」をさらに圧縮することはより困難になります。

このトピックに関するより長い説明と、このタイプの失敗した命題の多くの例については、comp.compression FAQを参照してください。「再帰的圧縮」機能の主張が目立つ。

于 2012-09-14T00:42:19.967 に答える