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 :D

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:

Zitat von generic (Beitrag 1107730)

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:

Zitat von Aphton (Beitrag 1107726)

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 :shock:
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 :twisted:



MFG
Memnarch

[implementation]

Du musst Pi auch nicht speichern.
Während des Berechnens kann man meines Wissens nach die meisten vorhergegangenen Ziffern wieder verwerfen.

[Aphton]

Der PI-Speicher belegt niemals mehr Speicher als 1 Byte!
>.>

Edit:

Code:

3.141592653
  ^ (Schritt 1)
   ^ (Schritt 2)
    ^ (Schritt 3)
...(Schritt n)

Bei Schritt 1 wird die Zahl 1 berechnet, bei Schritt 2 die Zahl 4 usw. usf!
(Siehe Algorithmus bei meiner letzten Nachricht [neu reineditiert]!)

[Memnarch]

Aphton: Wenn du 36GB daten finden willst, musst du dan schon wenigstens 36GB für PI aufwenden.

Dann werden meine <wazillionen irgendwas) zetabyte zwar nicht gespeichert, aber im schlimmsten fall werden die durchgerechnet. bis ein PC das schaft, sind die Festplatten so groß, das keiner auch nur im entferntesten darauf kommen würde schlappe 12GB (deine eigentlichen daten) zu komprimieren.

PS: gut du kannst auch nen offset nehmen und dan die aktuelle pi-stelle mit dem wert an offset X in deinen 12Gb vergleichen, bzw du brauchst 3byte pi speicher weil du 3 ziffern aus PI nimmst und daraus dein Byte formst.

MFG
Memnarch

[Aphton]

:(
Ich glaube, dass entweder ICH dich nicht verstehe, oder DU mich nicht verstehst.
Es stimmt zwar, dass alle 36 GB berechnet werden müssen, sie müssen aber sich nicht gleichzeitig im Speicher befinden (also Seitens PI).

Eig. auch Seitens Datei - per Filestream kann man ja schön Chunks einlesen. Also möglich ist das auf jeden Fall mit heutigen Mitteln. Nur kann es eben verdammt lange dauern! Deshalb meinte ich auch ferner Zukunft :P

Edit: Übrigens, falls ich - so gammatester - die irrationalen Zahlen falsch verstanden habe, kann man das natürlich über den Haufen hauen! Ich warte noch auf seine Antwort ^_^

[Memnarch]

@Aphton: ich hab mich doch bereits korrigiert. für den Fall dass man PI berechnen kann indem man nur die vorherigen zahl betrachtet(was ich bezweifle), reichen 3 byte..wenn nicht, dann trifst du auf meine watzillionen ZetaBytes ;) (den dann muss pi im ganzen berechnet werden, was aus meiner sicht der mathematischen kenntnisse mehr sinn macht)


MFG
Memnarch

[Daniel]

Schön, dass wir bald 'nen 64bit-Compiler haben. :mrgreen: Den könntest Du brauchen. ;-)

[gammatester]

Zitat:

Zitat von Aphton (Beitrag 1107736)

Aha :shock:
gammatester - also du meinst, irrationale Zahlen wiederholen sich ab einer bestimmten Stelle?

Das habe ich nicht gesagt, und es kann natürlich auch nicht richtig sein, da ja alle transzendeten Zahlen auch irrational sind. Aber: Nicht-transzendete Irrationalzahlen (also algebraische Zahlen) sind abzählbar, und können deshalb auch keine transzendenten Zahlen in ihrer Entwicklung enthalten. Auch haben zB alle quadratischen Irrationalzahlen (sqrt(2) usw) periodische Kettenbruchentwicklungen.

[Aphton]

@Memnarch - da ist etwas dran, aber ich denke es gibt iterative Verfahren, bei denen sich laufend der Zustand bestimmter Variablen verändert und mit einer bestimmten Berechnung eben die nächste Stelle sich ermitteln lässt. Also ich hoffe, dass man nicht wirklich alle Stellen im Speicher haben muss.

@Daniel - lol, 64 Bit Compiler wird alle Probleme lösen!

@Gammatester - es geht hier aber nun um irrationale Zahlen und laut Wikipedia sind sie nicht periodisch! (Also als Gegensatz zu rationalen Zahlen, die periodisch sind bzw. sein können)

Edit:

Zitat:

Zitat von Wikipedia

Im Gegensatz zu rationalen Zahlen, die als endliche oder periodische Dezimalzahlen dargestellt werden können, sind irrationale Zahlen solche, deren Dezimaldarstellung nicht abbricht und nicht periodisch ist

