Wiki source for EntropieKodierung


Show raw source

=====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}}
Valid XHTML :: Valid CSS: :: Powered by WikkaWiki