私はこの質問に出くわしました。
「ロスレス圧縮アルゴリズムは、一部のファイルを小さくし、ファイルを大きくしないことを保証すると主張しています。
これは;
a）不可能
b）可能ですが、不確定な時間実行される可能性があります。
c）圧縮率2以下で可能、
d）任意の圧縮率で可能ですか？」
私は（a）に傾倒していますが、その理由についてしっかりとした説明をすることができませんでした。（私は友人の考えをリストし、私は可能な答えとして思いついた）
1631 次
6 に答える
14
鳩の巣原理により、10ビットの文字列が与えられると、1024の可能な入力があり、9ビット以下にマップする必要があるため、出力は1024未満になります。
これにより、アルゴリズムに衝突（非可逆圧縮）があるか、ある時点で変更されていない入力を出力として返すことを選択することが保証されます。
後者の場合、ビットの任意の文字列を解凍する方法を決定することはできません。（変更されていない入力、またはより大きなビット文字列からの圧縮された出力である可能性があります）。
->不可能。
于 2009-10-03T11:58:25.807 に答える
10
RJFalconerの投稿のほんの少しの説明...
一部のファイルを小さくするだけでよいので、10ビットの文字列を9ビット以下にマップする必要があるという主張は正しくありません。特に、誰かがそのような圧縮メカニズムを提案した場合、10ビット以下のすべての文字列をまったく同じ出力にマップできます（つまり、恒等変換）。
ただし、小さくなるファイルが少なくとも1つあると言われています。一般性を失うことなく、xビットで始まり、yビットで終わることを考慮してください。ここで、yは厳密にxよりも小さくなります。
ここで、2つのy + 1 -1ビット文字列（空の文字列を含む）を持つ「yビット以下のファイル」のドメインについて考えてみます。それらのいずれもより大きなファイルにならないようにするには、それぞれが同じドメイン内のビット文字列、つまり2 y + 1-1圧縮ファイルにマップする必要があります。ただし、長さxビットの最初の文字列がこれらの値の1つに圧縮され、2つのy+ 1-2の可能な値のみが残ることはすでにわかっています。
この時点で鳩の巣原理が登場します。出力を繰り返さずに2y+ 1-1入力を2y + 1 -2出力にマッピングすることはできません。これは、圧縮の可逆性に違反します。
于 2009-10-03T12:12:47.850 に答える
0
a）不可能
それ以上圧縮できないファイルがある場合でも、圧縮されているかどうかに関係なく情報を追加する必要があるため、その場合はファイルを大きくする必要があります。
于 2009-10-03T12:48:46.500 に答える
0
私はちょっと遅れていることを知っていますが、これはグーグルで見つけました、そして他の誰かが同じことをすることができたので、私は私の答えを投稿します：明白な解決策はa) impossible、ジョン・スキートによっても指摘されています（そしてところでたくさんありますインターネット全体の証明の）。最初から明確にするために、ランダムデータを圧縮することが不可能であることを疑っていません。私はその背後にある理論を理解しました、そして-あなたが私に尋ねれば-私は数学を信頼します。：D
しかし、水平思考が許されれば、質問が明確に定義されていないという事実を確実に利用できます。つまり、「圧縮アルゴリズム」とそれが持つべき特性の厳密な定義が得られないということです。 （ただし、他の人を展開せずに一部のファイルを減らすため）。
また、圧縮するファイルにいかなる条件も課しません。関心があるのは、「一部のファイルを小さくし、ファイルを大きくしない」ことだけです。
とは言うものの、実際には、そのようなアルゴリズムが存在することを示すには、少なくとも2つの方法があります。
ファイルの名前を利用して、ファイルの情報の一部（または、ファイルシステムで許可されている場合はファイル全体）を保存して、すべてのファイルを0ビットに減らすことができます。自明なことに、1つを除くすべてのファイルをそのままにして、0ビットに減らし、事前定義された名前で名前を変更することもできます。これは不正行為と見なされる可能性があることに同意しますが、最初の質問に制限はなく、このアルゴリズムは目的を効果的に達成します（ファイルの名前を変更しない限り、これは設計上の選択としては非常に貧弱です。無意味であること）。
圧縮するファイルの数を、たとえば少なくとも
Xビット長のファイルに制限することができます。繰り返しになりますが、簡単な解決策は、すべてのファイルをそのままにして、1つだけ残しておくことです。これにより、Xビットよりも小さいファイルとの一致を減らすことができます。これで、逐語的に引用して、一部のファイルを小さくし、ファイルを大きくしないアルゴリズムができました。ただし、可能なすべての入力に対して制限を実行します（つまり、すべてのファイルを処理することはできません）。
これは実用的ではないと主張する人には、私はあなたに同意すると言います...しかしねえ、これは理論であり、これは単なる理論的な論文でした。;）
もちろん、テストを行ってこの質問に直面した場合は、に太字のXを付けてa)、あまり考えずに続行します。
それにもかかわらず、自然言語は本質的に曖昧であり、質問が正式に表現されていないため、他の考えられる答えのそれぞれが必ずしも間違っているわけではないことを示すことは完全に可能です：正しい条件を配置し、最終的に特定の概念が意味するものをより明確に指定する、他のリストされたオプションのいずれかの目標を合法的に達成できる可能性があり、ある種のトリックを実行し、プログラムに目的の動作を強制的に実行させます。
于 2014-09-19T01:07:24.523 に答える
0
e）可能
...いくつかの制限があります。
最近、小さな文字列用の文字列圧縮ライブラリであるShocoに出会いました。この主張を読んだとき、私はこの質問を思い出しました：
... shocoの最も注目すべき特性は、圧縮されたサイズが入力文字列のサイズを超えないことです。ただし、それがプレーンASCIIである場合に限ります。
入力データがプレーンASCIIであることが確実な場合、の出力バッファは入力文字列と同じ大きさである必要があります。
于 2017-06-07T08:44:11.830 に答える
0
可能
to make some files smaller and no files larger
上記の圧縮アルゴリズムによってファイルが大きくなる場合は、元のファイルを返すようにしてください。
于 2018-08-18T19:58:13.247 に答える