Edit2:

Zitat:

Zitat von gammatester

Das habe ich nicht gesagt

Wenn du das nicht gemeint hast, ist mir alles andere, was nicht wirklich etwas mit dem Thema zu tun hat, diesbezüglich eigentlich egal :P

[Memnarch]

@Aphton:

Es gibt wohl möglichkeiten PI Iterativ zu berechnen, aber dafür wird JEDESMAL der komplett vorangegangene wert benötigt(das ist halt Mathematik^^)

http://en.wikipedia.org/wiki/Pi

WatZillionenZetaPyte-Armee for the win :twisted:


MFG
Memnarch

[Aphton]

Ok. Nun, nicht wirklich.
Wer weiß, was "ferner" Zukunft alles mit sich bringt :P

Edit: (Ich mit meinen Edits xD)
Gibts wirklich keine iterativen Algorithmen, die die einzelnen Stellen berechnen können, ohne alle Zahlen davor kennen zu müssen?!

[Memnarch]

Die Zukunft wird vieles bringen, und vieles vernichten, Aber Mathematik ist in unserer Welt konstant.

[Aphton]

LOL xDDD

Die einzige Konstante, die ich kenne, ist der ewige Fluss der Veränderung!

Nun gut, es halten nicht viele Viel von dem hier. Wie dem auch sei :) Danke für die Beteiligung :D

[Memnarch]

Selbst wenn du das was du mit PI machen willst tatsächlich erreichen kannst, Die zu Benötigte PI-Größe wird immer um ein gigantisches größer sein, als die daten die wir komprimieren wollwn. Dementsprechend wird das wohl (meiner meinung nach) niemals in moderater geschwindigkeit möglich sein.

Stell dir vor du kannst in 10 Jahren 12GB damit komfortable in sagen wir mal 1h berechnen(mal sehr großzügig), dan sind die speichermengen die man in 10 jahren aber komprimieren möchte ebenso angewachsen. Das wird ein ziemlich mieser Kreislauf.


MFG
Memnarch

[Aphton]

Auch wahr..

Man kann da höchstens den Datenstrom in kleinere Blöcke aufteilen, da ja dadurch die Wahrscheinlichkeit gesteigert wird, dass die Folge gefunden wird...

[Memnarch]

Das stimmt wohl.

Es fragt sich nur: wenn ich eine zeichenkette von XByte länge suche, wie groß muss dann der indexspeicher sein wenn ich vom worstcase ausgehen?


Also wenn ich das gerade im Kopf richtig überschlagen habe ist der benötigte Indexspeicher größer wie der gesuchte speicher im worstcase szenario.

EDIT: das kommt dahei weil du für den gesuchten speicher die anzahl der möglichen kombinationen berechnen musst

Also:

2^(ByteZahl * 8) und das mit der Bytezahl des gesuchten speichers multiplizieren musst.
Dan hasst du den Maximalwert für den Index wen jede Kombination auf der strecke ein unicat ist.
Und dieser Wert passt nicht in dieselbe länge wie der gesuchte Bytestream.


MFG
Memnarch

[Deep-Sea]

Unabhängig von der Sinnhaftigkeit des Vorhabens an sich, wollte ich der Vollständigkeit halber noch mal kurz auf die BBP-Formel hinweisen :lol:

Zitat:

Algorithmus [...] der eine beliebige Ziffer der Darstellung von Pi im Hexadezimalsystem bestimmen kann, ohne die vorherigen Ziffern zu benötigen.

[Aphton]

o_O

[himitsu]

Memnarch stellt einfach einen Webservice bereit, wo er die ersten paar Zentilliarden Stellen von Pi, als eine Art vorberechnete Rainbowtable, bereitstellt.
Dann kann der "Algorithmus" den ja nutzen, um ganz schnell komprimieren zu können. :mrgreen:

Notfalls muß man ja nicht unbedingt die 12 GB als ein Stück suchen, sondern könnte es auch aufteilen und man muß dann nicht so rießige Teile finden.

[FredlFesl]

Wer sagt denn, das der Index immer weniger Stellen hat, als die zu packende Information?
Wenn ich z.B. einen 20 Byte langen String erst an einer Stelle finde, die > 2^(160) ist, hab ich auch nichts gewonnen.

Interessant wäre eine Berechnung, wie hoch die Wahrscheinlichkeit ist, in einer zufälligen Folge von Zahlen eine bestimmte Ziffernfolge zu finden, deren Position mit weniger Bits dargestellt werden kann, also die Ziffernfolge selbst.

