Was ist die maximal theoretisch mögliche Kompressionsrate?

Dies ist eine theoretische Frage, also erwarten Sie, dass viele Details in der Praxis oder sogar in der Theorie nicht berechenbar sind.Was ist die maximal theoretisch mögliche Kompressionsrate?

Nehmen wir an, ich habe eine Zeichenfolge s, die ich komprimieren möchte. Das Ergebnis sollte eine selbstextrahierende Binärdatei sein (kann x86-Assembler sein, aber es kann auch eine andere hypothetische Turing-vollständige Low-Level-Sprache sein), die s ausgibt.

Jetzt können wir leicht alle möglichen Binaries und Programme durchlaufen, sortiert nach Größe. Lassen Sie B_s die Unterliste dieser Binaries sein, die s ausgeben (natürlich ist B_s uncomputable).

Da jeder Satz positiver Ganzzahlen ein Minimum haben muss, muss in B_s ein kleinstes Programm b_min_s vorliegen.

Für welche Sprachen (d. H. Satz von Zeichenfolgen) wissen wir etwas über die Größe von b_min_s? Vielleicht nur eine Schätzung. (Ich kann einige trivialen Beispiele konstruieren, wo ich kann immer noch B_s berechnen und auch b_min_s, aber ich bin interessiert in interessanten Sprachen.)

Quelle

2010-07-16 Albert

Ich erinnere mich an einige sehr clevere Programme aus alten Zeiten, wie zum Beispiel Bootstrap Loader, die sich selbst mehrfach überschrieben haben. Wahrscheinlich könnte das Programm, um eine minimale Gesamtgröße des selbstextrahierenden Programms zu erreichen, irgendwie seinen eigenen Text verwenden - z. B. als eine Quelle von Konstanten. –

Dies ist Kolmogorov complexity, und Sie sind richtig, dass es not computable ist. Wenn dies der Fall wäre, könnten Sie ein paradoxes Programm der Länge n erstellen, das eine Zeichenkette mit der Kolmogorov-Komplexität m> n ausgibt.

Sie können natürlich für gegebene Eingaben b_min_s gebunden. Soweit ich weiß, waren die meisten Bemühungen jedoch Existenznachweise. Zum Beispiel gibt es einen ständigen Wettbewerb um English Wikipedia zu komprimieren.

Quelle

2010-07-16 03:18:19

Ja, genau dieser Preis hat mich auf diese Frage gebracht. :) Solche Wettkämpfe/Versuche geben jedoch nur Hinweise, weil sie für eine bestimmte Beispielschnur niedrigere Grenzen anzeigen. Sie geben keine Antwort auf eine durchschnittliche/reale harte Grenze einer bestimmten Sprache (z. B. XML mit grammatikalisch korrektem Englisch als Inhalt). – Albert

Hier ist eine gute Komprimierungserklärung, die ich für weitere Lektüre empfehlen würde: http://www.mattmahoney.net/dc/dce.html - und auf der Hutter-Seite gibt es einen Link zu http://cs.fit.edu /~mmahoney/compression/textdata.html was auch schön zu lesen ist. – schnaader

Die maximale (durchschnittliche) Komprimierungsrate ist 1: 1.
Die Anzahl der möglichen Eingänge entspricht der Anzahl der Ausgänge.
Es muss sein, um den Ausgang zurück zum Eingang zuordnen zu können.
Um die Ausgabe speichern zu können, benötigen Sie einen Container in der gleichen Größe wie der minimale Container für die Eingabe - mit einer Komprimierungsrate von 1: 1.

Quelle

2010-07-16 04:02:23 Dani

"Die maximale (durchschnittliche) Kompressionsrate ist 1: 1." Was bedeutet das eigentlich? –

Es bedeutet, dass Sie sagen, dass Sie alle möglichen 100-Byte-Strings nehmen und jeden einzelnen komprimieren. Die durchschnittliche Länge Ihrer Komprimierungsausgabe beträgt mindestens 100 Byte. Die durchschnittliche Komprimierung beträgt daher 1: 1 oder schlechter. Natürlich sind reale Daten nicht zufällig, so dass es am besten ist zu sagen, dass er im schlimmsten Fall über die optimale Kompressionsrate spricht. Aber es versucht die Frage in der Überschrift zu beantworten: Die maximal mögliche Kompressionsrate hängt vor allem von den Daten ab. Es beantwortet nicht wirklich den Körper der Frage ... – jjrv

Im Grunde benötigen Sie genügend Informationen, um Ihre ursprünglichen Informationen neu zu erstellen. Ich denke, die anderen Antworten sind hilfreicher für Ihre theoretische Diskussion, aber denken Sie daran.

Quelle

2010-07-16 04:09:13 Chad

Claude Shannon schätzten die Informationsdichte der englischen Sprache irgendwo pro Zeichen in seinem 1951 Papier Prediction and Entropy of Printed English (PDF, 1,6 MB . Bell-Sys. Tech zwischen 0,6 und 1,3 Bits. J (3) p. 50- 64).

Quelle

2010-07-16 10:25:44 phreeza

Hm, ich frage mich, ob Kolmogorov Komplexität mit Shannons Informationsdichte kompatibel ist. Aus meiner Intuition ist Shannon Information nur ein Strom von Bits. Z.B. der Pixelstrom eines Fraktalbildes hat nach Definition von Shannon noch eine hohe Informationsdichte. Unter diesen Umständen frage ich mich, ob 0,6 wirklich eine gute Schätzung ist. Vielleicht für englischen Text, der keine redundanten Informationen enthält. – Albert

Shannon Information gibt eine Aussage über den allgemeinen statistischen Fall, während Kolmogorov Komplexität der Informationsgehalt eines einzelnen Objekts ist. In diesem Beispiel sagt Shannon Information etwas über den durchschnittlichen Charakter in einem englischen Text aus, während die Kolmogorov Komplexität der Informationsgehalt eines bestimmten Textkörpers ist, zB der String s. – phreeza

Aber Shannon war eine wichtige prägende Figur in "Informationstheorie" und Entropie, und letztendlich ist es die Entropie, die hier das Thema ist. ["Shannons Entropie stellt eine absolute Grenze für die bestmögliche verlustfreie Komprimierung jeglicher Kommunikation dar"] (http://en.wikipedia.org/wiki/Entropy_%28information_theory%29) –

Was ist die maximal theoretisch mögliche Kompressionsrate?

Antwort

Verwandte Themen