Dateiformate

Beim Huffmann-Verfahren wird jeder der 256 Tonwertstufen eine Binärzahl zugeordnet. Tonwerte die häufiger vorkommen, erhalten eine kleinere Zahl und solche die selten vorkommen eine grosse.

Der von David Huffman beschriebene Algorithmus ordnet allen Zeichen, die in den betrachteten Daten auftreten können, einen Endknoten in einem binären Baum zu. Als Attribut erhalten diese Knoten die Auftrittshäufigkeiten der ensprechenden Zeichen. (a)

Die Baumstruktur entsteht durch das schrittweise Zusammenfassen dieser Knoten. Dazu werden die beiden Knoten mit der geringsten Auftrittshäufigkeit einem neuen Knoten untergeordnet, der die Summe der beiden Auftrittshäufigkeiten zugewiesen bekommt. (b)

Das Prozedere wird solange durchlaufen, bis alle Knoten in einer Wurzel zusammengeführt sind. (c–e)

Zur En- bzw. Dekodierung werden den Kanten des Huffman-Baums die binären Werte 0 bzw. 1 zugeordnet. Der «Weg» von der Wurzel zu dem entsprechenden Endknoten ergibt den Huffman-Kode des Zeichens, dem der Endknoten zugeordnet ist.

Run-Length-Encoding

Bei der Lauflängenkodierung wird ausgenutzt, das einer Datei oft mehrmals hintereinander das gleiche Zeichen erscheint. Eine solche Zeichenfolge wird dann durch das Zeichen selbst und der Anzahl folgender, gleicher Zeichen ersetzt.

AAAAAABBBB wird zu 6×A 4×B

Die Lauflängenkodierung eignet sich damit zum Beispiel besonders gut für Strichbilder.

Lempel-Ziv-Welch-Algorithmus

Bei der LZW-Komprimierung wird ein Wörterbuch mit den häufigsten Zeichenketten angelegt. Statt die Zeichenkette jedes Mal neu zu speichern muss dann nur noch ein Verweis auf den entsprechenden Wörterbucheintrag gesetzt werden. Die Komprimierung ist so angelegt, dass das Wörterbuch nicht speziell abgelegt werden muss. Der Decoder kann es aus der kodierten Datei rekonstruieren.

Wird bei GIF, ZIP und JPEG verwendet.