Datenkompression

Michael E.

Hi,

ich will mich näher mit Komprimieren beschäftigen. Algorithmen wie Huffman, LZ77 und arithmetisches Kodieren kann man zwar über Wikipedia lernen (hab ich auch gemacht), aber ein bisschen tiefer wollte ich schon einsteigen. Wer kennt gute Seiten zur Komprimierung allgemein (d.h. ohne spezielle Algorithmen abzuhandeln) sowie Erklärungen zu anderen Algorithmen als dne oben genannten? Ich wollte im Bereich verlustfreie Komprimierung bleiben. Meine Mathekenntnisse sind nicht sehr ausgeprägt.

[EDIT] Wie gut ist eigentlich http://www-user.tu-chemnitz.de/~mfie/compproj/index.htm , auf das der Wikipedia-Artikel Datenkompression verlinkt?

Taurin

Du könntest mal versuchen, dir den Begriff der Entropie genauer anzuschauen. Dabei wird allgemein darauf eingangen, in wie weit Compression überhaupt möglich ist.

rapso

Michael E. schrieb:

kann man zwar über Wikipedia lernen (hab ich auch gemacht), aber ein bisschen tiefer wollte ich schon einsteigen

Michael E. schrieb:

Wer kennt gute Seiten zur Komprimierung allgemein (d.h. ohne spezielle Algorithmen abzuhandeln)

das wiederspricht sich, wenn du tiefer einsteigen möchtest, mußt du dir die algorithmen anschauen. wenn du was allgemeines ließt, ist es highlevel und deswegen nicht "tiefer".

wobei es nicht sonderlich viel allgemeines gibt da die algorithmen immer die sache auf ne spezielle art und weise angehen.
grundsätzlich gibtes den unterschied zwischen algorithman die patternmatching durchführen (z.b. RLE,LZW), algorithmen zur entrophie an sich (z.b. Huffman) und transformationsalgorithmen die im grunde keine kompression durchführen (oft werden die datenmengen dabei sogar größer) um die daten aufzubereiten z.b. BWT oder prediction.

viel mehr gibt es im "allgemeinen" nicht zu sagen. zum tiefer einsteigen einfach alle algorithmen durchgehen und verstehen.

rapso->greets();

Michael E.

Danke euch beiden. Jetzt weiß ich, was ich während dem Zeltlager tu *ganzfreakigguck*

willst du später mal datenkompressionist werden??

Würd mir schon reichen, wenn er bzip2 nochmal verbessern könnte.

Michael E.

@frage: Ich glaub kaum, dass ich da Erfolgsaussichten hab. Aber mich interessierts.

Optimizer: Reichts dir, wenn ich in zwei Jahren fertig bin? :p

Hmmmmm, dann will ich aber, dass er im durchschnittlichen Fall mindestens 3mal so gut komprimiert wie jetzt.
Alternativ darfst du auch einen Algorithmus entwickeln und zu dem mathematisch beweisen, dass keine bessere Kompression mehr möglich ist.

rüdiger

bzip2 ist doch schon okay. Der Algorithmus sollte lieber beschleunigt werden, so dass man auf gzip verzichten kann (zB. für HTTP und andere on-the-fly-komprimierung)

volkard

kingruedi schrieb:

bzip2 ist doch schon okay. Der Algorithmus sollte lieber beschleunigt werden, so dass man auf gzip verzichten kann (zB. für HTTP und andere on-the-fly-komprimierung)

fenstergröße runter und die bwt ist auch schnell.

bzip2 komprimiert bei mir in der Praxis bei schlecht komprimierbaren Daten höchstens um 1-2% besser als Formate wie zip rar oder gzip. Ich kann mir vorstellen, dass der Vorteil vollends dahin ist, wenn man die BWT auf Geschwindigkeit trimmt.
Zum Beschleunigen ist vielleicht der gzip besser geeignet. Man sollte einen Algorithmus haben, der geil packt und dafür auch ne Stunde für 100MB brauchen darf und einen, der schnell packt. bz2 packt mir noch nicht gut genug. Da ist mir meistens der Punkt, dass es patentfrei ist, wichtiger als das eine Prozent.