• Hallo liebe Userinnen und User,

    nach bereits längeren Planungen und Vorbereitungen sind wir nun von vBulletin auf Xenforo umgestiegen. Die Umstellung musste leider aufgrund der Serverprobleme der letzten Tage notgedrungen vorverlegt werden. Das neue Forum ist soweit voll funktionsfähig, allerdings sind noch nicht alle der gewohnten Funktionen vorhanden. Nach Möglichkeit werden wir sie in den nächsten Wochen nachrüsten. Dafür sollte es nun einige der Probleme lösen, die wir in den letzten Tagen, Wochen und Monaten hatten. Auch der Server ist nun potenter als bei unserem alten Hoster, wodurch wir nun langfristig den Tank mit Bytes vollgetankt haben.

    Anfangs mag die neue Boardsoftware etwas ungewohnt sein, aber man findet sich recht schnell ein. Wir wissen, dass ihr alle Gewohnheitstiere seid, aber gebt dem neuen Board eine Chance.
    Sollte etwas der neuen oder auch gewohnten Funktionen unklar sein, könnt ihr den "Wo issn da der Button zu"-Thread im Feedback nutzen. Bugs meldet ihr bitte im Bugtracker, es wird sicher welche geben die uns noch nicht aufgefallen sind. Ich werde das dann versuchen, halbwegs im Startbeitrag übersichtlich zu halten, was an Arbeit noch aussteht.

    Neu ist, dass die Boardsoftware deutlich besser für Mobiltelefone und diverse Endgeräte geeignet ist und nun auch im mobilen Style alle Funktionen verfügbar sind. Am Desktop findet ihr oben rechts sowohl den Umschalter zwischen hellem und dunklem Style. Am Handy ist der Hell-/Dunkelschalter am Ende der Seite. Damit sollte zukünftig jeder sein Board so konfigurieren können, wie es ihm am liebsten ist.


    Die restlichen Funktionen sollten eigentlich soweit wie gewohnt funktionieren. Einfach mal ein wenig damit spielen oder bei Unklarheiten im Thread nachfragen. Viel Spaß im ngb 2.0.

Ideenfindung Datenkompression

theSplit

1998
Veteran Barkeeper

Registriert
3 Aug. 2014
Beiträge
28.561
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... :)
 

RedlightX

Bekannter NGBler

Registriert
18 Juli 2013
Beiträge
1.185
Das hört sich in der Tat spannend an.
Ist dieser Wettbewerb offiziell beendet? Scheint noch zu laufen :D

Momentan hab ich gerade Prüfungsstress, aber danach juckt es mir in den Fingern, mich daran mal zu versuchen :T
 
Zuletzt bearbeitet:

exomo

NGBler

Registriert
1 Aug. 2015
Beiträge
129
Das Thema ist auf jeden Fall interessant. Und komprimieren von Daten ist nach wie vor wichtig. Speicher wird zwar immer günstiger, aber auch die Datenmengen immer größer. Und nicht jeder hat ultraschnelles Breitband-Internet.

Wörterbücher sind auf jeden Fall eine gängige Methode für Komprimierung. Ein Wörterbuch enthält nicht unbedingt immer ganze Wörter, sondern auch Teilwörter und Wortgruppen werden eingetragen, um eben auch wiederkehrende Wortteile platzsparend zu kodieren.
Die Kunst dabei ist, ein möglichst optimales Wörterbuch zu finden. Ein guter Anfang finde ich ist immer der LZW-Algorithmus , der ist noch einigermaßen verständlich.

Ich habe nicht ganz verstanden wie deine Kodierung aussieht (du kannst ja mal ein kurzes Beispiel machen), aber hier mal meine Gedanken zu den Ideen:

1) Wie du schon festgestellt hast kommt es nicht so oft vor, dass die gleichen Würter direkt hintereinander stehen. Vor allem wenn du nur ganze Wörter im Wörterbuch hast. Die Lauflängenkodierung kann aber zum Beispiel nach einer Burrows-Wheeler-Transformation als zusätzlicher Schritt angewendet werden.

2) Wie in der Einleitung schon gesagt ist es schon sinnvoll auch Teilwörter zu kodieren. Um damit Platz zu sparen ist es wichtig, dass die kodierte Schreibweise nicht viel Platz braucht.

3) Habe ich nicht verstanden, klingt aber komisch. Zahlen lassen sich kaum dadurch komprimieren, dass man ihre Binärschreibweise kodiert.

4) Wörterbuch optimieren auf jeden Fall. Ob du alle Sonderzeichen dafür speziell behandeln musst weiß ich nicht. Eventuell kann es auch sinnvoll sein, das eine oder andere Wort wie "Test]" als eigenes Wort aufzunehmen, wenn es oft genug vorkommt.

Zu sonstigen Ansätzen:
Alles was ich so kenne ist noch aus dem Studium hängengeblieben, also sicher keine Geheimnisse. Ich kann dir mal ein paar Themen nennen die eventuell hilfreich sind:
Huffman-Kodierung: Häufig vorkommende Zeichen haben kürzeren Binärcode
LZW-Algorithmus (Stellvertretend für alle LZ..) Wörterbuch aufbauen
Burrows-Wheeler-Transformation
Lauflängenkodierung
Die meisten bekannten verlustfreien Kompressionsalgorithmen verwenden einen oder mehrere dieser Algorithmen in verschiedenen Variationen.

Eigene Ideen:
(erstmal nur Gedanken)
- Groß-/Kleinschreibung: Gleiche Wörter können je nach Position (z.B. Satzanfang) unterschiedlich geschrieben werden. Wenn man die Großschreibung anderweitig kodiert, kann man sich vielleicht Einträge im Wörterbuch sparen.
- Markup: Die Datei enthält jede Menge Markup (XML, Markdown), wobei sich immer bestimmte Muster wiederholen. Z.B. "=== Überschrift ===" mit unterschiedlichem Text. Durch spezielle Kodierung von "Tags" kann man sich dann sparen, zwei mal === zu kodieren. Bei XML wird es schon schwieriger, aber könnte auch was machbar sein.


Falls ich dazu komme hacke ich vielleicht auch mal die eine oder andere Zeile Code, aber du darfst auch gerne meine Ideen ausprobieren. Ich finde das ein spannendes Thema, aber wie immer ist meine Zeit begrenzt.
 

drfuture

Zeitreisender
Teammitglied

Registriert
14 Juli 2013
Beiträge
8.728
Ort
in der Zukunft
Mal eine fixe Idee in den Raum geworfen...
(nachdem ich den Wettbewerb oben gelesen habe bringt das leider nichts - aber finde die Idee trotzdem gut, nur nicht geeignet ;D)

Wenn es "nur" um Größe ginge und nicht in <10h auf einem alten PC laufen müsste könnte man eine Funktion schreiben die anhand eines Arrays an Buchstaben und Zeichen zufällige Kombinationen erstellt, dabei allerdings die Rnd() Quelle Festschreiben. Sodass nach 10 Versuchen immer das gleiche Ergebnis raus kommt.
Dann brauchst das Programm "nur" den Code, den Quellstring und die Anzahl der Iterationen zu speichern.

zum DIESEM Wettbewerb passend muss ich mir wohl neue Gedanken machen :D

Edit:
Aber eigentlich - so wie ich da verstehe - geh es in den Wettbewerb eher darum eine Art "Gehirn" zu programmieren... sprich Eindrücke die man eingibt (Wikipedia) so optimal wie möglich abzulegen und später wieder abzurufen - wobei es nicht um "gewöhnliche" bekannte Algorithmen geht.
Aber genau deswegen kapiere ich nicht warum die die Laufzeit auf so eine Kiste limitieren...
Mit genügend Rechenleistung könnte man garantiert auf basis von Wahrscheinlichkeiten / erfahrung so in richtung "Bussword Deeplearning" direkt was erreichen.

Edit²:
Dafür gäbe es diesen Unterwettbewerb http://mattmahoney.net/dc/textrules.html
 
Zuletzt bearbeitet:

theSplit

1998
Veteran Barkeeper

Registriert
3 Aug. 2014
Beiträge
28.561
  • Thread Starter Thread Starter
  • #5
Erstmal vielen Dank für euer Feedback - ich lasse das mal so stehen ohne zu tief ins Detail zu gehen, weil ich mich erst einmal etwas mit den Algorithmen die hier vorgeschlagen worden sind auseinandersetzen will und zu versuchen diese halbwegs nachzuvollziehen. Ist für mich nicht alles gleich so straight forward um ehrlich zu sein. Aber ein paar Gedanken und Fragen hab ich schon dazu angesammelt ;)

Was ich verstanden habe soweit (ich versuchs ehrlich kurz zu halten):

Huffman-Kodierung:
Statt eines vollem Byte (8 bit) für ein 'a' verwendet man einfach 1 Bit z.B. Binär 1 für 'b' Binär 01 für 'c' Binär 001 für 'd' Binär 0001, 'g' Binär 10, dann 11, 110, bis zu 11111111 theoretisch (8 bit, 1 Byte - Dictionary quasi erschöpft/voll)

Ich hoffe ich irre mich nicht, aber dann müsste man doch eine Datei im binären Schreibmodus öffnen um so etwas speichern zu können? Zum Beispiel WriteBinary (wb)?
In C habe ich mich noch nicht damit auseinandergesetzt um ehrlich zu sein.

Hier kämen mir die Idee das ganze noch ganz anders aufzubauen, in den 256 Symbolen die man 2 hoch 8 bit speichern kann, könnte man das gesamte Alphabet aufnehmen, so wie auch glaube ich im Wikiartikel dazu steht auch größere Wortbausteine, zum Beispiel 3 Buchstaben in einem Shorthand, so lange dies nur häufig genug vorkommt. Oder?

Aber was ich auch nicht ganz verstehe, wenn ich von 8 Bit nur 6 Bit nutze, muß ich doch irgendwie die Symbole voneinander trennen? Damit keine Fragmentierung entsteht und immer 8 bit Blöcke geschrieben werden? Ist vielleicht echt Basic, aber ich hab noch nie mit Binären Dateien gearbeitet, speziell nicht in C und da fehlt mir auch etwas das Know-How. Wenn einer mag, kann man das vielleicht aufklären, so ganz begreife ich das nicht?

*Habe gerade mal gelesen was das Binär in diesem Fall bedeutet, ich hab gedacht man hätte Zugriff auf Bits und nicht nur gesamte Bytes... also ist das doch nicht so einfach wie vermutet, dann stehe ich jetzt doch ganz mächtig auf dem Schlauch :(

Hab noch das dazu gefunden: http://stackoverflow.com/questions/13252697/writing-bits-to-a-file-in-c

Wie funktioniert dann aber diese Komprimierung wenn ich ein Byte nicht mit weniger als ein Byte festlegen/speichern/abbilden kann?



Lempel-Ziv-Welch-Algorithmus

Wenn ich richtig verstehe, versucht man hier ein Wörterbuch anzulegen, welches zu dem Teilstücke/Schnittmengen ermittelt, welche als Kürzel genutzt werden um Wiederholungen durch diese Kurzformen zu ersetzen und somit weniger Speicherplatz zu verbrauchen.

Ich glaube etwas ähnliches, natürlich aber viel einfacher, wollte ich nicht Binär aber mit normalen Zeichen nachbauen, wobei "http://" durch "#01#" ersetz wird (okay, sind nur 3 Zeichen weniger, aber immerhin... ;) )




Burrows-Wheeler-Transformation


Okay, dieses Vorgehen bzw. wo diese Transformation, erschließt sich mir noch nicht ganz. - Ich kann zwar nachvollziehen das dieser Algorithmus die Zeichen so anordnen soll, das diese besser komprimiert werden können, weil auf einander folgend - ist mir aber noch etwas unklar in wie weit man aus dieser "Anordnung" etwas Gewinnen kann.
Ich denke mir dabei jedenfalls, wenn die Buchstaben der Wörter/Sätze intakt bleiben, kann ich diese doch nicht wie 'AAAA' nach '4A' kürzen?


Sorry, das sind wie gesagt nur meine Fragen, aber ich hoffe jeder hat davon etwas da ich ja als jemand an so etwas herangehe der mit mathematischen Formel und Diagrammen in trüben Gewässern fischt. Mit anderen Worten, ich hab davon null Ahnung leider.



Zu guter letzt wollte ich mal ein Beispiel geben, wie meine bisherige Kodierung aussieht, mit der ich auf (~57 %) komme, aber die Idee hat nen Denkfehler, den ich gleich kurz erkläre, weil ich mich leider zu früh gefreut habe das ich schon so viel komprimieren konnte! :o



Hier folgend ein Teil des Outputs, die Form ist so:

Wortelement .Hex-Wert Pos 1 .Hex-Wert Pos 2 .Hex-Wert Pos 3...
also
Test.0.a.9.2...

Dabei ist die Reihenfolge der Wörter so, wie sie im Text auftauchen, außer sie sind schon im Wörterbuch vorhanden und ich glaube hier liegt auch mein Denkfehler das es so nicht ganz passen kann die Daten zurück zu konstruieren, es fehlen nämlich die Positionsangaben für Zeilen in denen das Wort nicht auftaucht, da wir nicht speichern welche Wörter zu welcher Zeile gehören bzw. ein nichtauftauchen mit einer 0 belegen, wobei die Indexe bei 1 starten sollten dann.... (zu früh gefreut :o)

[src=text]'''Anarchism'''.0
originated.1.6.86.66.8.17.65
as.2.50.10.43.5b.6a.81.17.4c.1d.70
a.3.23.51.11.51.88.a2.49.17.a.17.39.7
term.4.1e.9.3a.12.3.9.16.2d.3a.8.f
of.5.11.18.32.35.3d.41.24.33.3a
abuse.6.1e.14.4a.58.55
first.7.5.23.1.54.60.44.8
used.8.21.2b.a.b.5.15.23.19.79.3a.d
against.9.7f.17.3f.2.b.2c.5b.61.29.43.1b
early.a.5a.1.3.31.27.32.41.a.14.61[/src]

