Nextgen - Kompressionsverfahren

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