理論：いくつかのファイルを小さくしているが大きくする圧縮アルゴリズム？
https://stackoverflow.com/questions/1513567
-
19-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
私はこの質問に出くわしました。
「ロスレス圧縮アルゴリズムは、いくつかのファイルを小さくし、ファイルを大きくしないことを保証すると主張しています。
これは;
a）不可能
b）可能ですが、不確定な時間に実行される場合があります、
c）圧縮因子2以下の場合、
d）圧縮因子が可能ですか？」
私は（a）に傾いていますが、その理由について確かな説明をすることができませんでした。 （私は友人に考えをリストし、私は考えられる答えとして思いついた）
解決
ピジョンホールの原理により、10ビットの文字列が与えられた場合、1024の可能な入力があり、9ビット以下にマッピングする必要があるため、1024未満の出力があります。
これにより、アルゴリズムが衝突（損失のある圧縮）があるか、ある時点で、変更されていない入力を出力として返すことを保証します。
後者の場合、任意のビットを解凍する方法を決定することはできません。 （これは、変更されていない入力、または大きなビット文字列からの圧縮出力である可能性があります）。
- >不可能。
他のヒント
rjfalconerの投稿の少し明確化...
あなたは持っているだけです いくつか ファイルが小さくなるため、10ビットの文字列が9ビット以下にマッピングする必要があるという主張は正しくありません。特に、誰かがそのような圧縮メカニズムを提案した場合 できる 10ビット以下のすべての文字列をまったく同じ出力にマッピングします（つまり、アイデンティティ変換）。
しかし、私たちはあると言われています 少なくとも1つのファイル それは小さくなります。一般性を失うことなく、xビットから始めてyビットとして終わることを考慮してください。ここで、yは厳密にxより少ないです。
次に、2を持つ「Yビット以下のファイル」のドメインを検討してくださいy+1-1ビット文字列（空の文字列を含む）。それらのどれも大きなファイルをもたらさないために、それぞれが同じドメイン、すなわち2文字列にマッピングする必要があります。y+1-1圧縮ファイル。ただし、長さxビットの初期文字列がそれらの値の1つに圧縮されていることをすでに知っています - 2だけ残っていますy+1-2可能な値。
で これ ポイントピジョンホールの原理が入ってくる - あなたは明らかに2をマッピングすることはできませんy+1-1への入力2y+1-2出力を繰り返すことなく出力し、圧縮の可逆性に違反します。
a）不可能
これ以上圧縮できないファイルがある場合、それが圧縮されているかどうかにかかわらず情報を追加する必要があるため、その場合、ファイルは成長する必要があります。
私はちょっと遅れていることを知っていますが、私はこれをGoogleと他の誰かが同じことをすることができると感じたので、私の答えを投稿します：明らかな解決策はです a) impossible, 、Jon Skeetが指摘しています（そして、ところで、インターネット全体に多くの証拠があります）。最初から明確にするために、ランダムデータを圧縮することは不可能であることに疑問を抱いていません。私はその背後にある理論を理解しました、そして - あなたが私に尋ねるならば、私は数学を信頼しています。 ：d
しかし、私たちが許可されている場合 横方向に考えてください, 、私たちは間違いなく、質問が明確に定義されていないという事実を利用することができます。つまり、「圧縮アルゴリズム」とそれが持つべき特性の厳格な定義を与えないことを意味します（ただし、減らすために いくつか 他の人を拡張せずにファイル）。
また、それはファイルに圧縮されるように条件を置くことはありません、それが興味を持っているのは 「いくつかのファイルを小さくし、ファイルを大きくしないようにするために」.
とはいえ、実際、それがそのようなアルゴリズムが存在することを示すための少なくとも2つの方法があります。
ファイルの名前を悪用して、ファイルの情報の一部（ファイル全体が許可されている場合、ファイル全体を保存するため、すべてのファイルを0ビットに削減できます）。些細なことに、1つを除くすべてのファイルを控えめなままにしておくと、それを0ビットに減らして、事前定義された名前で名前を変更することを決定することができます。これは不正行為と見なされる可能性があることに同意しますが、繰り返しますが、最初の質問に制限はなく、このアルゴリズムは効果的に目的を達成します（ファイルの名前を変更しない限り、これは非常に悪いデザインの選択になります。無意味である）。
たとえば、少なくともファイルに圧縮されるファイルの数を制限することができます
X長さのビット。繰り返しになりますが、些細な解決策は、すべてのファイルを触れずに残すことです。Xビット。今 私たちはします Verbatimを引用して、いくつかのファイルを小さくし、ファイルを大きくしないアルゴリズムがあります。ただし、可能なすべての入力に対して制限を実行します（つまり、すべてのファイルを処理することはできません）。
これは実用的なものではないと主張する人々に、私はあなたに同意すると言います...しかし、これは理論であり、これは単なる理論的な論文でした。 ;）
明らかに、もし私がテストをしてこの質問に直面するなら、私は大胆なXを置いた a), 、そしてそれについてあまり考えずに続けてください。
それにもかかわらず、自然言語は本質的に曖昧であり、質問が正式に表現されていないため、他の可能な答えのそれぞれが必ずしも間違っているわけではないことを示すことが完全に可能です。正しい条件を配置し、最終的には特定の概念の意味をより明確に指定する、私たちは法的に他のリストされたオプションのいずれかの目標を達成し、何らかのトリックを行い、プログラムを強制して望ましい行動を達成することができるかもしれません。
e）可能
...いくつかの制限があります。
私は最近出会いました ショコ, 、小さな文字列用の文字列圧縮ライブラリ。この主張を読んだとき、私はこの質問を思い出しました：
... Shocoの最も注目すべき特性は、圧縮されたサイズが、単純なASCIIである場合、入力文字列のサイズを超えないことです。
入力データが単純なASCIIであると確信している場合は、入力文字列と同じ大きさである必要があります。
可能
to make some files smaller and no files larger
上記の圧縮アルゴリズムがファイルを大きくする場合、元のファイルを返すだけです。
