Theorie: Komprimierungsalgorithmus, der einige Dateien kleiner, aber keine größer macht?

Question

Ich bin auf diese Frage gestoßen;

"Ein verlustfreier Komprimierungsalgorithmus behauptet, einige Dateien zu garantieren, um kleiner und keine Dateien größer zu werden.
Ist das;

a) unmöglich

b) möglich, kann aber für eine unbestimmte Zeit laufen, Zeit,

c) für den Kompressionsfaktor 2 oder weniger möglich,

d) Möglich für einen Kompressionsfaktor? "

Ich neige zu (a), konnte aber keine solide Erklärung geben, warum. (Ich werde die Gedanken auflisten, die ein Freund und ich als mögliche Antwort ausgedacht haben)

Answer 1

Nach dem Prinzip von Taubenloch haben Sie bei einer Reihe von 10 Bits 1024 mögliche Eingänge und müssen auf 9 Bit oder weniger zugeordnet werden, sodass es <1024 Ausgänge gibt.

Dies garantiert entweder, dass der Algorithmus Kollisionen (Verlustkomprimierung) oder irgendwann entschieden hat, den nicht modifizierten Eingang als Ausgabe zurückzugeben.

Im letzteren Fall können Sie nicht bestimmen, wie Sie eine beliebige Bit -Reihe dekomprimieren können. (Es kann sich um einen unmodifizierten Eingang oder eine komprimierte Ausgabe aus einer größeren Bit -Zeichenfolge handeln.)

-> unmöglich.

Answer 2

Nur eine leichte Klärung von Rjfalconers Post ...

Sie müssen nur haben etwas Dateien werden kleiner, so dass die Behauptung, dass eine Zeichenfolge von 10 Bits 9 Bit oder weniger zu kartieren ist, ist nicht ganz richtig. Insbesondere, wenn jemand einen solchen Kompressionsmechanismus vorschlug könnte Zeichnen Sie alle Zeichenfolgen von 10 Bits oder weniger auf genau dieselbe Ausgabe ab (dh eine Identitätstransformation).

Uns wird jedoch gesagt, dass es gibt mindestens eine Datei das wird kleiner. Überlegen Sie sich ohne Verlust der Allgemeinheit, dass Sie mit X -Bits beginnen und als Y -Bits enden, wobei y streng geringer ist als x.

Betrachten Sie nun die Domäne von "Dateien mit Y -Bits oder weniger", die 2 haben^y+1-1 Bit Strings (einschließlich des leeren). Damit keiner von diesen zu einer größeren Datei führen kann, muss jeder in derselben Domäne einer Bit -Zeichenfolge zuordnen, dh 2^y+1-1 Komprimierte Dateien. Wir wissen jedoch bereits, dass die anfängliche Zeichenfolge von Länge x Bits zu einem dieser Werte komprimiert wird und nur 2 bleibt^y+1-2 mögliche Werte.

Bei Dies Zeigen Sie auf das Prinzip der Taubenloch - Sie können eindeutig nicht 2 zuordnen^y+1-1 Eingänge zu 2^y+1-2 Ausgänge, ohne einen Ausgang zu wiederholen, der gegen die Reversibilität der Komprimierung verstößt.

Answer 3

a) unmöglich

Wenn Sie eine Datei haben, die nicht weiter komprimiert werden kann, müssen Sie immer noch die Informationen hinzufügen, ob sie komprimiert wurde oder nicht. In diesem Fall müsste die Datei wachsen.

Answer 4

Ich weiß, dass ich ein bisschen spät dran bin, aber ich habe das über Google gefunden und jemand anderes könnte das Gleiche tun, also werde ich meine Antwort veröffentlichen: Die offensichtliche Lösung ist a) impossible, Auch Jon Skeet betonte (und übrigens gibt es überall im Internet viele Beweise). Ich stelle die Unmöglichkeit nicht in Frage, zufällige Daten zu komprimieren, nur um von Anfang an klar zu sein. Ich habe die Theorie verstanden, die dahinter liegt, und - Wenn Sie mich fragen, vertraue ich der Mathematik. : D

