Effiziente Kompressionsverfahren

[Marphy]

Hallo zusammen,
ich suche effiziente OpenSource-Kompressionsverfahren (z.B. 7Zip) für mein aktuelles Delphi-Projekt.

Diese sollten folgende Punkte erfüllen (der Priorität nach geordnet):

• möglichst schnell
• hohe Abwärtskompatiblität (das Verfahren sollte auch noch unter einem 486-Prozessor, 16 MB RAM und Windows 95 laufen können)
• möglichst geringer Ressourcenbedarf
• hohe Kompressionsrate
• im Code möglichst kompakt

Ich hoffe, ihr könnt mir ein paar Adressen etc. nennen...
Ach ja: CompressionStream bzw. (De)CompressBuf (Unit ZLib) ist mir schon bekannt :wink:

Danke für eure Postings!
Grüße, Marco

[jfheins]

Wie wäre es mit einem Huffman-Alsorithmus ?

[Robert Marquardt]

Besser geht es kaum.

[Luckie]

7Zip ist übrigens OpneSource, so weit ich weiß. Das sollte eigentlich alle deine Wünsche erfüllen.

[Marphy]

Hallo Michael,

Zitat:

Zitat von Luckie

7Zip ist übrigens OpneSource, so weit ich weiß. Das sollte eigentlich alle deine Wünsche erfüllen.

Ist mir schon bewusst, nur wo herunterladen?!

Marco

[flomei]

Das Orakel befragen hilt bei allerlei Fragen... ;)

MfG Florian :hi:

[Die Muhkuh]

Zitat:

Zitat von Marphy

Hallo Michael,

Zitat:

Zitat von Luckie

7Zip ist übrigens OpneSource, so weit ich weiß. Das sollte eigentlich alle deine Wünsche erfüllen.

Ist mir schon bewusst, nur wo herunterladen?!

Marco

http://www.7-zip.org/download.html

[edit] Schon wieder so ein toter Kasten [/edit]

[Marphy]

Danke Manuel!

Dann werd ich mich mal ran machen. Für weitere Krompressionsverfahren bin ich natütlich auch weiterhin offen. :wink:

Gruß + Dank, Marco

[Robert Marquardt]

Generische Kompressionsverfahren ohne Wissen ueber die Daten gibt es eigentlcih keine anderen.
Die Huffman-Familie mit Zlib als freie Variante und die arithmetische mit bzip2 (unf glaube ich 7zip).
Es kann kein effizienteres Verfahren geben ohne Information ueber die Daten.
MPEG z. B. nutzt die Aehnlichkeit aufeinanderfolgender Bilder.

[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.

[Dust Signs]

Zitat:

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:

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:

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? :stupid: 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! :thumb:

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... :stupid: :wink:

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. :gruebel:
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 :-D )

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

[Dax]

Zitat:

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://www.delphipraxis.net/images/p...marksearch.gif :arrow: 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 :oops:. 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)

[Dax]

Danke, ich sehs mir mal an :)

BtW: Ich habe den Huffman nicht implementiert, das war ein anderes fähiges angemeldetes Wesen ;)

read you,
Dax

[neogen]

Ich sehe grad, dass es um schnelle compression geht :) Also ich koennte hier noch

http://www.bitsum.com/jcalg1.htm

empfehlen, der macht sich gut und ist open source. und auch noch klein.

Folgendes wird erfuellt

• möglichst schnell - er ist schnell!
• hohe Abwärtskompatiblität (das Verfahren sollte auch noch unter einem 486-Prozessor, 16 MB RAM und Windows 95 laufen können) - weiss ich aber nicht genau, aber ist open source und in assembler
• möglichst geringer Ressourcenbedarf - das macht er!
• im Code möglichst kompakt - das ist er wirklich!

die kompressionsrate geht so, aber wenns schnell sein muss ist der hier gut :D

ich nutze den oefter fuer kleinere datenbanken und aehnliches, die in einen eigen format gespeichert werden.

cheers, neogen :)

PS: download http://www.bitsum.com/files/jcalg1_r534.zip

[Marphy]

Hallo zusammen!
Ich habe ein kleines Testprojekt zum Vergleichen der vielen vorgeschlagenen Kompressionsverfahren geschrieben (siehe Anhang).

Zwei Probleme:

• von alzirmar vorgeschlagenes, "sauschnelles" Verfahren funktioniert mit größeren Datenmengen nicht... Hab ich die Funktion falsch aufgerufen?
• JCALG1 (vorgeschlagen von neogen) läuft nur äußerst langsam.... Da ich Jordan Russells Interface-Unit aufgrund von der fehlenden OBJ-Datei nicht zum Laufen bringen konnte, habe ich diese einfach selbst geschrieben. Was hier schiefgelaufen ist, weiß ich jedoch nicht.

Hoffentlich wisst ihr weiter... :gruebel:

Gruß, Marco

[alzaimar]

Das von mir vorgeschlagene Verfahren funktioniert nur in Chunks à 32k (oder 64?). Schau einfach in den Code, dann siehst Du die Words. Wenn Du deine Daten so aufteilst, dann klappt das. Dann ist der Output eben immer ein Tupel (Länge, DATA) und nicht ein einziger Stream.

Übrigens ist es nicht 'fair' ein Kompressionsverfahren auf Zufallsdaten anzuwenden. Ein perfekter Zufallszahlengenerator zeichnet sich ja gerade dadurch aus, das er keine Redundanz erzeugt. Es wird sogar gemunkelt, das das Ergebnis einer Kompression (also der bytestrom) als sehr perfekter Randomgenerator taugt.

Viele Kompressionsverfahren, die in der freien Wildbahn recht schnell sind, beissen sich performancemässig an Zufallszahlen die Zähne aus. Nimm doch lieber Sourcecode oder irgendwelche EXE-files.

Ich habe dein testprogramm ein wenig modifiziert, damit 'mein' Kompressor auch zum Zug kommen kann und siehe da: Er versagt bei random-dateien und liegt ansonsten zwischen Huffman und zlib.

Ich habe einfach die EXE als Input genommen.

[Dust Signs]

@alzaimar: Könntest du uU eine EXE hochladen? Hab grade kein Delphi da und würde mir das gerne mal ansehen

Vielen Dank
Dust Signs

[Vjay]

Es wäre zuckersüß einen Beitrag einzugeben, nur um auf den Attachment hinzufügen-Button drücken zu dürfen?... seltsam

[alzaimar]

@Vjay: PrecTimer war im vorherigen Attachment drin und bei mir aus Gründen, die meinem Nick zu entnehmen sind, nicht. Unabhängig davon verstehe ich deine Zeilen nicht, aber der Sinn wird über die PNG klar.

@Dust Signs & Rest: Exe im Anhang

[Dust Signs]

Zitat:

Zitat von alzaimar

@Dust Signs & Rest: Exe im Anhang

Da fehlt eine DLL...

Dust Signs

[alzaimar]

Du wolltest nur die EXE, von DLL war keine Rede. Gibts nur gegen Aufpreis. Und überhaupt, sei nich so pingelig, is ja furchbar :mrgreen:

[Vjay]

Hab dann noch bzlib2 eingefügt.

Zitat:

davon verstehe ich deine Zeilen nicht

Diese Fehlermeldung kommt vom Board wenn du versuchst ein Attachment hochzuladen ohne vorher Text eingegeben zu haben.

[Marphy]

Hallo zusammen,
danke für die rege Beteiligung... Hätte ich nicht erwartet :-D

Zitat:

Übrigens ist es nicht 'fair' ein Kompressionsverfahren auf Zufallsdaten anzuwenden. Ein perfekter Zufallszahlengenerator zeichnet sich ja gerade dadurch aus, das er keine Redundanz erzeugt. Es wird sogar gemunkelt, das das Ergebnis einer Kompression (also der bytestrom) als sehr perfekter Randomgenerator taugt.

Und es ist auch nicht fair, meinen "Daten-Erstellungs-Algorithmus" so "runterzumachen" :evil: :wink:
So zufällig sind die Daten ja eben gar nicht, was man auch an der Kompressionsrate sehen kann/konnte.

Zitat:

Ich habe dein testprogramm ein wenig modifiziert, damit 'mein' Kompressor auch zum Zug kommen kann und siehe da: Er versagt bei random-dateien und liegt ansonsten zwischen Huffman und zlib.

Danke! Hmm, also habe ich nur die falsche Funktion aufgerufen (knapp daneben ist auch vorbei)...

Zitat:

Hab dann noch bzlib2 eingefügt.

Danke ebenfalls. Woher der Source?

Mal sehen, vielleicht werde ich bei Gelegenheit auch noch 7Zip "verbauen"... Werd mich mal im Inno Setup Source schlau machen... :mrgreen:

Grüße, Marco

[Marphy]

Ich bins nochmal...

Hat vielleicht jemand eine Idee, was bei JCALG1 schief läuft? Hat ja die beste Kompression, aber für einen hochoptimierten ASM-Algorithmus sieht das performancemäßig ja nicht gerade aus:
Über fünf Sekunden braucht das Ding für 51% Kompression bei mir :gruebel:

Gruß, Marco

[Marphy]

No ideas? :hi:

[alzaimar]

DEr JCALG1 Algorithmus implementiert den LZSS-Algorithmus. Das ist (soweit ich das korrekt überflogen habe) ein LZW mit zusätzlichem 'sliding window'. Entweder wird eine Zeichenkette als eintrag im Wörterbuch (LZW) kodiert, oder als "jetz kommen X Zeichen, die auch schon an Y Zeichen vorher vorkamen" kodiert wird. Je nachdem, was kürzer ist.

Ich habe mir die Implementierung von JCALG nicht angeschaut, aber könnte mir vorstellen, das das sliding Window nicht optimal umgesetzt wird. Im Übrigen bringt der JCALG1 bei mir nicht die besten Ergebnisse. Hier ist zlib vorne. Da es zudem schnell genug ist, würde ich das benutzen. Tu ich ja auch.

[Marphy]

Hallo zusammen,

Zitat:

Zitat von alzaimar

Hier ist zlib vorne. Da es zudem schnell genug ist, würde ich das benutzen. Tu ich ja auch.

Du meinst wohl ZLibEx?!

@neogen: Du bist jetzt besonders angesprochen :tongue: Schnell ist der JCALG1 eben nicht. Mach ich was falsch?!

Grüße, Marco

[alzaimar]

Latürnich ZlibEx... Ich meinte das eher als "die Z-Lib(rary)"

[Marphy]

Hallo alzaimar,

Zitat:

Zitat von alzaimar

die Z-Lib(rary)

will dich ja nicht nerven, aber die integrierte ZLib(rary) ist alles andere als schnell... :stupid:

Gruß, Marco

[alzaimar]

Mann, hast Du mich jetzt durcheinander gebracht. Ich wusste gar nicht, das zlib bei delphi mit dabei ist...
Natürlich die ZLibex.

[Marphy]

:-D Sowas auch :nerd: :wink:

[Marphy]

Hallo zusammen,
endlich habe ich mal wieder etwas länger Zeit gehabt und das Projekt ziemlich umfangreich überarbeitet. Neben einigen neuen nützlichen Features habe ich auch die neueste Version von ZLibEx, 1.2.2, hinzugefügt.

Ich freue mich über euer Feedback! :thumb:

Gruß, Marco

P.S.: Falls ihr etwas im Projekt ändert und hier hochladet, setzt doch bitte die Ausgabe-Versionsnummer um eins hoch. Danke! :-D