Effiziente Kompressionsverfahren

[Dust Signs]

Zitat von alzaimar:

Der hier in der Codelibrary gepostete Huffman Algorithmus hat Nichts, aber auch gar Nichts mit effektiven Kompressionsverfahren und inbesondere dem adaptiven Huffman Coding zu tun. Er implementiert den einfachen Brute Force Entropieverdichter, ein netter Algorithmus zum Üben, er eignet sich jedoch überhaupt nicht für den praktischen Einsatz. Ich weiss nicht, wieso das keiner ausprobiert.

Ich habe hier eine 110MB Datenbank (MSSQL), die sich wunderbar verdichten lässt. Die Kompressionsrate von 'Hufman' liegt bei ca 55%. Das ist schlecht. Sehr schlecht. Wie man dann behaupten kann, besser ginge es nicht, der kennt wohl kein LZW, LZSS oder BZIP usw.

RAR (adaptives Huffman Coding) kommt auf 95%,
Pkzip auf 91%. Zlib liegt gleich auf, was daran liegt, das die in PKZIP verwendeten Verfahren implementiert wurden.
Lz
Ich verwende in meinen Applikationen Zlib, da die Geschwindigkeit ordendlich und die erzielten Kompressionsraten ausreichend sind. Ich würde RAR nehmen, aber leider gibt es den Packer, soweit ich weiss, nicht als Code.

BZIP (oder Markov) soll zwar besser sein, die mir vorliegende Sourcen schaffen das aber nicht.

Es geht hier aber um schnelle Kompressionsverfahren, wie du ohne Zweifel dem ersten Beitrag entnehmen kannst. Und RAR ist bei den Kompressionsraten, die du ansprichst, alles andere als schnell...

Dust Signs

[Matze]

@Dust Signs: Bitte zitiere doch nur den Teil des Beitrags, den du für deine Stellungnahme auch benötigst, das liest sich deutlich besser, danke.

Zitat von Dust Signs:

Es geht hier aber um schnelle Kompressionsverfahren [...]

