Können mit PRNGs Sachen magisch komprimiert werden?

Diese Idee kam mir als Kind, als ich das Programmieren lernte und PRNGs zum ersten Mal begegnete. Ich weiß immer noch nicht, wie realistisch es ist, aber jetzt gibt es Stapelaustausch.

Hier ist ein 14-jähriges Schema für einen erstaunlichen Komprimierungsalgorithmus:

Nehmen Sie ein PRNG und sortieren Sie es mit seed s, um eine lange Folge von pseudozufälligen Bytes zu erhalten. Um diese Sequenz an eine andere Partei zu übertragen, müssen Sie nur eine Beschreibung des PRNG, den entsprechenden Startwert und die Länge der Nachricht mitteilen. Für eine ausreichend lange Sequenz wäre diese Beschreibung viel kürzer als die Sequenz selbst.

Angenommen, ich könnte den Prozess umkehren. Mit genügend Zeit und Rechenressourcen könnte ich eine Brute-Force-Suche durchführen und einen Samen (und PRNG, oder mit anderen Worten: ein Programm) finden, der meine gewünschte Sequenz erzeugt (sagen wir ein amüsantes Foto von Katzen, die boshaft sind).

PRNGs wiederholen sich, nachdem eine ausreichend große Anzahl von Bits generiert wurde, aber im Vergleich zu "typischen" Zyklen ist meine Nachricht ziemlich kurz, sodass dies kein großes Problem zu sein scheint.

Voila, eine effektive (wenn auch rube-goldbergische) Möglichkeit, Daten zu komprimieren.

Angenommen also:

• Die Sequenz, die ich komprimieren möchte, ist endlich und im Voraus bekannt.
• Ich habe nicht wenig Geld oder Zeit (nur solange eine begrenzte Menge von beiden benötigt wird)

Ich würde gerne wissen:

• Gibt es einen fundamentalen Fehler in der Begründung des Systems?
• Wie kann man diese Art von Gedankenexperimenten normalerweise analysieren?

Zusammenfassung

Oft machen gute Antworten nicht nur die Antwort deutlich, sondern auch, was ich wirklich gefragt habe. Vielen Dank für die Geduld und die ausführlichen Antworten.

Hier ist mein n-ter Versuch, eine Zusammenfassung der Antworten zu geben:

• Der PRNG / Seed-Winkel trägt nichts bei, es ist nur ein Programm, das die gewünschte Sequenz als Ausgabe erzeugt.
• Das Pigeonhole-Prinzip: Es gibt viel mehr Nachrichten der Länge> k als es (Nachrichten erzeugende) Programme der Länge <= k gibt. Einige Sequenzen können also einfach nicht die Ausgabe eines Programms sein, das kürzer als die Nachricht ist.
• Erwähnenswert ist, dass der Interpreter des Programms (Nachricht) unbedingt im Voraus festgelegt wird. Und sein Design bestimmt die (kleine) Teilmenge von Nachrichten, die generiert werden können, wenn eine Nachricht der Länge k empfangen wird.

Zu diesem Zeitpunkt ist die ursprüngliche PRNG-Idee bereits tot, aber es gibt mindestens eine letzte zu klärende Frage:

• F: Könnte ich Glück haben und feststellen, dass meine lange (aber endliche) Nachricht zufällig die Ausgabe eines Programms mit einer Länge von <k Bits ist?

Streng genommen ist es keine Zufallsfrage, da die Bedeutung jeder möglichen Nachricht (Programm) im Voraus bekannt sein muss. Entweder es ist die Bedeutung einiger Nachricht von <k Bits oder ist es nicht .

Wenn ich eine zufällige Nachricht von> = k Bits zufällig wähle (warum sollte ich das tun?), Hätte ich auf jeden Fall eine verschwindende Wahrscheinlichkeit, sie mit weniger als k Bits senden zu können, und eine fast Gewissheit, nicht senden zu können es überhaupt mit weniger als k Bits.

OTOH, wenn ich eine bestimmte Nachricht von> = k Bits aus jenen auswähle, die die Ausgabe eines Programms von weniger als k Bits sind (vorausgesetzt, es gibt eine solche Nachricht), dann nutze ich tatsächlich die Bits, die bereits an das übertragen wurden Empfänger (das Design des Interpreters), der als Teil der übertragenen Nachricht zählt.

Endlich:

• F: Was ist das ganze Geschäft mit Entropie / Kolmogorov-Komplexität ?

