- Registriert
- 3 Aug. 2014
- Beiträge
- 28.573
Guten Morgen,
zur Zeit versuche ich mich an diesem, etwas älterem, Programmierwettbewerb: http://prize.hutter1.net/
Gut, der ist nicht mehr sonderlich aktuell vielleicht, aber ich finde die Thematik eigentlich sehr spannend und interessant, es geht um Datenkompression.
Es geht dabei darum einen Wikipedia Artikel, 100 MB groß, so weit wie möglich ohne Datenverlust zu komprimieren und wieder zu dekomprimieren. Download auf der Seite, "enwik8" heißt die Datei. Aktueller Rekord sind etwas um die 15,932,968 Bytes.
Ich würde gerne mal in die Runde fragen, ob so was ein interessantes Thema wäre was es lohnt sich mal gemeinsam den Kopf darüber zu zerbrechen und Erfahrungen auszutauschen was Datenkompression anbelangt - nicht das man in der heutigen Zeit noch großartig den Zwang hat Datenkompression anwenden zu müssen bei den Speicherpreisen und Größen, aber ich finde das herunterbrechen von Daten höchst interessant und irgendwo doch auch noch wichtig genug, selbst wenn es nur um Bildverarbeitung geht oder ähnlichem.
Also ich beschreibe mal einen Ansatz den ich gerade hierbei verfolgt habe (ohne tieferes fundiertes Vorwissen), gerne kann ich dazu auch noch Code posten, falls gewünscht:
1 - Die Datei wird eingelesen und jedes Wort wird notiert und in ein Wörterbuch gepackt mit Länge des Wortes und dessen Anzahl
2 - Taucht ein Wort auf das existiert, wird dessen Position in der Zeile notiert (ohne Zeilenangabe) und die Anzahl erhöht, logisch
3 - Das Wort wird gespeichert, Newline, Positionsangabe in HEX mit ".HEX-Pos" (ist noch etwas kürzer als rein Dezimal zu verwenden)
Allein durch dieses Vorgehen komme ich auf circa. 56%-60% bei 100 MB, also etwas um die 56-60 MB die nur noch gespeichert werden müssen. Okay, sind keine 16 MB aber das ist vermutlich auch schon Hardcore Coding
Meine Frage wäre jetzt, wie könnte man dies verbessern?
Ideen die ich habe aber noch nicht umgesetzt sind:
1) Sich wiederholende Positionen könnte man kürzen, das würde das Datenaufkommen vielleicht noch etwas reduzieren was die Positionsbestimmungen angeht
Also aus .0.0.0.0.0 (der Punkt ist Trenner für die Positionsangaben) könnte man auf .5*0 zusammenfassen.
Allerdings tritt der Fall auch leider etwas zu selten auf, wenn die Schreibweise des Kürzels größer ist als das was ersetzt wird, hat man wieder mehr geschrieben als gekürzt worden ist.
2) Kürzel einführen die längere Textelement wegkürzen
Hierbei wäre die Idee, häufig auftretende Kürzel in einem Wort durch etwas zu ersetzen, da es sich um einen englischen Text handelt, sind das zum Beispiel:
"of", "and", "then", "lly", auch "http://", "www" oder ähnliches, so genau habe ich die Daten noch nicht analysiert
Einziges Problem aber auch hierbei, weniger Zeichen für das Kürzel zu verwenden als zu dem was ersetzt werden soll und natürlich auch zu gewährleisten das nicht genau diese Kombination auch in dem Wort auftaucht, vielleicht ist das auch etwas falsch.
3) Binär Arbeiten (nicht wirkich durchdacht, weil wenig Know-How)
Alle Positionsfelder in Binär ausgeben und dann damit versuchen zu komprimieren wie (1111 = 4*1), (5*0 = 00000) usw.... aber das habe ich noch nicht wirklich durchdacht weil Binär ja eigentlich Dezimal unterlegen ist auch wenn die Datenstruktur durch 0 und 1 vereinfacht wird...
4) Noch sauberes Dictionary erstellen:
Derzeit sind 'Test' und 'Test]' oder ' Test" ' unterschiedliche Wörter, hier könnte man eventuell säubern, muß jedoch dann die Zeichen ()[]{}=' und " einzelnen notieren, Frage ist, ob sich das wirklich lohnt.
------------
Es gibt vermutlich noch viele weitere Optionen und Ansätze, aber das Thema ist für mich Neuland. Aber vielleicht finden das anderes ja auch interessant wie man dabei vorgehen könnte oder hat jemand konkrete Erfahrungen, die man preisgeben kann/darf.
Im übrigen, einen Dekompressor habe ich derweil noch nicht geschrieben, es sollte allerdings möglich sein, die Daten, durch die Positionsangaben zurückzugewinnen. Ohne die Zeilen mit zu notieren. Aber gut, vielleicht sollte ich das einfach auch nochmal testen...
zur Zeit versuche ich mich an diesem, etwas älterem, Programmierwettbewerb: http://prize.hutter1.net/
Gut, der ist nicht mehr sonderlich aktuell vielleicht, aber ich finde die Thematik eigentlich sehr spannend und interessant, es geht um Datenkompression.
Es geht dabei darum einen Wikipedia Artikel, 100 MB groß, so weit wie möglich ohne Datenverlust zu komprimieren und wieder zu dekomprimieren. Download auf der Seite, "enwik8" heißt die Datei. Aktueller Rekord sind etwas um die 15,932,968 Bytes.
Ich würde gerne mal in die Runde fragen, ob so was ein interessantes Thema wäre was es lohnt sich mal gemeinsam den Kopf darüber zu zerbrechen und Erfahrungen auszutauschen was Datenkompression anbelangt - nicht das man in der heutigen Zeit noch großartig den Zwang hat Datenkompression anwenden zu müssen bei den Speicherpreisen und Größen, aber ich finde das herunterbrechen von Daten höchst interessant und irgendwo doch auch noch wichtig genug, selbst wenn es nur um Bildverarbeitung geht oder ähnlichem.
Also ich beschreibe mal einen Ansatz den ich gerade hierbei verfolgt habe (ohne tieferes fundiertes Vorwissen), gerne kann ich dazu auch noch Code posten, falls gewünscht:
1 - Die Datei wird eingelesen und jedes Wort wird notiert und in ein Wörterbuch gepackt mit Länge des Wortes und dessen Anzahl
2 - Taucht ein Wort auf das existiert, wird dessen Position in der Zeile notiert (ohne Zeilenangabe) und die Anzahl erhöht, logisch
3 - Das Wort wird gespeichert, Newline, Positionsangabe in HEX mit ".HEX-Pos" (ist noch etwas kürzer als rein Dezimal zu verwenden)
Allein durch dieses Vorgehen komme ich auf circa. 56%-60% bei 100 MB, also etwas um die 56-60 MB die nur noch gespeichert werden müssen. Okay, sind keine 16 MB aber das ist vermutlich auch schon Hardcore Coding
Meine Frage wäre jetzt, wie könnte man dies verbessern?
Ideen die ich habe aber noch nicht umgesetzt sind:
1) Sich wiederholende Positionen könnte man kürzen, das würde das Datenaufkommen vielleicht noch etwas reduzieren was die Positionsbestimmungen angeht
Also aus .0.0.0.0.0 (der Punkt ist Trenner für die Positionsangaben) könnte man auf .5*0 zusammenfassen.
Allerdings tritt der Fall auch leider etwas zu selten auf, wenn die Schreibweise des Kürzels größer ist als das was ersetzt wird, hat man wieder mehr geschrieben als gekürzt worden ist.
2) Kürzel einführen die längere Textelement wegkürzen
Hierbei wäre die Idee, häufig auftretende Kürzel in einem Wort durch etwas zu ersetzen, da es sich um einen englischen Text handelt, sind das zum Beispiel:
"of", "and", "then", "lly", auch "http://", "www" oder ähnliches, so genau habe ich die Daten noch nicht analysiert
Einziges Problem aber auch hierbei, weniger Zeichen für das Kürzel zu verwenden als zu dem was ersetzt werden soll und natürlich auch zu gewährleisten das nicht genau diese Kombination auch in dem Wort auftaucht, vielleicht ist das auch etwas falsch.
3) Binär Arbeiten (nicht wirkich durchdacht, weil wenig Know-How)
Alle Positionsfelder in Binär ausgeben und dann damit versuchen zu komprimieren wie (1111 = 4*1), (5*0 = 00000) usw.... aber das habe ich noch nicht wirklich durchdacht weil Binär ja eigentlich Dezimal unterlegen ist auch wenn die Datenstruktur durch 0 und 1 vereinfacht wird...
4) Noch sauberes Dictionary erstellen:
Derzeit sind 'Test' und 'Test]' oder ' Test" ' unterschiedliche Wörter, hier könnte man eventuell säubern, muß jedoch dann die Zeichen ()[]{}=' und " einzelnen notieren, Frage ist, ob sich das wirklich lohnt.
------------
Es gibt vermutlich noch viele weitere Optionen und Ansätze, aber das Thema ist für mich Neuland. Aber vielleicht finden das anderes ja auch interessant wie man dabei vorgehen könnte oder hat jemand konkrete Erfahrungen, die man preisgeben kann/darf.
Im übrigen, einen Dekompressor habe ich derweil noch nicht geschrieben, es sollte allerdings möglich sein, die Daten, durch die Positionsangaben zurückzugewinnen. Ohne die Zeilen mit zu notieren. Aber gut, vielleicht sollte ich das einfach auch nochmal testen...