Kompression: Matches finden

[BeRsErKeR]

Hallo ich bastel gerade an einer Komprimierung die eine abgewandelte Form von LZW/LZX benutzt. Genauer gesagt gibt es 257 Symbole: 256 für die normalen Byte-Literale und 256 kennzeichnet ein Match. Auf ein Match-Literal folgen dann kodiert die Match-Length und das Match-Offset. Prinzipiell ist dies aber nebensächlich. Was mich interessiert ist der Algorithmus für das Finden eines Matches beim Komprimieren.

Ich hatte bislang 2 Verfahren probiert. Mit kleinen Dateien (kleiner 500 KB) geht das ganze noch in ein paar Sekunden. Bei einem 300MB-Video musste ich jeweils nach 8 Stunden abbrechen, weil er nicht fertig war. Kurz gesagt: Ich muss das anders machen.

Mein erster Versuch war die brachiale Art mit der Brechstange: Für jedes Literal im Input-Stream prüfe ich die window_size letzten Literale auf Matches und wähle das Längste aus. Meine window_size betrug 10, 11 oder 12 Bit bei einer min_match_length von 3. Sprich 1026, 2050 bzw. 4098. Man stelle sich nun eine 300MB-Datei vor: Es sind 314572800 Input-Literale, für die ich jeweils bis zu 1026 (oder mehr) Vorgänger-Literale durchgehen muss. Vernachlässigen wir mal, dass die ersten 3 Bytes kein Match haben können und dass vor dem 1026ten Byte die zu prüfenden Vorgänger-Literale nicht 1026 sind. Dann sind das 322751692800 Schleifendurchläufe und Vergleichsoperationen. Nehmen wir mal grob an er würde das pro Literal in 1 Microsekunde machen, dann wären das immer noch genau 10 Jahre (exakt sogar :) ), die er dafür braucht. Ist also etwas langwierig. ;)

Dann habe ich mal die LZW-Variante probiert, sofern ich sie richtig verstanden habe. Sprich: Wenn ich min_match_length Byte-Literale gelesen habe, packe ich diese in ein Dictionary. Bei einem Literal wird dann im Dictionary nach einem Eintrag im Dictionary gesucht, der passt. Folgt ein Literal, dass kein Match hat, so wird es zusammen mit den letzten min_match_length Byte-Literalen oder dem letzten Match, falls es vorher ein Match gab, kombiniert und ebenfalls ins Dictionary gepackt. Soweit ich LZW verstanden habe packt dieses sogar noch mehr Einträge ins Dictionary. Meiner Einschätzung nach sollte das in jedem Fall deutlich schnell gehen als der obige Ansatz. Allerdings hat er für die 300MB wie gesagt auch über 8 Stunden gebraucht (Dauer ungewiss). Das kann also auch nicht das Gelbe vom Ei sein.

Habt ihr Ideen zu dem Thema? Wie werden denn normal größere Datenmengen komprimiert? Normal dauert sowas ja maximal einige Minuten.

Ich hab auch gelesen, dass Deflate z.B. nach einer gewissen Zeit die Match-Suche abbricht. Aber ist das wirklich schon die Lösung? Die Kompression leidet dadurch ja recht stark.

Als Anmerkung vielleicht noch: Ich habe auch schon probiert die Daten in kleinere Blöcke aufzuteilen (z.B. 32 KB) und darin dann Matches zu suchen. Allerdings scheint das zeitlich nicht wirklich was auszumachen.

Wie gesagt: Ich wäre sehr dankbar für Anregungen und Hinweise.

[simbad]

Man verwendet Chunks mit maximal 64k.
Es wird also nie gegen das ganze geprüft.
Denke ich.
Meine das so gelesen zu haben.
Bei einem Video, das nicht als 24Bit RGB abgelegt ist, also schon eine Kompression durchlaufen hat, ist das Kompressionsergebnis eher gering. Kompression bedeutet immer das Entfernen von Redundanzen, was auch dazu führt, das Textdateien, die verschlüsselt worden sind, nicht komprimiert werden können, da die Daten ja nach dem Verschlüsseln eine Pseudozufälligkeit aufweisen.

[Schrompf]

Wenn es wirklich nur 256 verschiedene Symbole sind, kannst Du doch stressfrei beim Schreiben in einer Tabelle festhalten, an welcher Position das xte Symbol zum letzten Mal aufgetreten ist. Oder meinetwegen die letzten 20 Auftrittstellen in einem kleinen Circular Buffer.

[BeRsErKeR]

Man verwendet Chunks mit maximal 64k.
Es wird also nie gegen das ganze geprüft.
Denke ich.
Meine das so gelesen zu haben.
Bei einem Video, das nicht als 24Bit RGB abgelegt ist, also schon eine Kompression durchlaufen hat, ist das Kompressionsergebnis eher gering. Kompression bedeutet immer das Entfernen von Redundanzen, was auch dazu führt, das Textdateien, die verschlüsselt worden sind, nicht komprimiert werden können, da die Daten ja nach dem Verschlüsseln eine Pseudozufälligkeit aufweisen.

Naja ich verwende auch 32KB-Chunks und ein Suchfenster mit der Größe 4096 (es wird also nur in den letzten 4096 Bytes nach Matches gesucht). Wie gut die Kompression ist, ist erstmal unwichtig. Es geht eher um die Dauer der Kompression.

Wenn es wirklich nur 256 verschiedene Symbole sind, kannst Du doch stressfrei beim Schreiben in einer Tabelle festhalten, an welcher Position das xte Symbol zum letzten Mal aufgetreten ist. Oder meinetwegen die letzten 20 Auftrittstellen in einem kleinen Circular Buffer.

Naja es bringt nichts wenn ich weiß wo das aktuelle Zeichen das letzte mal vorkommt, da ich ja Sequenzen vergleiche. Allerdings könnte man das als Anfang nehme und nur an den Stellen suchen. Allerdings reichen die letzten 20 Auftrittsstellen nicht, wenn das Match z.B. 100 Bytes zurückliegt und dazwischen noch 25 dieser Bytes kamen. Schneller wäre es wohl, aber die Kompression wird dann unter Umständen sehr leiden.


Ich habe mal gelesen wie Deflate das macht. Die benutzen Hash-Werte und Single-Linked-Lists. Allerdings komm ich damit auch auf keinen grünen Zweig. Ich hab nun ein Dictionary, welches Matches mit Hash-Werten aus den Byte-Sequenzen speichert. Im ungünstigen Fall einer Kollision speicher ich die Sequenz nicht in der Match-Table - das wird nicht viel ausmachen, da es selten passiert. Ich denke mal FNV ist schon in Ordnung als Hash-Funktion, wenn man bedenkt, dass es sich nur maximal um 32768 Bytes handelt.

Allerdings braucht jetzt schon ein 450KB Bitmap (viele weiße Flächen) viel länger als vorher und die Kompressionsrate eben dieser ist von 74% (Brechstangenmethode) über 50% (LZW-Abklatsch) auf lächerliche 26% gesunken.


Nachtrag:

Vielleicht war ich zu vorschnell. Die Komprimierung eines 15MB-Videos lief während ich das geschrieben hatte und hat scheinbar keine Minute gebraucht. Allerdings ist wohl was schief gegangen. Ich teste mal weiter.

Nachtrag2:

Ok die Geschwindigkeit scheint nun zu passen (130MB MOV-Datei in weniger als 2 Minuten), allerdings ist die Kompressionsrate nun echt schlecht.

Nachtrag3:

Scheinbar ist viel manchmal weniger. Ich hatte vorher versucht nicht jede Sequenz zu speichern, nun speichere ich wirklich jede. Und überraschenderweise braucht das 450KB Bitmap nun nur noch 4 Sekunden für die Kompression und wird auf nicht mehr ganz so schlechte 179KB geschrumpft.

[BeRsErKeR]

Was jetzt noch fehlt ist das lazy-matching von Deflate. Mal gucken was ich da noch an Kompressionsrate rausholen kann. Ich hab mal ein Test mit einem 32MB Bitmap gemacht was größtenteils gleichfarbige Flächen enthält mit ein paar Kritzeleien drüber. Mein Algorithmus schrumpft das ganze ohne grafik-spezische Kompression auf 1,8MB, PNG auf rund 750KB, JPEG auf rund 250KB und das Win7-builtin-Zip (denke mal das ist auch Deflate) auf 13KB!! Keine Ahnung ob das Win7-Zip bei Standardtypen wie BMP eventuell auch zusätzlich noch Grafikkompressionsalgorithmen anwendet. 1,8MB zu 13KB ist aber schon ein großer Unterschied, obwohl mein Algo schon eine Kompressionsrate von über 94% aufweist. Das Win7-Zip schafft aber stattliche 99,96%, was wohl in diesem Fall auch auf die größere window_size bzw. max_match_length zurückzuführen ist (bzw. auf oben genanntes lazy-matching).

Was ich auch noch optimieren könnte ist, dass zwar das Match-Literal nur sehr wenige Bits (Huffman) benötigt, aber für das kodierte Offset und die kodierte Länge 16-20 Bit. Wenn nun eine Sequenz von z.B. 5 Nullen auftritt (die Null wird sicher auch sehr kurz kodiert), dann wären die Match-Daten eventuell sogar länger als die Daten für diese 5 Literale.

Als Beispiel:

0 ist kodiert als 100 (binär)
Match (257) ist kodiert als 00 (binär)

5 "0-Literale" wären dann 15 Bit groß. Das Match wäre mindestens 18 Bit groß (2 Bit für das Literal und 16 Bit für Offset und Length).