Letztendlich erzählen uns beide dasselbe, wie das (einfachere) Pigeonhole-Prinzip uns sagt, wie viel wir komprimieren können: vielleicht gar nicht, vielleicht einige, aber sicher nicht so viel, wie wir uns vorstellen (es sei denn, wir betrügen).

Du hast ein geniales neues Komprimierungsschema, was? Alles kar...

♫ Lass uns alle spielen, das Entropiespiel ♫

Um ganz einfach zu sein, gehe ich davon aus, dass Sie Nachrichten mit genau Bits für einige feste komprimieren möchten . Sie möchten es jedoch für längere Nachrichten verwenden können, daher müssen Sie Ihre erste Nachricht von der zweiten unterscheiden (es kann nicht mehrdeutig sein, was Sie komprimiert haben).$n$$n$

Ihr Schema besteht also darin, eine PRNG / Familie so zu bestimmen, dass Sie, wenn Sie beispielsweise komprimieren , einfach eine Zahl schreiben , die eine vorberechnete (und gemeinsam genutzte) Seed / PRNG-Kombination identifiziert, die diese Bits danach erzeugt Abfragen. In Ordung. Wie viele verschiedene Bitketten der Länge gibt es? (Sie haben n Auswahlmöglichkeiten zwischen zwei Elementen; und ). Das heißt, Sie müssen dieser Combos berechnen . Kein Problem. Sie müssen jedoch in binär schreiben, damit ich es lesen kann. Wie groß kann bekommen? Nun, es kann so groß wie$01000111001$$k$$n$$n$$2^n$$0$$1$$2^n$$k$$k$$2^n$. Wie viele Bits brauche ich, um auszuschreiben ? .$2^n$$\log{2^n} = n$

Hoppla! Ihr Komprimierungsschema benötigt Nachrichten, solange Sie komprimieren!

"Haha!", Sagst du, "aber das ist im schlimmsten Fall! Eine meiner Nachrichten wird auf abgebildet , was nur Bit zur Darstellung benötigt! Sieg!"$0$$1$

Ja, aber Ihre Nachrichten müssen eindeutig sein! Wie kann ich gefolgt von von ? Da einige Ihrer Schlüssel die Länge , müssen es alle sein, sonst kann ich nicht sagen, wo Sie begonnen und aufgehört haben.$1$$0$$10$$n$

"Haha!", Sagst du, "aber ich kann nur die Länge des Strings zuerst in binär setzen! Das muss nur bis , was durch Bits dargestellt werden kann! Also wird meiner jetzt ein Präfix vorangestellt Nur Bits, ich gewinne noch! "$n$$\log{n}$$0$$\log{n}$

Ja, aber diesen wirklich großen Zahlen werden jetzt Bits vorangestellt . Ihr Komprimierungsschema hat einige Ihrer Nachrichten noch länger gemacht! Und die Hälfte aller Ihrer Nummern beginnt mit , sodass die Hälfte Ihrer Nachrichten so viel länger ist!$\log{n}$$1$

Anschließend werfen Sie weitere Ideen aus, z. B. ein abschließendes Zeichen, zippen die Zahl und komprimieren die Länge selbst. In all diesen Fällen ist die resultierende Nachricht jedoch nur länger. Tatsächlich wird für jedes Bit, das Sie in einer Nachricht speichern, eine andere Nachricht als Antwort länger. Im Allgemeinen werden Sie sich nur um die "Kosten" Ihrer Nachrichten kümmern. Wenn Sie einige kürzer machen, werden andere nur länger. Sie können wirklich nicht verschiedene Nachrichten in weniger Platz einpassen, als binäre Zeichenfolgen der Länge schreiben .$2^n$$2^n$$n$

"Haha!", Sagst du, "aber ich kann einige Nachrichten als" dumm "auswählen und sie als illegal kennzeichnen! Dann muss ich nicht bis , weil ich nicht so viele Nachrichten unterstütze!" "$2^n$

Du hast recht, aber du hast nicht wirklich gewonnen. Sie haben gerade die Anzahl der von Ihnen unterstützten Nachrichten verkleinert. Wenn Sie nur und als gesendete Nachrichten unterstützt haben, können Sie auf jeden Fall nur den Code , , der genau mit dem übereinstimmt, was ich gesagt habe. Hier ist . Die tatsächliche Länge der Nachrichten ist nicht wichtig, es ist, wie viele es gibt.$a=0000000011010$$b=111111110101000$$a\rightarrow 0$$b\rightarrow 1$$n=1$

"Haha!", Sagst du, "aber ich kann einfach feststellen, dass diese dummen Botschaften selten sind! Ich mache die seltenen groß und die gewöhnlichen klein! Dann gewinne ich im Durchschnitt!"

