Komprimierung, Algorithmen, Konzepte, Ideen

Cpp_Junky

Wie funktioniert eigentlich Daten-Komprimierung ?
Bitte keine meterlangen Beispielcodes, sondern nur eine Erklärung was da hinter steckt. Hab im Netz schon irgendwas über "Huffmann"-Algorithmen gefunden, bin aber nicht besonders schlau daraus geworden
Wer hat sowas schon mal programmiert ?

echter Troll

Die einfachste Methode ist eine Zeichenfolge durch ein anderes Zeichen zu ersetzen, zum Beispiel "ei" durch *.
Die *nfachste Methode ist *ne Z*chenfolge durch *n anderes Z*chen zu ersetzen, zum B*spiel "*" durch *.

Huffmann hat etwas mit Binärcodierung zu tun, wenn ich mich recht erinnere ...
Ein rekursives Verfahren, dass die beiden Zeichen mit dem niedrigsten Vorkommen zu einem neuen Zusammengefaßt werden. Ergebnis ist ein Binärbaum. Mehr fällt mir auf Anhieb nicht ein ...

[ Dieser Beitrag wurde am 17.12.2002 um 11:44 Uhr von Marc--us editiert. ]

Cpp_Junky

Hm na gut...
Und was wenn bei dem Beispiel oben der User einen Text mit Sternchen komprimieren will ?
Dann kommt beim Dekomprimieren aber murks raus:

"Viele Programm-Dateien haben einfach die Endung *.exe"
"Viele Programm-Dat*en haben *nfach die Endung *.exe"
->
"Viele Programm-Dateien haben einfach die Endung ei.exe"

Jester

Schau mal nach LZW.
Das Prinzip war so:

Du nimmst mehr als 8 Bit pro Zeichen. Dann liest Du den Text von vorne und schaust immer nach, ob das noch im Alphabet steht, wenn ja, dann weiterlesen. Ansonsten wird der vorhergehende Teil, der noch ein Zeichen im Alphabet besaß als dieses geschrieben, das nächste Zeichen dazu und das ganze Teil kriegt die nächste freie Nummer im Alphabet. Meistens macht man das dann so, daß man die Zeichenbreite von 9 bis ca. 12-14 Bits wachsen läßt und dann irgendwann neu anfängt. Das tolle an der Sache ist, daß man das Alphabet nicht mitspeichern muß, es kann beim dekomprimieren praktisch miterzeugt werden.

GIF Kompression funtkioniert nach diesem Prinzip. Liefert ziemlich gute Ergebnisse. Okay, jedes Zeichen braucht mehr als 8 Bit Speicher, aber wenn man dann in 12 Bit mal 10 oder 15 Zeichen untergebracht hat, dann lohnt sich das schon.

Dann gibts noch RLE, da zählt man immer wieviele Zeichen der gleichen Sorte jetzt kommen schreib als erstes die Zahl (1-255), dann das Zeichen. Das macht allerdings nur in wenigen Fällen wirklich Sinn. Ich glaub pcx arbeitet so. BMP kann man auch RL-Encoden.

Ansonsten google mal nach Wavelet-Transformation.

frenki

Mir fällt noch die Modified-Huffman-Komprimierung ein, die für Monochrom-TIFF's und beim Faxen verwendet wird. Dort sind zwei Bäume fest vorgegeben, einer für weiss und einer für Schwarz, die immer im Wechsel folgen. Die Bit-Folgen, die in Faxen am häufigsten vorkommen, sind am kürzesten kodiert (2 Bit, oder war' gar nur 1 Bit?). Die Fehlererkennung läuft dann über falschen Zeilenlängen (bei A4 z.B. so um die 1700 Pixel pro Zeile). Die Positionen im Baum geben dort einfach nur an, wieviele Bits der entsprechenden Farbe hintereinandergehängt werden. Man kann das auch ohne Baum lösen, ich fand die Baum-Lösung aber schöner.

Also z.B.

1 -> 64 Weisse Pixel
010 -> 32 Weisse Pixel
011 -> 10 Weisse Pixel
[...]
01111111111 -> 1 Weisser Pixel.

Man geht jetzt einfach durch seinen Baum (0 = links, 1 = rechts) bis man an die Stelle kommt, wo das Ende des Astes markiert ist (z.B. Lauflänge != 0), und man die Bit-Anzahl ablesen kann. Die Bäume müssen natürlich so aufgebaut sein, dass es keine Verwechslungen geben kann, und genau das ist der Trick beim Modified-Huffman.

0 -> irgendwas
01 -> was anderes

geht z.B. nicht, weil du ja hier nicht wüsstest, ist 0 schon Ende, oder geht's noch weiter. Darum besteht der Baum immer aus eindeutigen Bitfolgen. Die Längste Folge sind 11 Bits, wenn ich mich recht erinnere. Ja, und daduuch, das es zwei Bäume gibt, einen für Schwarz und einen für Weiss, wird der Effekt noch verdoppelt, weil Schwarze und Weisse Lauflängen in ihrer Häufigkeit doch arg unterschiedlich sind (bei Faxen zumindest).

Die wohl einfachste Methode, die aber bei reinen Text-Dateien dennoch gute Ergebnisse erzielt, weil dieselben Wörter in einem Text ja häufiger auftauchen: Einfach für jedes Wort eine Nummer vergeben. Am Anfang der komprimierten Datei steht dann einfach das Wort mit der zugeordneten Zahl, und danach folgen dann einfach die Zahlen. Beim Dekomprimieren wird dann einfach wieder jede Zahl durch das passende Wort ersetzt. Je nach Anzahl der unterschiedlichen Wörter kommt man dann mit ein paar Bits pro Wort aus.