Ebenfalls aber auch um eine hohe Kompression und ähnliches (siehe Beitrag #1). Und eine hohe Kompression bietet nunmal RAR. Langsam ist es nicht, aber auch nicht das Schnellste.
Ich denke allerdings auch, dass Schnelligkeit und eine hohe Kompression einen Widerspruch darstellen. Je besser die Kompression, desto länger dauert das Komprimieren. Zumindest habe ich es bei den Kompressionsprogrammen, die ich nutze so festgestellt.

[tommie-lie]

Zitat von Dust Signs:

Es geht hier aber um schnelle Kompressionsverfahren, wie du ohne Zweifel dem ersten Beitrag entnehmen kannst. Und RAR ist bei den Kompressionsraten, die du ansprichst, alles andere als schnell...

BZip2 in Software iss auch nicht schnell
Wo wir schon dabei sind, darf ich wieder mit meinen obligatorischen non-PC-Plattformen kommen? Man könnte ja Kompressionsalgorithmen in Hardware gießen, idR schneller als auf einem RISC

[alzaimar]

@Dust Signs: Ich habe das 'schnell' schon gelesen. RAR ist schon ok, schneller als die mir vorliegende zlib-Version, soweit ich mich erinnere. Natürlich nicht so schnell wie PKZIP, aber ausreichend. Da die Kompressionsrate von RAR jedoch unerreicht ist, kommt RAR für mich als perfekter Kandidat in Betracht. Aber, das ist Geschmacksache. Wichtig war mir, das hier Dinge gepostet werden, ohne sie mal nachzuprüfen.

Von der Schnelligkeit her würde ich LZW Verfahren nehmen. Das ist sauschnell. Aber eben nicht sonderlich effizient. Probier das hier mal aus. Das ist zwar nur Delphi (kein ASM), aber geht wirklich ab wie Sau. Vielleicht reicht es Dir ja.

Ich habe auch den LZH Code als Delphi-Version probiert. Aber der ist einfach zu langsam.

[Marphy]

Hallo zusammen,
danke erstmal für die rege Beteiligung!

Zitat:

Der hier in der Codelibrary gepostete Huffman Algorithmus hat Nichts, aber auch gar Nichts mit effektiven Kompressionsverfahren und inbesondere dem adaptiven Huffman Coding zu tun. Er implementiert den einfachen Brute Force Entropieverdichter, ein netter Algorithmus zum Üben, er eignet sich jedoch überhaupt nicht für den praktischen Einsatz. Ich weiss nicht, wieso das keiner ausprobiert.

Danke für den Hinweis, alzaimar!

Zitat:

Ich denke allerdings auch, dass Schnelligkeit und eine hohe Kompression einen Widerspruch darstellen. Je besser die Kompression, desto länger dauert das Komprimieren.

Natürlich. Ich habe nur die Forderung gestellt, dass der Algo möglichst schnell sein, dabei aber auch eine möglichst hohe Krompression bieten soll. Wenn es mit nur um Schnelligkeit ginge, würde ich nicht auf die Idee kommen, die Daten zu komprimieren.

Zitat:

Man könnte ja Kompressionsalgorithmen in Hardware gießen, idR schneller als auf einem RISC

Tolle Idee! Wahrscheinlich werde ich gleich eine kleine PCI-Karte basteln, dem Setup meiner Freeware beilegen und das Ganze dann zum Download anbieten...

Zitat:

@Dust Signs: Ich habe das 'schnell' schon gelesen. RAR ist schon ok, schneller als die mir vorliegende zlib-Version, soweit ich mich erinnere. Natürlich nicht so schnell wie PKZIP, aber ausreichend.

PKZIP ist höchstwahrscheinlich C++ oder gar Assembler. Wenn Delphi die gleiche Kompressionsmethode in seiner ZLib implementiert, ist diese "schlampig" geschrieben, Delphi nicht sonderlich schnell oder beides zusammen.
Bisher dachte ich jedenfalls, Delphi langt von der Performance her knapp an C(++) heran.

Zitat:

Von der Schnelligkeit her würde ich LZW Verfahren nehmen. Das ist sauschnell. Aber eben nicht sonderlich effizient. Probier das hier mal aus. Das ist zwar nur Delphi (kein ASM), aber geht wirklich ab wie Sau. Vielleicht reicht es Dir ja.

Werde ich auf jeden Fall mal ausprobieren. Danke!

Gruß, Marco

[alzaimar]

Was PKZIP und zlib anbelangt, darfst Du nicht vergessen, das der gute Phillip Katz ('PK') sich einen abgebrochen hat, damit sein Tool die #1 wird. Also hat er optimiert, was das Zeug hält. Zlib ist 'nur' eine normale ASM-Implementierung, die natürlich noch Optimierungspotential hat. Beim LZW-Algorithmus z.B. gibt es ein Wörterbuch, das immer weiter wächst. Irgendwann wird es zu gross und muss 'bereinigt' werden. Ich meine, das PkWare das genaue WIE und WANN der 'Dictionary-Reinigung' nicht verraten. Gerade DAS macht aber noch einige Prozente in der Komprimierungsrate aus.

Die Geschwindigkeit von zlib hat m.E. nichts mit Delphi vs. C(++) zu tun, sondern mit Algorithmen und Optimierungen: "Ein BubbleSort in ASM ist immer langsamer als ein Quicksort in JavaScript." (Gut, bei mehr als 1000 Elementen )

Teste einfach mal zlib. Ich weiss nicht, welche Version Du hast. Ich habe die hier und mir reichts (ich wiederhole mich)

[Dax]

Zitat von alzaimar:

Der hier in der Codelibrary gepostete Huffman Algorithmus hat Nichts, aber auch gar Nichts mit effektiven Kompressionsverfahren und inbesondere dem adaptiven Huffman Coding zu tun.

Das ohne Zweifel, der Code is nach eigenen Aussagen nicht optimiert Und da du es gerade ansprichst: Wie funktioniert diese Kompressionsmethode denn genau? Entweder suche ich falsch oder ich bin blind

read you,
Dax

[jfheins]

Huffman + http://de.wikipedia.org/wiki/Huffman

[Dax]

Ach Heinz Wie Die Huffman-Kodierung funktioniert weiß ich Ich wollt aber was zu adaptive Variante erfahren, und dazu hab ich nix gefunden

[alzaimar]

Ich wollte Dir nix Böses . Es geht ja bei Verfahren erst in zweiter Linie ums Optimieren. Wenn das Verfahren nicht stimmt, dann bringt 'Optimieren' hier auch Nichts. Deine Hufman-Implementierung is ordendlich, darauf kommt es an. Allerdings sollte man schon mal Vergleiche mit in freier Wildbahn auftretenden Packern machen, bevor man euphorisch die Implementierung des Hufman feiert. Aber egal.

Ich habe leider keine akkuraten Beschreibungen oder Listings zum RAR-Verfahren. Das LZH-Verfahren kann ich Dir geben...

Der 'Nachteil' vom von Dir implementierten 'statischen' Huffman Codiung ist:
1. Du musst den KodierungsBaum mitschicken.
2. Du berücksichtigst die Verteilung der Bytes nur in der gesamten Datei.

So, wie ich das verstanden habe, fängt der 'adaptive Hufman' mit einem standardisierten Kodierungsbaum an (Es gibt ein Listing für UNRAR, da steht er drin). Somit entfält Nachteil #1. Dann wird während des Kodierens der Kodierungsbaum immer wieder überarbeitet, um die aktuelle Bytehäufigkeit zu berücksichtigen. Somit entfällt Nachteil #2. Vermutlich stecken noch ettliche kleine 'Optimierungen' drin, um auf diese Kompressionsraten zu kommen: Trivial ist das nämlich nicht.

Am Spannendsten finde ich jedoch die Markov-Verfahren, die doch tatsächlich darauf aufbauen, das nächste Byte zu 'erraten'. Das klappt sogar. Unglaublich. Leider auch extrem langsam.

Hier das LZH-Verfahren (Ziemlich laaaangsam)