Ja! Herzlichen Glückwunsch, Sie haben gerade Entropie entdeckt ! Wenn Sie Nachrichten haben, bei denen die te Nachricht die Wahrscheinlichkeit , gesendet zu werden, können Sie Ihre erwartete Nachrichtenlänge auf die Entropie von diesem Reihe von Nachrichten. Das ist eine Art seltsamer Ausdruck, aber alles, was Sie wirklich wissen müssen, ist, dass er am größten ist, wenn alle Nachrichten gleich wahrscheinlich sind, und kleiner, wenn einige häufiger sind als andere. Im Extremfall, wenn Sie wissen, dass im Grunde jede Nachricht . Dann können Sie diesen supereffizienten Code verwenden: ,i p i H = ∑ n i = 1 p i log ( 1 / p i ) a = 000111010101 a → 0 x → 1 x 1 H $n$$i$$p_i$$H = \sum_{i=1}^np_i\log(1/p_i)$$a=000111010101$$a\rightarrow0$$x\rightarrow1x$Andernfalls. Dann ist Ihre erwartete Nachrichtenlänge im Grunde genommen , was fantastisch ist und der Entropie sehr nahe kommt . Allerdings ist eine Untergrenze, und Sie können es wirklich nicht schlagen, egal wie sehr Sie es versuchen.$1$$H$$H$

Alles, was behauptet, die Entropie zu schlagen, liefert wahrscheinlich nicht genügend Informationen, um die komprimierte Nachricht eindeutig abzurufen, oder ist einfach falsch. Entropie ist ein so leistungsfähiges Konzept, dass wir die Laufzeit einiger Algorithmen damit nach unten (und manchmal sogar nach oben) einschränken können, denn wenn sie sehr schnell (oder sehr langsam) laufen, müssen sie etwas tun, das die Entropie verletzt .

Es gibt binäre Strings der Länge kleiner als , und binäre Strings der Länge genau . Dies bedeutet, dass es unabhängig von Ihrem Komprimierungsalgorithmus eine Zeichenfolge geben muss, die überhaupt nicht komprimiert werden kann, nur weil die Zuordnung von der ursprünglichen Zeichenfolge zur komprimierten Zeichenfolge injektiv sein muss (eins zu eins). Dies ist die treibende Kraft hinter vielen Anwendungen der Kolmogorov-Komplexität.N 2 N$2^N-1$$N$$2^N$$N$

Im wirklichen Leben wissen wir oft etwas über die Sequenz, die wir komprimieren, sagen, es ist eine Stimme oder ein Bild. Im Fall einer verlustfreien Komprimierung zeigt Shannons Quellcodierungssatz, dass die optimale Komprimierungsrate gleich der Entropie der Quelle ist. Für die verlustbehaftete Codierung gibt es andere Theoreme in der Informationstheorie (Rate-Distortion-Theorie). Selbst in diesem Fall ist die Datenkomprimierung begrenzt.

Stellen Sie sich vor , dass Ihre Samen Länge . Ihr PRNG ist eine deterministische Funktion des Seeds und gibt maximal verschiedene Folgen der Länge . Es gibt von diesen, so dass Ihr Schema nicht funktionieren wird, wenn es nicht darauf zurückgreift, nur den gesamten Bit-String zu senden, wenn es kein entsprechendes .k 2 k n 2 n n $s$$k$$2^k$$n$$2^n$$n$$s$

(Wie eine andere Antwort vermerkt, geschieht dies für jede Komprimierungsfunktion, die Sie überhaupt auswählen.)

Neben anderen bereits beantworteten Punkten möchte ich nur diesen Link hinzufügen: https://www.schneier.com:443/blog/archives/2009/09/the_doghouse_cr.html

Die jährliche Energieabgabe unserer Sonne beträgt nun etwa 1,21 × 10 ^ 41 Erg. Dies reicht aus, um auf unserem idealen Computer etwa 2,7 × 10 ^ 56 einzelne Bitänderungen zu erzeugen. genug Zustandsänderungen, um einen 187-Bit-Zähler durch alle seine Werte zu führen. Wenn wir eine Dyson-Kugel um die Sonne bauen und ihre gesamte Energie 32 Jahre lang ohne Verluste einfangen würden, könnten wir einen Computer mit Strom versorgen, um bis zu 2 ^ 192 zu zählen. Natürlich hätte es nicht die Energie übrig, nützliche Berechnungen mit diesem Zähler durchzuführen.

Wenn Sie also nur iterieren (nicht vergleichen ...), um eine gültige 187-Bit-Konstellation Ihrer gewünschten Daten zu finden, benötigen Sie unter (nicht erreichbaren) idealen Bedingungen mehr Energie als die Sonne über ein Jahr abgibt.

Ein sehr schneller Beweis, dass es keinen Universalkompressor geben kann. Nehmen wir an, Sie erstellen eine und komprimieren eine Eingabe. Komprimieren Sie nun iterativ die Ausgabe Ihres Programms. Wenn Sie die Größe immer verringern können, wird sie bei jedem Schritt kleiner, bis Sie auf 1 Bit reduziert sind.

Sie könnten argumentieren, dass die Ausgabe Ihres Algorithmus möglicherweise so strukturiert ist, dass sie nicht mehr komprimiert werden kann, aber Sie könnten vor der erneuten Komprimierung einfach ein deterministisches Shuffle * anwenden.

Fußnote: Einige deterministische Shufflings helfen tatsächlich bei einigen Komprimierungsschemata: http://pytables.github.io/usersguide/optimization.html?highlight=shuffling#shufflingoptim

Die Verwendung eines PRNG für "Komprimierung" ist grundsätzlich in einer Situation nützlich: Wenn es erforderlich ist, eine "zufällige" Datenmenge zu verwenden und kompakt aufzuzeichnen, welche Daten verwendet wurden. Die meisten Pseudozufallsgeneratoren können nur einen winzigen Bruchteil möglicher Sequenzen erzeugen. Wenn man jedoch nur eine kleine bis mittlere Anzahl von "zufälligen" Sequenzen benötigt, ist der Bruchteil möglicher Sequenzen, die ein PRNG erzeugen kann, oft mehr als ausreichend.

Wenn die Sequenz von Daten, die man speichern möchte, zufällig übereinstimmt, was ein bestimmter PRNG bei gegebenem richtigen Startwert erzeugen würde, kann das Speichern des Startwerts eine kompakte Alternative zum Speichern der Daten sein. Sofern die Datenquelle nicht so beschaffen ist, dass solche Übereinstimmungen wahrscheinlich auftreten, sind sie jedoch so selten, dass sich eine Suche nach ihnen nicht lohnt.

Erwägen Sie Folgendes, um die Kakophonie der Antworten zu erweitern, die erklären, warum es einige Zeichenfolgen gibt, die aufgrund der per Definition injektiven Natur der Dekomprimierung und des begrenzten Universums komprimierter Zeichenfolgen, aus denen Nachrichten dargestellt werden sollen, nicht komprimiert werden können: Die meisten Zeichenfolgen können nicht komprimiert werden, da es sehr viel mehr ungeordnete Zeichenfolgen mit hoher Entropie als solche mit niedrigerer Entropie und Struktur gibt. Dies führt zu der Bedingung, die wir in der Praxis sehen: Komprimierung ist die meiste Zeit nützlich, da die Nachrichten wir Am häufigsten sind diejenigen, die komprimiert werden möchten, die ein Aliquot von Ordnung und Struktur besitzen und daher Teil des sehr viel kleineren Universums von Objekten mit niedrigerer Entropie sind. Dies bedeutet, dass durch Auswahl einer geeigneten Ausgabelänge Wir können alles im kleineren, strukturierten Universum komprimieren. Der hier verwendete Begriff "strukturiert", "Entropie" und "geordnet" ist bewusst ungenau, um die subjektiven Definitionen der Semantik und Nützlichkeit von Nachrichten widerzuspiegeln, die wir möglicherweise komprimieren möchten.

Und als direkte Antwort auf die Anfrage des Fragestellers: * Ja, Sie könnten natürlich einfach Glück haben und feststellen, dass die Ausgabe Ihres PRNG genau die Nachricht ist, die Sie komprimieren möchten Die eigentliche Eigenschaft, die ein PRNG auszeichnet, nämlich die Fähigkeit, eine (fast) endlose Vielfalt unterschiedlicher Saiten zu produzieren, macht es gleichzeitig unwahrscheinlich, Ihre zu produzieren.

Natürlich können Sie diese Unwahrscheinlichkeit abmildern, indem Sie mit einem PRNG über einen "Domänengraphen" von Wort zu Wort-Übergängen navigieren und die Wahrscheinlichkeit, dass die Nachricht angezeigt wird, erheblich erhöhen. Außerdem müssen Sie jetzt den Domänengraphen zur komprimierten Nachricht hinzufügen Länge.