Theorie: Kompressionsalgorithmus, der einige Dateien kleiner, aber keiner größer macht?

Question

ich auf diese Frage kam;

„Ein lossless Kompressionsalgorithmus behauptet zu garantieren einige Dateien kleiner und keine Dateien größer machen
Ist das,.

a) Impossible

b) Mögliche, sondern kann für eine unbestimmte Menge laufen die Zeit,

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

d) möglich, für jeden Kompressionsfaktor?“

Ich lehne mich an (a), aber konnte keine solide Erklärung geben, warum. (Ich werde die Gedanken einen Freund auflisten und ich kam als mögliche Antwort)

Answer 1

Nach dem Taube-Loch-Prinzip, mit einer Folge von 10 Bits haben Sie 1024 mögliche Eingänge, und müssen auf 9 Bits oder zuordnen weniger, also gibt es < 1024 Ausgänge.

Dies garantiert entweder die Algorithmus hat Kollisionen (verlustbehaftete Kompression) oder an einem gewissen Punkt wählt den unmodifizierte Eingang als Ausgang zurückzukehren.

Im letzteren Fall können Sie nicht bestimmen, wie eine beliebige Bitfolge dekomprimiert wird. (Es könnte eine unmodifizierte Eingabe oder eine komprimierte Ausgabe von einer größeren Bitfolge sein).

-> Unmöglich.

Answer 2

Nur eine leichte Klärung RJFalconer die Post ...

Sie haben nur einige Dateien immer kleiner haben, so die Behauptung, dass eine Kette von 10 Bit auf 9 Bits oder weniger zur Karte hat, ist nicht ganz recht. Insbesondere, wenn jemand einen solchen Komprimierungsmechanismus vorgeschlagen hat, könnte er alle Zeichenfolgen von 10 Bits oder weniger auf genau den gleichen Ausgang (d. H. Eine Identitätstransformation) abbilden.

Allerdings wird uns gesagt, dass es mindestens eine Datei gibt, die kleiner wird. Ohne Beschränkung der Allgemeinheit, die Ansicht, dass mit x Bits zu starten und als y Bits enden, wobei y streng kleiner als x ist.

Betrachten Sie nun die Domäne von "Dateien mit y Bits oder weniger", die 2 ^{y + 1} -1 Bit Strings (einschließlich der leeren) hat. Damit keine von ihnen zu einer größeren Datei führt, muss jede auf eine Bitfolge in der gleichen Domäne abgebildet werden, d. H. 2 ^{y + 1} -1 komprimierte Dateien. Wir wissen jedoch bereits, dass die anfängliche Zeichenfolge der Länge x Bits auf einen dieser Werte komprimiert wird, so dass nur 2 ^{y + 1} -2 mögliche Werte übrig bleiben.

Bei diesen Punkt des Taube Loch Prinzip kommt - man kann eindeutig nicht 2 ^{Karte y + 1} -1 Eingänge 2 ^{y + 1} -2 Ausgänge ohne einen Ausgang zu wiederholen, was die Reversibilität verletzt der Kompression.

Answer 3

a) unmöglich

Wenn Sie eine Datei, die nicht weiter komprimiert werden kann, haben Sie noch die Informationen hinzufügen, ob es oder nicht komprimiert wurde, so dass in diesem Fall die Datei wachsen würde.

Answer 4

Ich weiß, dass ich etwas spät bin, aber ich fand dies über Google und jemand anderes könnte das gleiche tun, also werde ich meine Antwort posten: die offensichtliche Lösung ist a) impossible, auch von Jon Skeet (und Übrigens gibt es im Internet viele Beweise. Ich stelle nicht die Unmöglichkeit in Frage, zufällige Daten zu komprimieren, nur um von Anfang an klar zu sein; Ich habe die Theorie verstanden, die dahinter steckt, und - wenn Sie mich fragen - ich vertraue der Mathematik. : D

Aber wenn wir think laterally dürfen, könnten wir definitiv die Tatsache nutzen, dass die Frage nicht gut definiert ist, was bedeutet, dass es keine strenge Definition von "Kompressionsalgorithmus" und der Eigenschaften, die es haben sollte (aber einige Dateien zu reduzieren, ohne jemand anderen zu erweitern).

Es stellt auch keine Bedingung für die komprimierten Dateien, das einzige, das es interessiert, ist ", um einige Dateien kleiner und keine Dateien größer".

Das heißt, wir jetzt mindestens zwei Möglichkeiten haben zu zeigen, dass in der Tat, es einen solchen Algorithmus existiert:

1. Wir haben den Namen der Datei von einigen der Informationen speichern ausnutzen können die Datei (oder sogar die gesamte Datei, wenn das Dateisystem dies zulässt, wodurch jede Datei auf 0 Bit reduziert wird). Trivialerweise könnten wir einfach entscheiden, jede Datei bis auf eine unverändert zu belassen, sie auf 0 Bit zu reduzieren und sie mit einem vordefinierten Namen umzubenennen. Ich bin damit einverstanden, dass dieser Betrug in Betracht gezogen werden könnte, aber dann wieder, gibt es keine Einschränkungen in der anfänglichen Frage und dieser Algorithmus würde den Zweck effektiv erreichen (solange niemand die Datei umbenennt, das ist, warum dies eine sehr schlechtes Design Wahl wäre außer sinnlos sein).

2. Wir können die Anzahl der zu komprimierenden Dateien auf mindestens X Bits begrenzen. Noch einmal, eine triviale Lösung wäre, jede Datei unberührt zu lassen, aber eine, die wir reduzieren können, so dass sie mit einer Datei übereinstimmt, die kleiner als X Bits ist. Jetzt wir haben einen Algorithmus, der unter Angabe wörtlich, größer einige Dateien kleiner und keine Dateien macht; es führt jedoch eine Beschränkung für alle möglichen Eingaben durch (d. h. es kann nicht alle Dateien verarbeiten).

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

Offensichtlich, wenn ich einen Test machen und diese Frage stellen würde, würde ich ein fettes X auf das a) setzen, und dann weitergehen, ohne zu viel darüber nachzudenken.

Trotzdem ist es durchaus möglich ist, zu zeigen, dass da in natürlicher Sprache an mich nicht eindeutig ist und die Frage ist nicht formell ausgedrückt, jeder der anderen möglichen Antworten ist nicht unbedingt falsch: die richtigen Bedingungen platzieren und schließlich klare Angabe, was Mit bestimmten Begriffen gemeint, können wir legal in der Lage sein, das Ziel einer der anderen aufgelisteten Optionen zu erreichen, eine Art von Trickserei zu machen und das Programm zu zwingen, das gewünschte Verhalten zu erreichen.

Answer 5

e) Mögliche

... mit einigen Einschränkungen.

Ich kam vor kurzem in Shoco, eine Zeichenfolge Kompressionsbibliothek für kleine Strings. Ich wurde an diese Frage beim Lesen dieses Anspruchs erinnert:

... die bemerkenswerteste Eigenschaft von shoco ist, dass die komprimierte Größe niemals die Größe Ihrer Eingabezeichenfolge überschreiten wird, vorausgesetzt, es ist einfaches ASCII.

Wenn Sie sicher sind, dass die Eingangsdaten reine ASCII, Ihre Puffer aus für braucht nur so groß wie die Eingangskette

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