Wie man sieht:
'''Anarchism''' <--- ist auf "0" (erstes Wort in der neuen Zeile)
originated <---- ist auf 1 in dieser Zeile
as <--- das 2 Wort der Zeile
a <--- drittes Wort
term <--- viertes Wort
usw...


Ich glaube aber, jetzt wo ich gerade die Dekompremierung beschreiben wollte, hat das System einen Fehler..., es müsste zum Beispiel eine 0 ausgeben (wenn alles bei 1 anfängt) wenn ein Wort in einer Zeile nicht vorhanden ist, da wir sonst ja nicht wissen können wo eine Zeile anfängt oder Ende :o



PS: DrFuture, ich werd aus deinem Beitrag nicht ganz schlau, war die Idee jetzt für diese Aufgabe oder war das mehr auf ein selbstlernendes System bezogen? Es ging eigentlich um Datenkompression nicht direkt Maschine Learning; auch wenn man das vielleicht irgendwie kombinieren kann.... hab keine Ahnung. :unknown:
 
Zuletzt bearbeitet:

Jester

★★★★☆ (Kasparski)

Registriert
1 Dez. 2014
Beiträge
6.057
Ort
Code Azure
@theSplit: Bei reiner Text-Kompression kannst Du den Inhalt grundsätzlich mit 7 Bit je Byte abbilden (33 - 125 dez.). Bit 8 des ersten komprimierten Bytes ist dann Bit 1 des 2. Ursprungsbytes und so weiter, ein Datenstrom also, der auf dem gleichen Weg dekomprimiert wird.

Ob diese Methode in dem aktuellen Fall Sinn macht, ist fragwürdig. Nach der Eindampfung auf 7-Bit-Wörter greifen andere Kompressionsmethoden nicht mehr so gut, weil z. B. Wiederholungen asymmetrisch auf Bytes verteilt sind. Interessant wäre aber ein 7-Bit-Packer für den bereits komprimierten Strom.

Rein aus dem Bauch raus sollten bei der Menge an Text Tokens die erste Wahl sein, das müsste ordentlich Ratio ergeben. Um aber auf die Werte des derzeit Besten (~16 MiB) zu kommen, wirst Du um mehrere Pack-Passes und Algorhythmen nicht herumkommen.
 

theSplit

1998
Veteran Barkeeper

Registriert
3 Aug. 2014
Beiträge
28.561
  • Thread Starter Thread Starter
  • #7
Hi Jester,
also nur um es ferstzuhalten, es geht mir nicht zwingend darum diese magisch gelegte Untergrenze zu knacken, auch wenn das natürlich das Optimium wäre... - ich halte es aber für etwas unwahrscheinlich ohne ein Crack in dem Thema zu sein. :D

Bis vor ein paar Minuten (hab deinen Beitrag mehrmals lesen müssen) hat mich deine Antwort auch etwas weiter verunsichert, für mich ist halt nur logisch das die kleinste Einheit ein Byte - zum Beispiel aus dem 8 bit ASCII Zeichenvorrat ist, worunter neben dem Alphabet auch die Zahlen 0-9 fallen und Steuerzeichen, also alles was man als "char" in C abbilden kann. Soweit richtig?

Ich könnte jetzt Binär intern ausgeben lassen und müßte diese 7 bits dann wie du sagst mit einem Folgebit füllen und hätte dann ein Byte, das Zeichen X das ich nun speichern als Byte speichern kann.
Also wenn die 7 bit folgende Abbildung sind 0101011 sind und das nächste Bit des nächsten Datenstroms wäre 1, ergibt sich 01010111 (ich hab das jetzt mal in einem Binary <=> Ascii Konverter konvertiert) - es wäre das Zeichen "W".

Wenn man jetzt nur auf 2 hoch 7 Bits begrenzt haben wir dennoch 128 "Shortcuts", bzw. Wörter die wir mit Synonymen kürzen könnten, right? So in der Denke der Huffmann-Kodierung wäre das?

Fallt mir bitte bloß ins Wort wenn ich mich irre - wäre sehr nett! :T

Zum Thema 7 Bit Packer, meine spontaner Gedanke, wenn man den LZW anwendet, könnte man damit doch auf häufig auftretende 1-Byte-Zeichen/Zahlen/Symbol-Folgen komprimieren, so fern die paare nochmals im Datenstrom auftreten den man temporär ausgibt/erzeugt.

Aber kann auch sein das ich es nur nicht ganz so Hinterblicke.
 

drfuture

Zeitreisender
Teammitglied

Registriert
14 Juli 2013
Beiträge
8.728
Ort
in der Zukunft
@theSplit,
mein Beitrag zeigt Chronologisch auf was ich zu deinem Beitrag "dachte" ....

