=====Entropiekodierung===== ==a==Eigenschaften==a== 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 ==a==Mögliche Ansetze zur Synchronisation==a== ~-Einfügen von Trennsymbolen ~~-Nicht besonders Effizient, da die Kompressionsfaktor dadurch erheblich schlechter wird ~-Codes mit Präfix ~~-[[HuffmannCodierung Huffmann-Kodierung]] ~~-[[http://en.wikipedia.org/wiki/Adaptive_Huffman_coding Adaptive Huffmann-Kodierung]] ~~-[[http://en.wikipedia.org/wiki/Arithmetic_coding Arithmetische Kodierung]] ==a==Präcodierung==a== 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, [[http://en.wikipedia.org/wiki/Context_tree_weighting 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 ==a==Transformationen==a== Transformationen für eine bessere Kompression. ~-[[http://en.wikipedia.org/wiki/Burrows-Wheeler_transform Burrows-Wheeler transform]], verwendet in bzip2 ==a==Dateiformate==a== [[http://en.wikipedia.org/wiki/Comparison_of_file_archivers Vergleich]] ===Dateiarchive (mehrere Dateien, Verzeichnisse)=== - [[https://en.wikipedia.org/wiki/LHA_(file_format) LHA]]basierend 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 - [[http://en.wikipedia.org/wiki/Gzip tar/gzip]] (.tar.gz) - [[http://en.wikipedia.org/wiki/RAR_(file_format) RAR]] - [[http://en.wikipedia.org/wiki/ZIP_file_format ZIP]] - JAR by Robert Jung ===Einzelne Dateien=== [[http://en.wikipedia.org/wiki/Gzip gzip]] (.gz) [[http://en.wikipedia.org/wiki/LHA_(file_format) lha]] [[http://en.wikipedia.org/wiki/Bzip2 bzip2]] ==a==Was ist DEFLATE?==a== [[DEFLATE]] ist ein in [[http://tools.ietf.org/html/rfc1951 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 ==a==Bibliotheken==a== - [[uzlib]] - [[zlib]] - [[SFL]] compresses it using a fast LZ/RLE algorithm - [[heatshrink]] Code Snippets - [[LZW]] - [[RunLengthEncoding Run Length Encoding (RLE)]] - [[HuffmannCodierung Huffmann-Kodierung]] ---- Referenziert von {{backlinks}}