Nextgen - Kompressionsverfahren

[Khabarakh]

Zitat:

Zitat von FredlFesl (Beitrag 1108208)

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 :stupid:*

[Aphton]

Ja gut, mittlerweile sehe ich das ein.

Sorry für den Blödsinn :|

[BUG]

Zitat:

Zitat von Aphton (Beitrag 1108451)

Sorry für den Blödsinn :|

Passiert jedem mal :zwinker:

[FredlFesl]

Zitat:

Zitat von Khabarakh (Beitrag 1108436)

... dass kein Kompressionsalgorithmus beliebige Daten im Durchschnitt verkleinern kann; er kann sich also nur auf spezielle Daten, solche mit geringer Entropie, konzentrieren ...
Da Aphtons Algorithmus aber offensichtlich keine solche Auswahl trifft, ...

Spielverderber!
Der Aphton-Pi-Komprimator wäre für einen Fall der beste Algorithmus weit und breit und nicht zu toppen: Als Nachkommastellenvonpikomprimierer :stupid:
Dann leg gleich noch den Aphton-e-Komprimator nach.

[Memnarch]

Zitat:

Zitat von FredlFesl (Beitrag 1108208)

Wer sagt denn, das der Index immer weniger Stellen hat, als die zu packende Information?

Ich hatte bereits darauf hingewiesen dass die wahrscheinlichkeit, dass der für den Index benötigte speicher größer als der gesuchte Stream ist, gefährlich groß ist ;)


MFG
Memnarch

[gammatester]

Um meinem Namen gerecht zu werden, habe ich die Testseite mal gamma-getestet. Ergebnis: Unklar! Die Hex-Darstellung von Pi beginnt mit 3.243F6A8885A308D313198A2E0. Also sollte man erwarten, daß Hex 3 bei 1 (oder 0) und Hex 243 bei 2 (oder 1) gefunden wird. Ergebnisse:

Code:

search string = "3"
 4-bit binary equivalent =   0011
search string found at binary index =  2515296752
903d3f6328baab252dbd3000000afee7dbd393887dff7f24
hex string:                     3

Code:

search string = "243"
12-bit binary equivalent =   001001000011
search string found at binary index =  3278825488
hex pi    : f1067d584f402f9edfce2430000bf80de0c8a8952b1bf586
hex string:                     243

Alle einzelnen Hex-Ziffern werden erst bei Offsets von einigen Zillionen gefunden, also müssen wahrscheinlich die ersten Prä-Zillionen gespeicherten/errechneten Ziffern aus UHZs (Unbekannte Hex-Ziffern) bestehen. Da die verlinkte Info/News-Seite nicht erreichbar ist ('Page not found'), kann man nur spekulieren, was dahinter steckt. Aber vielleicht haben ja die, deren Vornamen gefunden wurde, mal nachgerechnet.

[Memnarch]

Momentmal. Wenn du in Hex suchst, sind 2 ziffern immer ein Byte.
Demnach ist hex 243 = 2 bytes groß.

Komplett ausgeschrieben müsste die hexzahl so notiert werden: 0243

Es wird also nach einer 2byte Kombo gesucht. Was du gerade assoziiert hast, war den Gesuchten hexwert in einem zeichenstring zu suchen. Du suchst aber eine HexFolge in einer Hexfolge.

Die wazillionen ungültigen resultate stammen aus dubleten. Nicht zutreffende kombos könne auch mehrmals vorkommen.

Dann ist auch noch wichtig: wie wird gesucht? wird statisch so gekapselt( | trennt ein byte):

(3.)24|3F|6A|88|85|A3|08|D3|13|19|8A|2E|0?|

oder geht es immer um eine hexziffer weiter und wird von drtaus immer die bytefolge untersucht?

also:
24|3F
43|F6

etc

Du siehst dass da durchaus alles korrekt abläuft.


MFG
Memnarch

[gammatester]

Zitat:

Zitat von Memnarch (Beitrag 1108486)

Momentmal.
Dann ist auch noch wichtig: wie wird gesucht? wird statisch so gekapselt( | trennt ein byte):

(3.)24|3F|6A|88|85|A3|08|D3|13|19|8A|2E|0?|

oder geht es immer um eine hexziffer weiter und wird von drtaus immer die bytefolge untersucht?

also:
24|3F
43|F6

etc

Du siehst dass da durchaus alles korrekt abläuft.

Ne so ist das nicht, bzw. es bleibt undurchsichtig. Wir stimmen wohl überein, daß entweder '24' oder '43' ziemlich weit vorne steht:

Code:

Search string = "24"
 8-bit binary equivalent =   00100100
search string found at binary index =  2922859472
hex pi    : 3994def110dad7bc89f52400000ace1eef6688d61da713e4
hex string:                     24 