[himitsu]

Je größer der Wert/die Daten, um so kleiner die Wahrscheinlichkeit.

Du brauchst ja nur mal prüfen, wie lang PI sein muß, damit z.B. alle möglichen Kombinationen eines 1 MB-Blocksdrin vorkommen,
dann kannst'e für alle Blöcke bis 1 MB die minimale Wahrscheinlichkeit ausrechnen.


Ein Byte wirst'e wohl schon in den ersten 1000 Nachkommastellen finden können. :)
Falls du PI Hexadezimal darstellst, bzw. im Zweierkomplement (kommt wohl auf's Selbe raus, wenn die Bitreihenfolge die Gleiche ist),
und man den Index nicht auf die Dezimalstellem oder ganze byte, sondern Bit festlegt, dann reichen wohl auch schon knapp 100-200 dezimalstellen aus.



Du könntest die gefundenen Indize in PI ja noch so umsortieren, daß es oftmals einen kleineren Index ergibt, als Daten gesucht werden.
Dann brauchst'e nur noch eine klitzekleine Umrechnungstabelle, neben PI. :stupid:

Wo ist eigentlich Hagen?
Der hätte bestimmt schon einen Algo dafür.

[Namenloser]

Zitat:

Zitat von himitsu (Beitrag 1108210)

Wo ist eigentlich Hagen?
Der hätte bestimmt schon einen Algo dafür.

Hagen sitzt seit Tagen in seiner Wohnung und lacht sich über unsere Naivität schlapp :stupid:

[BUG]

Hier kann das mal ausprobieren :mrgreen:

[gammatester]

Zitat:

Zitat von BUG (Beitrag 1108275)

Hier kann das mal ausprobieren :mrgreen:

Ich hatte ja schon in meinem Beitrag #8 auf die Bedeutung von normalen Zahlen für diese Thematik hingewiesen (was aber für den TE nicht ausdrücklich nicht interessant war). MW ist allerdings die Normalität von Pi noch nicht bewiesen, und die Seite leitet die Statistik ein mit "Assuming pi is normal, we have the following probabilities".

Aber selbst wenn das alles der Fall wäre, hätte man ja noch keinen konstruktiven Algorithmus.

[himitsu]

Vielleicht als Backupverfahren?

Man schickt seine Dateien an das Speichercenter
und bekommt von denen eine NameID+Dateinummer.


Frank wurde an Position $08C30EF0 gefunden, also für 5 Buchstaben brauch ich jetzt nur noch 3,5 Byte zum speichern :stupid:
Aber sobald mein Nachname in der Datei drinsteht, war's das dann wohl und man findet nicht so schnell etwas.
> string does not occur in first 4 billion binary digits of pi

[Teekeks]

Bei mir genauso ^^
Vorname: Gefunden, Nachname? nö!

[FredlFesl]

Dann eignet sich das Verfahren wohl nur für Vornamen.
Erstaunlich:
Die Zahl PI enthält alle Vornamen, jedoch keine Nachnamen. Sollte uns das nicht zu denken geben? :stupid:
Wer steckt dahinter? 2012? Maya? Illuminaten?

[Aphton]

Schön, dass euch meine Naivität so viel Spaß macht, aber ich kann nicht wirklich darüber lachen =\

Ich habe die Frage ehrlich gestellt. Ich habe auch niemals gemeint, es sei schon heute möglich.

Weiters war es vor vielen Jahren auch nicht wirklich möglich, bzw. sehr mühselig, so viele Stellen der Zahl PI zu berechnen, was uns heutzutage ja nicht wirklich schwer fällt!

Lasst es bitte >.>
Haut nicht den naiven Visionär :P

[FredlFesl]

Moment, so war das nicht gemeint, mein Kommentar ging eher in Richtung Teekeks und himitsu.

Prinzipiell ist das Verfahren doch denkbar und nicht gerade abwegig.

Wenn man heute schon die N'te Stelle von PI ausrechnen kann, ohne die N-1'ten Stellen davor zu kennen, könnte man auch irgendwann eine Formel dafür finden,
die Position einer Folge X1,X2...Xn in PI zu finden. Dann wäre dein Verfahren marktreif.

[implementation]

Mein Nachname kommt vor :mrgreen:
Das heißt: Ich bin der Illuminat und Schuld daran, dass eure nicht vorkommen.

[FredlFesl]

"lementation" ist kein Nachname. :mrgreen: