Nextgen - Kompressionsverfahren

[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.

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.

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

[Namenloser]

Zitat von himitsu:

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

[BUG]

Hier kann das mal ausprobieren

[gammatester]

Zitat von BUG:

Hier kann das mal ausprobieren

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

[Khabarakh]

Zitat von FredlFesl:

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.

Da gibt's nicht viel zu rechnen . Durch Bijektivität und Schubfachprinzip folgt sofort, dass kein Kompressionsalgorithmus beliebige Daten im Durchschnitt verkleinern kann; er kann sich also nur auf spezielle Daten, solche mit geringer Entropie, konzentrieren und in dieser Teilmenge mehr oder weniger gute Kompressionsraten erzielen.
Da Aphtons Algorithmus aber offensichtlich keine solche Auswahl trifft, garantiere ich, dass er im Durchschnitt, selbst wenn wir von Plaintext-Dateien reden, Daten nur vergrößert .

*wegduck *

[Aphton]

Ja gut, mittlerweile sehe ich das ein.

Sorry für den Blödsinn

[BUG]

Zitat von Aphton:

Sorry für den Blödsinn

Passiert jedem mal