earch string = "43"
 8-bit binary equivalent =   01000011
search string found at binary index =   546355468
hex pi    : 3d96f8432694804d0f443000002249ced2642d61f35135ad
hex string:                    43

Im übrigen wird selbst auf der Seite nicht verlangt, eine gerade Anzahl von Hex-Ziffern einzugeben, die Wahrscheinlichkeiten werden für 7,9,11.. Ziffern abgegeben etc.

[Memnarch]

du weißt aber nicht was das programm macht. Natürlich kannst du ungerade ziffern angeben.

Schätze aber mal, es wird auf komplette bytes aufgefüllt.

So würde aus

243

0243.

Sonst hantierst du mit halben bytes. Wenn das programm nur mit vollen bytes arbeitet, dann füllt es eben auf.

EDIT: mh seh gerade dein letztes suchergebnis

[Satty67]

Wenn der Index das Problem ist, also das verdefinierte Wörterbuch einen zu großen Index bekommen kann, muss man da ansetzen.

LZW ist bei vorsortierter Datenmenge ja bereits ein Verfahren, das mit fast optimalem Wörterbuch (gebildeten) und damit Indexgröße arbeitet.

Was ist, wenn man nun ein optimales Wörterbuch selbst definiert (statt Pi), das für jede Datenmenge eine kleinere Index/Count Kombination liefert, als mit Index/Count abgebildet letztlich wird?

Ist sowas überhaupt mathematisch möglich?

€: Da bei so einer Definition durch Wiederholung gegen 0 komprimiert werden könnte, ist das rein logisch betrachtet eine unmögliche Aufgabe. Das gilt auch für den hier vorgestellten Vorschlag mit PI

[Memnarch]

@Satty: also was du gerade beschreibst hort sich nach einem Mathematischen Perpetuummobile an.
Wenn du ein Wörterbuch hast mit kürzeln für bestimmte datenkombinationen, so kannst du bei gegebener länge X der Kürzel auch nur eine bestimmte anzahl an Kürzeln notieren. Die zu indizierende datenmenge ist aber unendlich. Dementsprechend brauchst du auch einen Index von bis zu unendlicher größe.


MFG
Memnarch

[Satty67]

Zitat:

Zitat von Satty67 (Beitrag 1108492)

€: Da bei so einer Definition durch Wiederholung gegen 0 komprimiert werden könnte, ist das rein logisch betrachtet eine unmögliche Aufgabe. Das gilt auch für den hier vorgestellten Vorschlag mit PI

Ich hab' gerade nochmal mein Edit zitiert... mir ist das nach dem Posten selber aufgefallen.

[negaH]

Folgendes wäre sinnvoller: man nimmt alle Wörter die im Internet kursieren, sortiert sie nach Häufigkeit und hat eine Tabelle die jeder Rechner bekommt.

Die Stellen von PI zu berechnen geht zZ. nur über Formeln die alle Vorgängerstellen von PI berechnen müssen. Der Aufwand steigt also mit größeren Indizes immer weiter an bis zur Unberechenbarkeit. Oder man nimmt Formeln die schneller sind dafür aber mit gigantisch großen Zahlen rechnen müssen und auch hier gibt es technische Grenzen.

Je größer der Index wird desto schlechter wird das Kompressionsratio zwischen Länge des gesuchten Textes zu Bitgröße des gefundenen Indizes. Auch hier gibt es eine Grenze und der erechnete Indize spiegelt in seiner Bitgröße nicht die Häufigkeit des gesuchten Wortes wider. Aber exakt das benutzen alle Komprimierungen, sie benutzen Häufigkeiten in einem Text um ihn zu komprimieren.

Wie Gammatester schon eingangs sagte auch ich halte nicht viel davon. Es sei denn es ist akademischer Natur nur gäbe es dann bessere Themen. Die Idee als solches ist garnicht so unbekannt.

Gruß Hagen

[himitsu]

Dann bauen wir halt eine DP-Verschlüsselung daraus auf. :dp:

@Aphton: Nicht entmutigen Lassen ... auch aus den dümmste Ideen sind schon manchmal geniale Dinge entstanden.
Muß ja nicht gleich jetzt passieren, aber vielleicht kommt ja noch irgendwann mal DIE dumme Idee zu dir. :stupid:

[Namenloser]

Insgeheim hoffe ich ja immer noch, dass die Nachkommastellen von Pi ab einer gewissen Stelle anfangen, Sinn zu machen und eine Erklärung für das Universum liefern :oops:
Ich glaube, es gibt sogar einen SciFi-Roman, der darauf basiert...

[Memnarch]

@NamenLozer: Dan geh mal schnell gucken welcher das war, wäre vllt ganz interressanter lesestoff :stupid: