Die Codewörter haben nach der Entropiekodierung unterschiedliche Längen. Dabei werden Symbole mit hoher Wahrscheinlichkeit werden mit kurzen Bit-Sequenzen kodiert. Deshalb ist eine Synchronisation oder das Markieren der Schranken eines Codeworts notwendig.

Entropie: SkriptRoth2008, S. 16

• Einfügen von Trennsymbolen
• Nicht besonders Effizient, da die Kompressionsfaktor dadurch erheblich schlechter wird
• Codes mit Präfix
• HuffmannCodierung Huffmann-Kodierung
• Adaptive Huffmann-Kodierung
• Arithmetische Kodierung

Oft auftretende Folgen von Symbolen werden zu einem Symbol zusammengefasst mit dem Ziel der Verringerung der Intersymbolredundanz.

• Run Length Coding (RLE), Lauflängenkodierung, verwendet in Bildformaten pcx, bmp, jpeg und beim FAX (ITU-Empfehlung T.4)
• Patternsubstitution, Phrasenkodierung (Bsp. deutsche Sprache: ch, sch, tz, en)
• Lampel-Ziv-Verfahren und Erweiterungen
• LZ-77 (1977), png, gzip
• LZ-78 (Verbesserung 1978)
• LZSS (Lempel-Ziv-Storer-Szymanski, 1982), verwendet in Kompressionsprogrammen lha, zip
• LZW (Lampel-Ziv-Welch, 1984), verwendet in Kompressionsprogrammen zip, gzip, bzip und Bildformaten gif, tiff (SkriptRoth2008, S. 18 und SkriptCarl, S. 85)
• CTW, Context tree weighting by Willems, Shtarkov, and Tjalkens, 1995, The algorithm is is mixing the predictions of many underlying variable order Markov models.

Transformationen für eine bessere Kompression.

• Burrows-Wheeler transform, verwendet in bzip2

Vergleich

Dateiarchive (mehrere Dateien, Verzeichnisse)

arj
tar/gzip (.tar.gz)
rar
zip

Einzelne Dateien

gzip (.gz)
lha
bzip2

DEFLATE ist ein in RFC1951 definiertes Verfahren, was den Algorithmus LZ77 und die Hufmann-Kodierung kombiniert. Der Standard speilte eine besondere Rolle bevor das Patent auf den im GIF-Format verwendeten LZW-Algorithmus ausgelaufen ist.

Verwendung in gzip, png

---

Referenziert von • • • •