1. Beitrag gelesen > Idee gehabt den Text so zu komprimieren in dem man eben zufällig aus dem Alphabet einen Artikel mit 100.000 Zeichen erstellen lässt. Dann die Buchstaben so lange durchwürfelt bis das Endergebnis erreicht ist. Wobei der Startpunkt + Ablauf des "Zufalls" bei jedem Start gleich ablaufen muss. Für den Fall würde die Anwendung "nur" das Alphabet, den Code + die Anzahl der Iterationen benötigen.
2. Ich habe gelesen das es eine Maximale Anzahl an Laufzeit gibt - somit war die Idee für die Tonne
3. Habe gesehen das es einen Wettbewerb ohne das Zeitlimit gibt ....

Aber! Auf der Seite steht das es bei dem Wettbewerb eigentlich eben nicht um die Implementierung oder Verkettung von "bekannten" Komprimierungen geht, es ist auch nicht durch Zufall ein Artikel von Wikipedia als Testfile gewählt.
Es geht darum möglichst Intelligent - eben so wie es der Mensch im Gehirn macht - Sprache bzw. Wissen zu komprimieren um bei Bedarf darauf zugreifen zu können. Das Menschliche Gehirn lägt ja Wissen und Bilder auch nicht als volle "Daten" ab sondern umso unwichtiger umso unschärfer und weniger Details usw. - So soll das Ziel hier wohl auch sein. Das geballte Wissen von Wikipedia so zu komprimieren das es wenig Platz braucht und evtl. dadurch auch hirarchisch / objektbasiert durchsucht werden kann und Machinen dadurch einfach ein großes Wissen bekommen und Effecktiv damit arbeiten können.

Dadurch sollte man wohl auch creativer an sowas ran gehen - auch wenn man es dann gar nicht umsetzen kann :D
 

Jester

★★★★☆ (Kasparski)

Registriert
1 Dez. 2014
Beiträge
6.057
Ort
Code Azure
@theSplit:
Yup, korrekt.

Das kleinste in reinem Text verwendete Zeichen ist das Blank 20h bzw. 32d. Das letzte ist 7Bh bzw. 125d. Also kommst Du zwar nicht unter 128 (64 reicht nicht für Sonderzeichen), musst aber auch nicht über 128.

Im Byte hast Du aber 256 mögliche Kombinationen, so dass das oberste Bit nicht genutzt werden muss, um alle möglichen Zeichen abbilden zu können.

Beispiel:

STRING "7-bit"
7 -> 37h -> 100101b -> 0100101
- -> 2Dh -> 101101b -> 0101101
b -> 62h -> 1100010 -> 1100010
i -> 69h -> 1101001 -> 1101001
t -> 74h -> 1110100 -> 1110100
- -> 2Dh -> 101101b -> 0101101
F -> 46h -> 1000110 -> 1000110
u -> 75h -> 1110101 -> 1110101
n -> 6Eh -> 1101110 -> 1101110

(In den ersten beiden Fällen mit leading zero aufgefüllt).

BitsToPack: 01001010101101110001011010011110100100011011101011101110
Segmented: 01001010 10110111 00010110 10011110 10010001 10111010 11101110

So wurden aus 8 Byte 7 Byte.

Allerdings ist das nicht besonders effizient, weil es - vor ggfs. weiteren Pack-Passes - nur 12,5% Ersparnis bringt, ohne den Code des Decompressors zu berücksichtigen.

(...)

Der beste Pack-Algorhythmus für diesen Fall dürfte CMIX sein. Gemeinerweise wurde der ohne Rücksicht auf Kodierungszeit entworfen, wird also die max. Packtime sicher überschreiten :)
 

theSplit

1998
Veteran Barkeeper

Registriert
3 Aug. 2014
Beiträge
28.561
  • Thread Starter Thread Starter
  • #10
Für das "du hast es schon halbwegs verstanden junger Padawan" @ Jester, gibt es ein Danke ;)

Und natürlich auch für die liebevolle Erklärung/Bestätigung :)


@drfuture:
So kann ich es auch nachvollziehen :) - Ja das mit den Limits ist doof, aber es soll vermutlich ein Schnitt zwischen Geschwindigkeit/Speicherverbrauch und Pack-Leistung ermittelt werden der auf moderneren Geräten vermutlich schneller ablaufen könnte, auch bei größeren Datenmengen. Deßhalb wohl auch die alte Hardware, nehme ich jetzt mal an ;)

Zum Thema Self-learning System indirekt:
Man könnte es auch wie einer Art "Stemmer" aufbauen, bei dem man nach logischen "Buchstabenkombination" sucht, die in der Sprache (also generell auf vieles der Inhalte) beliebig angewandt werden können, das ist zwar nur bedingt intelligent, aber so fern man genug große "Worteinheiten" zusammenführen bzw. Kürzen kann auf Basis eines Grundwörterbuches welches dynamisch gestaltet ist, sollte es möglich sein mehr einzusparen.



Es gibt ja auch im Deutschen so etwas wie "ung", "auf", "und", "gen" / "en" (en ist natürlich sehr klein leider, aber 50% durch ein Zeichen ersetzt...), "isch", "hen", "che", "sche" oder andere Wortbausteine.

Wenn man hier noch größere "Wortbausteine" durch Stemming in ein Dictionary pressen und verkürzen kann, weil sie genug häufig auftauchen, was man natürlich aus den Datenfunds eines gesamten Dictionary ermitteln bzw. herunterbrechen muß bzw. den längsten Wörtern in diesem - hätte man einen sehr guten Kompressor meine ich.

Das größte Problem was ich bisher aber dabei festgestellt habe, das Kürzel darf nicht im Wort auftauchen, sonst haben wir Humbug im Text weil etwas gefüllt wird, was nicht so gefüllt werden sollte - also das Isolieren von reinem Wort gegenüber validen Kürzungen.

Was mir hierbei aber auch gerade einfällt, ein Wort das eine Abkürzung enthält, aber nicht "expandiert" werden soll mit dem "Wortbaustein", könnte "geflaggt" werden - so das man das Wort / die Zeichenfolge unverändert lässt. Find ich gar nicht sooo schlecht. Man könnte auch "Werbung#01" (#01 = ung) z.b. das Wort flaggen. Also "Werbung.#01." - also einen Schutzraum um das Wort bilden durch zwei Steuerzeichen für einen Dekompressor. Wäre jetzt meine Idee, wobei das zwei Extra Byte sind... was ein Rattenschwanz :D
 
Zuletzt bearbeitet:

Roin

Freier Denker

Registriert
22 Juli 2013
Beiträge
581
Wenn ich demnächst mal Zeit habe, werde ich mich an einer kleinen Datenkompression auch mal versuchen (dann aber in Java oder Python). Ganz unabhängig von der Laufzeit, die es benötigen darf.
Mich interessiert dabei nur, ob ich die 50% knacke oder nicht.
Die ganzen speziellen Vorgehensweisen, die sich kluge Leute in der Vergangenheit ausgedacht haben, sind mir dann doch einfach etwas zu... speziell.

Eine Idee wäre allerdings ganze Satzteile zu ersetzten also "a special task" zB durch #5 zu ersetzten und #5 dann noch einmal durch "a#4#3" zu ersetzten. So könnte man für das Wörterbuch noch einmal ein Wörterbuch erstellen. Das könnte vermutlich noch das eine oder andere % rauskitzeln.

Ich melde mich einfach mal in einigen Tagen/Wochen, was ich da so geschafft habe ;-)
 

theSplit

1998
Veteran Barkeeper

Registriert
3 Aug. 2014
Beiträge
28.561
  • Thread Starter Thread Starter
  • #12
@Roin

Schön das es dich auch in den Finger kitzelt, so soll das sein! :T

Mein Versuch mit den 57% ist eh etwas hinfällig, wie schon vorher mal geschrieben, weil ich die Daten nicht zurückgewinnen kann, auch wenn es minimal noch möglich sein sollte etwas daraus zu konstruieren, aber nicht alles. ;)

Und die Sprache sollte eigentlich egal sein! :)
 

Roin

Freier Denker

Registriert
22 Juli 2013
Beiträge
581
@theSplit:
Mein Ansatz wäre aber ähnlich.
Beim Lesen der Aufgabe habe ich einfach gedacht, dass ich alle Wörter durch entsprechende Zahlen ersetze und anschließend alle Wörter aufschreibe (also alle Wortkonstrukte) und diese durch ein Trennzeichen trenne. So muss ich etwas weniger Zahlen im Wörterbuch speichern, als du es musst und die Rekonstruierbarkeit sollte gegeben sein.
Dann sollte ich bei ~55 - 60 % sein. Danach würde noch Optimierung kommen (Bitstrom statt ganze Bytes, mehrfach-Konstrukte ersetzten, Wörterbuch für das Wörterbuch, Flags). Ich vermute damit sollte ich auf 45% kommen. Wird sich dann ja zeigen, wie nah ich mit meiner Schätzung liege.
 

theSplit

1998
Veteran Barkeeper

Registriert
3 Aug. 2014
Beiträge
28.561
  • Thread Starter Thread Starter
  • #14
Naja, dann bin ich ja nicht so falsch in meiner Herangehensweise wenn du es ähnlich machen würdest. :)

Ob du darunter kommst, wie gesagt, es muss wiederherstellbar sein aus dem Kodierten ohne Fehler - kann aber gut möglich sein. :)
Ich hab ja nur mal aufgeschrieben was ich so als erste "Ideen" ganz naiv gehabt habe und was ich probiert habe, ohne mich jetzt mit irgendwelchen Algorithmen auseinander zu setzen.

Wäre schön wenn du dann mal ein Beispiel - so fern es lesbar ist, posten könntest wie deine Quellausgabe für den Dekompilierer aussieht.

Finds aber gerade sehr cool wenn es die Leute hier motiviert sich auch daran zu machen. ;)

Darum ging es mir mit dem Thread auch, und das gegenseitige Lernen dabei! :T
 

Larius

OutOfOrder

Registriert
12 Juli 2013
Beiträge
5.792
Interessantes Thema. Ich werde es mir am Wochenende mal zu gemuete führen. Ich weiss nur nicht ob mein Ansatz praktikabel ist.
 

Seedy

A.C.I.D

Registriert
13 Juli 2013
Beiträge
22.571
So auf Wunsch, schreib ich meine Ideen nochmal hier:

1. Hast du auch Wortgruppen zusammen gefasst, oder nur Wörter?

Also
"is" "an"
oder
"is" "an" "is an"

Damit müsstest du beim Einlesen zwar ne Prüfung aufs nachfolgende Wort einbauen.
Solltest aber gesamt einige MB in den Positionsangaben sparen.

2. "Worthülsen"

Sind quasi Wortgruppen, die von einem anderen Wort unterbrochen werden.

z.b "as __ as" oder "the __ of"

Wenn du hinbekommst, dass er nicht Wortweise, sondern Satzweise einließt UND beim Encoden mit einem Positionseintrag die Stellen Vor und Hinter dem ___ füllen könnte.

Müsste das bei Englisch eigentlich etwas ausmachen.

3. Groß und Kleinschreibung.
speicher alles klein, und mach ein Marker, dass er groß schreiben soll.
Im englischen werden nur Satzanfänge und Eigennamen großgeschrieben.
Der Marker für Großbuchstaben kann also an das Satzzeichen "." gekoppelt werden.

Wie oben erfordert es, dass die Wörter nicht für sich, sondern abhängig vom vorhergehenden und folgenden codiert werden.

Eigennamen treten häufig in Gruppen auf, so das du den Capitol Marker auf Gruppen von 3-4 Wörtern anwenden kannst.

4. Wenn du noch weiter gehen willst.
Suffixe und Prefixe abkoppeln.

wie z.B. bei Anti-religious.
Das du anti- und religious getrennt aufnimmst und hinterher zusammen bastelst.
Dann kannst du dir ein Seperates Prefix/Suffix Wörterbuch aufmachen.
Dann kannst du Anti- mehrfach verwenden.

Noch eine Stufe härter wäre, die Wörter zu zerteilen.
Also statt Anarchism, Anarcho, Anarchist
Anarch
+
ism/o/ist

Da ist/o/ism relativ häufig vorkommen, würdest du das Wörterbuch damit auch nochmal kürzen

Nachtrag zu 4. ist:
Es gibt im englischen nur eine Handvoll wiederkehrender "fixe".
Damit würde man das Wörterbuch kürzen.

Dann würde beim Entpacken erst das Wörterbuch zusammen gebaut, danach die Datei selber.
 

dexter

Cloogshicer®
Teammitglied

Registriert
14 Juli 2013
Beiträge
5.312
So auf Wunsch, schreib ich meine Ideen nochmal hier:
speicher alles klein, und mach ein Marker, dass er groß schreiben soll.
Öhm, wird nicht bei normaler Wörterbuch-kompression schon mit Markern gearbeitet? Man schreibt doch wohl kaum "hello" und "Hello" ins Wörterbuch? Ich hab da überhaupt keinen durchblick, denke aber, dass das im Vergleich zu normalen Packern nix spart.

edit: zur 4.: macht man sowas nicht auch bereits?
 

Seedy

A.C.I.D

Registriert
13 Juli 2013
Beiträge
22.571
Öhm, wird nicht bei normaler Wörterbuch-kompression schon mit Markern gearbeitet? Man schreibt doch wohl kaum "hello" und "Hello" ins Wörterbuch? Ich hab da überhaupt keinen durchblick, denke aber, dass das im Vergleich zu normalen Packern nix spart.

Das kommt ein wenig auf das zu komprimierende Objekt an.
Mit dem Marker sparst du 50% Wörterbuch.
Die Frage ist allerdings wie häufig du den Marker verwendest.
Im Deutschen kann es dir schnell passieren, dass die häufige Großschreibung, die jedesmal einen Marker benötigt, am Ende mehr Platz kostet als die zugehörigen Wörterbuch Einträge.

--- [2016-04-20 19:34 CEST] Automatisch zusammengeführter Beitrag ---

edit: zur 4.: macht man sowas nicht auch bereits?

Weis ich nicht, die Frage ist ja ob Split es macht :D
und
Ob es überhaupt was bringt, oder nach hinten los geht.
 

theSplit

1998
Veteran Barkeeper

Registriert
3 Aug. 2014
Beiträge
28.561
  • Thread Starter Thread Starter
  • #19
Seedy, danke das du deine Ideen hier gepostet hast :)

Ich habe mal ein Testfile eines 1,1 MB Auszugs der 100 MB gemacht und darin die Wörter nach Vorkommen absteigend sortiert.

Hier mal ein Auszug der Datei, die "Top 50" Analyse - ich werde das gleich mal für das große File laufen lassen.... (die kleine Übersicht ist auch dem Beitrag angefügt, hier: Anhang anzeigen tmpfile.txt)

Ich lass das mal unkommentiert im Raum stehen, hierbei wird aber Groß- und Kleinschreibung nicht gesondert behandelt, really stupid daher ;)

Vorkommen - Wort
[src=text] 6635 the
5110 of
3649 and
2779 in
2577 to
1916 a
1466 is
1253 |
1045 as
1001 that
884 by
864 *
850 The
804 for
778 was
705 with
616 on
569 his
542 or
519 from
515 are
440 be
434 an
418 |-
410 he
365 not
365 at
361 which
357 have
355 In
347 it
343 =
307 has
262 also
254 this
251 who
241 were
227 such
226 but
225 their
223 Atlas
222 had
216 other
211 one
205 He
204 its
190 been
188 they
187 align="right"
186 <page>[/src]


----------------

Was wäre meine nächste Idee?

Ich habe alle Wörter und deren Aufkommen schon im Speicher, in einer Datei ausgegeben ist diese Liste, mit einem minimalen Aufkommen von 10. Alles darunter habe ich nicht in den Index gelegt.
Basierend auf dieser Datei könnte man nun anfangen diese Kandidaten, so die Idee, der Reihenfolge nach mit Synonymen zu versehen, wobei man IMO lediglich die Längsten bevorzugen sollte vor den kleinsten Elementen.

Gutes Beispiel:
[src=text]align="right"[/src]

wird mit

[src=text]:0:[/src]

gekürzt - das wäre dann ein Ersparnis von:
(24 - 3) * 178 = 12816 Bytes

Wenn wir das mit dem Wort "which" machen, was dann ":1:" bekommt:
(5 - 3) * 361 = 722 Bytes

usw... wobei man auch sagen muß, diese am häufigsten auftauchenden 2 Zeichen ("as", "is") würde ich dann einfach ignorieren weil ich diese ja nicht mit 3 Zeichen effektiv kürzen kann.
 

Roin

Freier Denker

Registriert
22 Juli 2013
Beiträge
581
@Seedy:
1 mache ich ebenfalls, allerdings auch nur mit maximal 2 Wörtern.

2 mache ich derzeit noch nicht, habe ich bisher gar nicht dran gedacht, klingt aber eigentlich logisch. Leider ist Python (die Sprache, in der ich gerade schreibe...) nicht wirklich schnell, wodurch das alles etwas dauert zu testen.

3 mache ich seit eben auch - allerdings nur für einzelne und zwei Zusammengefasste Wörter.

4 ist mir derzeit noch etwas zu "hoch" - Ich denke ich muss den rest erst noch etwas optimieren


wobei man auch sagen muß, diese am häufigsten auftauchenden 2 Zeichen ("as", "is") würde ich dann einfach ignorieren weil ich diese ja nicht mit 3 Zeichen effektiv kürzen kann.
Ich mache es so, dass ich vorher die Datei nach bestimmten Konstrukten durchsuche.
Ich habe beispielsweise eine kleine Liste an Zeichen (,.-_° usw) und überprüfe, ob es in der Datei das Zeichen, gefolgt von einer Zahl bereits existiert. Wenn nichts, nehme ich dieses in meinen Zeichenvorrat auf.
Und nun werden Wörter beispielsweise mit ,7F ersetzt und Leerzeichen durch .4 oder .5 (je nach Vorkommen).

Ich habe natürlich dadurch den Nachteil, dass ich ggf. nur 2 Zeichen habe, die ich für meine Ersetzungen nutzen kann, wodurch ich dann nur einige meiner einzelnen Schritte durchführen kann, da ich auch mit seperierten Wörterbüchern arbeite.
Das muss ich aber alles noch optimieren.
Ich hätte gedacht, dass mein erstes Wörterbuch effektiver ist, aber ich komme nur auf 15-25 % Komprimierung (Ich arbeite zum Testen ebenfalls mit der Datei von theSplit).

EDIT:
Ich habe gerade mal das mit der Groß und Kleinschreibung getestet mit der 1MB Datei.
Obwohl das Wörterbuch eigentlich hätte kleiner werden sollen und ich lediglich ein anderes Steuerzeichen nutze, ist die Kompression um etwa 1% schlechter geworden. Finde ich etwas suspekt. Vermutlich habe ich doch irgendwo einen Programmfehler.
 
Zuletzt bearbeitet:
Oben