Nextgen - Kompressionsverfahren

[Aphton]

Ich bin mir sicher, dieser Gedanke ist bestimmt schon einigen gekommen, aber ich will es hier mal verbalisieren bzw. niederschreiben und eure Meinung dazu hören

Die Zahl PI ist irrational. Irrational heißt, sie kann nicht durch das Verhältnis zweier natürlichen Zahlen dargestellt werden. Weiters sind irrationale Zahlen unendlich lang und unperiodisch (Quelle).

Diese Eigenschaften haben etwas wunderbares an sich. Somit kann man sagen, dass in der Zahl PI oder in jeglich anderen irrationalen Zahl alles drinnen steckt - informationstechnisch betrachtet; also im Grunde alle möglichen Zahlenfolgen.

Damit meine ich man könnte zb. nach dem String "Hallo" (Ascii 72-97-108-108-111) suchen und die Indizes speichern. Also angenommen, diese Zahlenfolge befindet sich in PI bei der Stelle 5232241 und ist 5 Stellen lang, so müsste man nur diese zwei Zahlen speichern.

Man kann das natürlich noch ausweiten und kann somit gleich nach größeren Datenströmen (Spiele/Videos/Musik/...) suchen. Hat man einmal diese Folge gefunden, speichert man, wie schon zuvor erklärt, die Indizes und hat eine unglaubliche Komprimierung dadurch erreicht - denn die Datei lässt sich ja durch Rückberechnung der irrationalen Zahl zurückberechnen! Es könnte einzig und allein wegen dem hier problematisch werden - wenn die Indizes (Zahlen) größer sind als die Datei selbst.

NATÜRLICH ist mir klar, dass dies übelst lang dauern kann und mit heutigen Mitteln kaum praktisch einsetzbar ist, aber wer weiß, vlt. in ferner Zukunft mit Quantencomputer oder Ähnlichem?!

Was denkt ihr euch so?

[Namenloser]

Die Idee hatte ich auch schon. Natürlich ist das nur eine Gedankenspielerei und kaum praxistauglich. In Einzelfällen sind damit vielleicht gute Kompressionsraten möglich, in der Regel wird man aber sehr lange suchen müssen, bis man die jeweilige Stelle findet → Zahl wird extrem groß, braucht damit viele Stellen und nimmt dann wahrscheinlich mindestens genau so viel Platz weg wie die eigentlichen Daten.

[generic]

Im Prinzip nutzt du ein vordefiniertes Wörterbuch, welches bereits beim entpacken vorhanden ist.

Dein Beispiel hingt aber.
Denn 5232241 würdest du als Integer ablegen müssen 4 Byte. Plus die Länge 5 in 1 Byte = 5 Byte = Length(HALLO)

Wird die Position größer, dann musst du diese evtl. als int64 ablegen - 8 Byte.

Also musst du um überhaupt komprimieren (mit Gewinn) zu können ca. 10 Bytes am Stück finden im Wörterbuch.
Je länger umso unwahrscheinlicher, dass du es findest.

Außerdem müsstest jedes mal PI in den benötigten Stellen berechnen.

[WM_CLOSE]

Nehmen wir mal das Beispiel, wenn eine Kombination GAR NICHT vorkommt.
Was passiert dann? Auch das Infinite Monkey - Theorem hat diese Ausnahme, auch wenn die Wahrscheinlichkeit gegen null geht.

Dann muss man noch mit einbeziehen, dass es schon mehr Speicherplatz braucht um Pi bis zur 5232246. Stelle zu speichern (berechnen kann man ja vergessen)als die meisten Zip Archive heute verbrauchen.

EDIT: Zu langsam.

[mleyen]

Zitat von generic:

Im Prinzip nutzt du ein vordefiniertes Wörterbuch, welches bereits beim entpacken vorhanden ist.

Jap, eines mit unvorstellbar großem Overhead, dann doch lieber 0123456789101112...∞

[Aphton]

Ne überhaupt nicht. Also das war ja nur ein Beispiel.
Nehmen wir nen Aufsatz, bestehend aus 500 Wörtern mit jeweils durchschnittlicher Wortlänge von 5 Zeichen. Dadurch hätte man (ohne Satz- & Leerzeichen) 2500 Zeichen.
Diese findet man bestimmt iwo in PI. Und ich hab mir auch überlegt - für den Fall, dass der Index viel zu groß wird - was ist, wenn man ne kurzschreibweise verwendet wie zb. x * 10^y + z oder soetwas halt?!
Oder direkt den Index komprimiert - wobei wir dann wieder beim Anfangsproblem wären, wenn der Index gleichgroß bis größer ist, als die ursprüngliche Datei..

Hmm...

[Memnarch]

Das ist wie: Ich bestimme wieviele buchstaben ein Buch X haben soll, und gehe dan alle Buchstabenkombos durch. Dadurch erhalte ich der länge entsprechend ebenfalls sämtliche werke der Menschheit, und dinge die noch geschrieben werden, und welche die nie geschrieben werden.

Hier rennt mir aber der HDD speicher davon.

Bei dem beispiel mit PI müsste erstmal eine Unglaublich große zahl gespeichert werden bzw überhaupt erstmal berechnet. DANN:

Um den Wert eines Bytes unserer datei zu erhalten, müssen wir 3 zahlen aus der nachkomma folge nutzen.
Nehmen wir mal ein Spiel mit 12GB, dan müsste ich eine PI zahlenkolone von 36GB finden die exakt genauso ist. ein 36GB datenstream kann 309.237.645.312 Kombinationen anehmen. Du wirst deine 12GB daten, also in ca 1.11325552 × 10^13 GB Daten suchen müssen o.O
Glaube das sind 10,125 Zetabyte


MFG
Memnarch

[gammatester]

Zitat von Aphton:

Die Zahl PI ist irrational. Irrational heißt, sie kann nicht durch das Verhältnis zweier natürlichen Zahlen dargestellt werden. Weiters sind irrationale Zahlen unendlich lang und unperiodisch (Quelle).

Diese Eigenschaften haben etwas wunderbares an sich. Somit kann man sagen, dass in der Zahl PI oder in jeglich anderen irrationalen Zahl alles drinnen steckt - informationstechnisch betrachtet; also im Grunde alle möglichen Zahlenfolgen.

Damit meine ich man könnte zb. nach dem String "Hallo" (Ascii 72-97-108-108-111) suchen und die Indizes speichern. Also angenommen, diese Zahlenfolge befindet sich in PI bei der Stelle 5232241 und ist 5 Stellen lang, so müsste man nur diese zwei Zahlen speichern.

Das ist mathematischer Unsinn. Erstens meinst Du wahrscheinlich transzendente Zahlen und nicht irrationale. Zweistens gilt das auch noch nicht einmal für transzendente Zahlen. Die Liouvillesche Zahl ist transzendet, hat aber in ihrer Dezimaldarstellung nur 0 und 1! Aber vielleicht meinst Du ja auch Normale Zahlen?

[Aphton]

Aha
Dann habe ich etwas grundlegend falsch verstanden!

[Edit]
gammatester - also du meinst, irrationale Zahlen wiederholen sich ab einer bestimmten Stelle?
[/Edit]

@Memnarch: Das ist falsch so.
Du musst ja nicht wirklich jede Kombinationsmöglickeit im Speicher behalten und auch nicht alle bis zum Index berechnette Stellen der irrationalen Zahl! Man sollte das natürlich ein bisschen optimierter angehen!

Der Algorithmus sähe ja ca. so aus:

Code:

wiederhole...
1. Berechne nächste Stelle der Irrationalen Zahl (Stellenindex = j)
2. Vergleiche Zahl mit Datenstrom[i]
-a) sind sie gleich, inkrementiere i
-b) sind sie nicht gleich, setze i auf 0
bis i = Größe_der_Datei
Startindexindex = j - i

(Edit - nun, es muss jeweils 1 Byte gebildet werden, aber vom Prinzip her sollte es so wie oben vereinfacht dargestellt - funktionieren)

[Memnarch]

NEIN...was ich berechnet habe ist der geschätze speicher den die PI zahl belegt, damit du ne chance hast den 12gb stream index darin zu FINDEN


PS: hab mcih übrigens verechnet... 36GB können 2^(309237645312) kombinationen annehmen... googlecalculator verreckt hier.... Dementsprechen sind die 10.125 Zetabyte ZU KLEIN



MFG
Memnarch