Eventuell würde hier eine Prüfung die Kompression nochmal optimieren. In einem Bitmap treten, wie man sich vorstellen kann, beispielsweise sehr viele 3-Literal-Matches bzw. 4-Literal-Matches auf, die dann meist kürzer sind als die Match-Daten, die aber im Moment noch genutzt werden. Die Matches vergrößeren in diesem Fall quasi wieder die Daten.


Habt ihr noch Ideen für Kompressions-Optimierungen?

[Schrompf]

Evtl. hab ich das überlesen, aber mich verwundert schon, warum Du das überhaupt tust? Ist es zu Studierzwecken? Nach meinem Verständnis kannst Du nur durch Ausnutzung anwendungsspezifischer Korrelationen überhaupt noch Boden gut machen. Für allgemeine Fälle sind die gängigen Kompressionsmethoden kaum noch zu schlagen. Nimm bzip2 - MIT-Lizenz und sowohl in Geschwindigkeit als auch in Ergebnis-Datengröße himmelweit überlegen.

[BeRsErKeR]

Studieren? Lange ists her...

Ne ich durfte mich in letzter Zeit viel mit CHM-Dateien rumschlagen und baue für das Format einen Encoder/Decoder + GUI, die ohne das häßliche COM-Objekt auskommen und womit man Daten direkt editieren kann. Bislang gibt es zwar viele Decoder aber wenig Encoder und die, die es gibt können bzw. wollen wir nicht verwenden, da wir Lizenzen (z.B. für FAR) loswerden wollen.

Und da das abgewandelte LZX für CHMs ziemlich verwirrend ist und man leicht Fehler macht hab ich mich mal an was eigenes gesetzt um Details zu klären und mal was Funktionierendes zu haben. Ich überlege aber auch das neue Format für ein Spieleprojekt von mir zu nutzen. Dabei geht es mir nicht um eine bessere Komprimierung als mit gängigen Formaten, sondern auch um leichte Les-/Schreibbarkeit und vorallem möchte ich auf eine Einarbeitung in ein solches Format verzichten (LZX ist schon grausam genug). Es gibt zwar Bilbiotheken wie zlib und Co, aber mein Spieleprojekt ist ja auch nicht dafür gedacht, ein super tolles Spiel zu machen, sondern dient vorallem Lernzwecken. Da mich Komprimierung allgemein auch interessiert benutze ich das ganze auch um mich weiter in die Materie vorwagen zu können.

[BeRsErKeR]

Mit lazy-matching, variabler chunk_size (die ggf. an die Datengröße angepasst wird) und huffman-encoded Match-Daten, sowie einer höheren max_match_size komme ich nun schon annähernd auf die Deflate-Kompressionsraten. Die Dauer der Komprimierung ist allerdings noch größer, wobei auch große Dateien noch in annehmbarer Zeit komprimiert werden.

Was ich mich noch frage ist, ob huffman-kodierte Match-Daten wirklich gut sind, da sie ja die ggf. vielversprechende Verteilung von Literalhäufigkeiten für bswp. Bitmaps oder Textdateien zunichte machen können. Match-Offsets und Match-Längen können ja relativ beliebig sein und somit alle Byte-Literale in unbestimmter Anzahl hinzufügen. LZX speichert zwar auch Matches mit in die Literal-Huffman-Table, besitzt aber für Längen einen eigenen 249-Element großen Huffman-Tree. Ich glaub ich guck mir nochmal an wie Deflate Match-Daten kodiert. Prinzipiell bin ich aber schon ganz zufrieden.

Mein Ansatz ist folgender:

Tritt ein Match auf, so wird das Match-Indikations-Literal 256 in den Stream geschrieben (huffman-kodiert). Danach folgen 2-3 Bytes mit dem Match-Offset (Distance) und der Match-Length. In den ersten 16 Bit stehen 12 Bits für das Offset (welches somit von 3 - 4098 reicht). 0-2 wäre unmöglich, da die minimal Länge von Matches 3 ist. 3 Bits werden für die Länge benutzt (3 - 10). Dies reicht für viele kleinere Matches aus. Das letzte Bit ist ein Indikator dafür, dass noch Zusatzbits für die Match-Länge benötigt werden. Ist das Bit 1, so ist die Länge größer als 10 und das nächste Symbol (8 Bit) wird mit als Länge interpretiert (insgesamt dann also maximal 11 Bits -> 3 - 2050). Diese 2-3 Bytes werden als normale Byte-Literale (je nach Wert eben von 0-255) in den Stream geschrieben. Die Unterscheidung von normalem Byte-Literal und diesen Match-Daten geschieht durch das vorangestellte Match-Indikations-Literal. Wie gesagt können die 2-3 Bytes alle normalen Byte-Literale annehmen und Verändern dadurch die Häufigkeiten der normalen Literale. Ich bin mir nicht sicher was das für Auswirkungen haben könnte. Prinzipiell erhöht man ja die Entropie.