Aber wenn wir dürfen Denken Sie seitlich nach, Wir könnten definitiv die Tatsache nutzen, dass die Frage nicht genau definiert ist, was bedeutet, dass sie keine strenge Definition des "Komprimierungsalgorithmus" und der Eigenschaften, die es haben sollte (aber zu reduzieren etwas Dateien, ohne irgendjemanden zu erweitern).

Außerdem ist es für die Komprimierung der Dateien überhaupt nicht die Bedingung. Das einzige, an dem es interessiert ist, ist "Um einige Dateien kleiner zu machen und keine Dateien größer zu machen".

Trotzdem haben wir jetzt mindestens zwei Möglichkeiten, um zu zeigen, dass es tatsächlich einen solchen Algorithmus gibt:

1. Wir können den Namen der Datei ausnutzen, um einige der Informationen der Datei zu speichern (oder sogar die gesamte Datei, falls das Dateisystem dies zulässt, wodurch jede Datei auf 0 Bit reduziert wird). Trivial konnten wir einfach entscheiden, dass wir jede Datei außer einer unberührt haben, sie auf 0 Bit reduzieren und sie mit einem vordefinierten Namen umbenennen. Ich bin damit einverstanden, dass dies als Betrug angesehen werden könnte, aber es gibt keine Einschränkungen in der anfänglichen Frage, und dieser Algorithmus würde den Zweck effektiv erreichen (solange niemand die Datei umbenannt, wäre dies der Grund, warum dies eine sehr schlechte Auswahl von Designs wäre sinnlos sein).

2. Wir können die Anzahl der zu komprimierten Dateien zumindest auf diejenigen beschränken X Bits lang. Eine triviale Lösung wäre erneut, jede Datei unberührt zu lassen, die wir reduzieren können, damit sie mit einer kleineren Datei übereinstimmt X Bits. Jetzt Wir tun es Haben Sie einen Algorithmus, der wörtlich zitiert, einige Dateien kleiner und keine Dateien größer werden. Es führt jedoch eine Einschränkung für alle möglichen Eingaben durch (dh es kann nicht alle Dateien verarbeiten).

Für diejenigen, die argumentieren, dass dies keine praktische Verwendung haben würde, sage ich, dass ich Ihnen zustimme ... aber hey, das ist die Theorie, und das war nur eine theoretische Dissertation. ;))

Wenn ich einen Test durchführen und sich dieser Frage stellen würde, würde ich natürlich ein mutiges X auf die a), Und dann gehen Sie einfach weiter, ohne zu viel darüber nachzudenken.

Dennoch ist es durchaus möglich zu zeigen, dass die natürliche Sprache, da die natürliche Sprache an sich nicht mehrdeutig ist und die Frage nicht formell ausgedrückt wird, jede der anderen möglichen Antworten nicht unbedingt falsch ist: die richtigen Bedingungen zu platzieren und schließlich klarer anzugeben, was unter bestimmten Konzepten gemeint ist Möglicherweise können wir rechtlich das Ziel einer der anderen aufgeführten Optionen erfüllen, eine Art Trick machen und das Programm dazu zwingen, das gewünschte Verhalten zu erreichen.

Answer 5

e) möglich

... mit einigen Einschränkungen.

Ich bin kürzlich auf Shoco, eine String -Komprimierungsbibliothek für kleine Zeichenfolgen. Ich wurde an diese Frage erinnert, als ich diese Behauptung las:

... Die bemerkenswerteste Eigenschaft von SHOCO ist, dass die komprimierte Größe die Größe Ihrer Eingangszeichenfolge niemals überschreiten wird, vorausgesetzt, es handelt sich um einfaches ASCII.

Wenn Sie sicher sind, dass die Eingabedaten nur ASCII sind, muss Ihr Out -Puffer nur so groß sein wie die Eingangszeichenfolge

http://ed- von-schleck.github.io/shoco/#how-it-works

Answer 6

möglich

to make some files smaller and no files larger

Wenn dieser Komprimierungsalgorithmus die Datei größer macht, lassen Sie sie einfach die Originaldatei zurückgeben.