Entropiekodierung
1. Eigenschaften
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
2. Mögliche Ansetze zur Synchronisation
- Einfügen von Trennsymbolen
- Nicht besonders Effizient, da die Kompressionsfaktor dadurch erheblich schlechter wird
- Codes mit Präfix
3. Präcodierung
Oft auftretende Folgen von Symbolen werden zu einem Symbol zusammengefasst mit dem Ziel der Verringerung der Intersymbolredundanz.
- RunLengthEncoding Run Length Encoding (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.
J. Ziv and A. Lempel. A Universal Algorithm for Sequential Data Compression. IEEE Trans. on Information
Theory, vol. 23, 3 (1977), pp. 337-343
4. Transformationen
5. Dateiformate
Vergleich
Dateiarchive (mehrere Dateien, Verzeichnisse)
- LHAbasierend auf dem Lempel-Ziv-Storer-Szymanski-Algorithmus (LZSS) und eine Entropiekodierung nach Huffman, created in 1988 by Haruyasu Yoshizaki
- PKZIP
- ARJ (Archived by Robert Jung) 1991
- tar/gzip (.tar.gz)
- RAR
- ZIP
- JAR by Robert Jung
Einzelne Dateien
gzip (.gz)
lha
bzip2
6. Was ist DEFLATE?
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
7. Bibliotheken
- uzlib
- zlib
- SFL compresses it using a fast LZ/RLE algorithm
- heatshrink
Code Snippets
Referenziert von • • • •