Plotservice - wir plotten für Sie schnell, günstig, einfach sicher digital - ob CAD-Plan oder Poster testen Sie unseren Plotservice kostenlos.

Als Datenkompression bezeichnet man Verfahren zur Reduktion des Speicherbedarfs von Daten durch Umkodieren. Zu einem solchen Verfahren gehört eine Methode zur Reduktion der benötigten Speicherkapazität (Kompression) und der Wiederherstellung der Daten in ursprünglicher Form (Dekompression).

Inhaltsverzeichnis

1 Informatik

1.1 Redundanz- und Irrelevanzreduktion

1.2 Verfahren

1.3 Einsatzgebiete

1.3.1 Speicherung von Text

1.3.2 Speicherung von Bildern und Ton

1.3.3 Kompressionsartefakte

1.4 Zeittafel der arithmetischen Kompressions-Algorithmen

1.5 Siehe auch

1.6 Weblinks

2 Biologie

Informatik

Redundanz- und Irrelevanzreduktion

Die Datenkompression wird teils durch günstigere Repräsentation, d.h. Vermeiden von Redundanz, teils durch Weglassen von Information erreicht. Wenn die Daten mit einem Dekompressionsverfahren wieder originalgetreu hergestellt werden können, arbeitet es verlustfrei. Man spricht dann von Redundanzreduktion. Andernfalls ist es verlustbehaftet. In diesem Fall spricht man von Irrelevanzreduktion.

Bei der verlustfreien Kompression wird die originäre Information I in eine komprimierte Information I' überführt. Diese Abbildung von I nach I' ist eindeutig, und umkehrbar.

Die verlustbehaftete Komprimierung reduziert die Information. Es wird ein Modell zu Grunde gelegt, das entscheidet, welcher Anteil der Information für den Empfänger entbehrlich ist.

Verfahren

Die theoretische Grundlage bildet die von Informationswissenschaftlern (Claude Shannon; Kolmogoroff) erarbeitete Theorie der Information und Kommunikation (Informationstheorie). Diese beschreibt den Zusammenhang zwischen Informationsgehalt einer Zeichenkette auf der Basis von Zeichen durch den Begriff der Entropie der Zeichenkette, die im Allgemeinen auf eine bestimmte, minimale Länge gebracht werden kann. In neuerer Zeit gibt es umgekehrt auch Ansätze, den Informationsgehalt auf die 'Nichtmehrverkürzbarkeit' zurückzuführen (Chaitin).

Einsatzgebiete

Speicherung von Text

Texte, sofern sie aus Buchstaben bestehen und nicht aus eingescannten Bildern, belegen wenig Speicherplatz. Eine Textdatei ohne Bilder ist selten größer als 10 MByte, die eine verlustfreie Kompression auf 1/5 bis 1/10 der Ursprungsgröße reduziert.

Beispiele:

Ausgangstext: AUCH EIN KLEINER BEITRAG IST EIN BEITRAG

Kodiertext: AUCH EIN KLEINER BEITRAG IST -4 -3

Hier wurde erkannt, dass die Worte EIN und BEITRAG zweimal auftauchen, und dadurch angegeben, dass diese mit den gerade zurückliegenden übereinstimmen. Bei genauerer Betrachtung könnte dann auch das EIN in KLEINER entsprechend kodiert werden.

Verwandt ist die tokenbasierte Kompression. Häufig wiederkehrende Schlüsselwörter werden durch Abkürzungen, den Tokens, ersetzt.

Ausgangstext: Print "Hallo"; Print "Hier"

Kodiertext: 3F "Hallo"; 3F "Hier"

Weitere Verfahren, die auf der sog. Entropiekodierung basieren:

Huffman-Code (in modifizierter Form z.B. für die Fax-Übertragung)

Arithmetische Kodierung

LZW (Lempel-Ziv-Welch), als Weiterentwicklung von LZ78 (Lempel-Ziv, 1978) und LZ77

RLE Lauflängenkodierung

LZMA, als Weiterentwicklung von LZ77

Heutzutage stehen viele Datenkompressionsprogramme für den Rechnereinsatz zur Verfügung.

Speicherung von Bildern und Ton

Ton, Bild und Film sind Einsatzgebiete verlustbehafteter Kompression. Anders wären die oftmals enormen Datenmengen nicht zu handhaben. Bereits die Aufnahmegeräte begrenzen das Datenvolumen. Die Reduktion der gespeicherten Daten orientiert sich an den physiologischen Wahrnehmungseigenschaften des Menschen. Die Kompression durch Algorithmen bedient sich dabei typischerweise der Wandlung von Singalverläufen von Abtastsignalen in eine Frequenzdarstellung.

In der akustischen Wahrnehmung des Menschen werden Frequenzen oberhalb 20-25 kHz meist nicht mehr wahrgenommen und können bereits im Aufnahmesystem beschnitten werden, ebenso werden leise Nebentöne nur schwer wahrgenommen, so dass sie vom Kompressions-System entfernt werden können. Die Verfahren Ogg Vorbis oder MP3 reduzieren das Datenvolumen um Faktoren bis zu 50. Bei einem Faktor von 10 sind durch den Menschen kaum noch Qualitätsunterschiede zum Ausgansformat wie z.B. WAV festzustellen. Eine CD von einer Stunde Laufzeit enthält etwa 600 MByte Daten für HiFi-Stereo Ton. In einem datenreduzierten Format benötigen diese Daten aber nur wenig mehr als 60 MByte. Mit anderen Worten, eine im MP3-Format bespielte CD kann bis zu 10 Stunden hochqualitative Musik speichern und das bei einer Datenrate von nur etwa 1 MByte/min was etwas mehr als 128 kbit/s entspricht. Bei Verzicht auf Stereo sowie weiterer Qulitätsreduzierung ist bei zum Beispiel 24 kbit/s schon Musikgenuss per Web-Radio möglich oder Internet-Telefonie realisierbar.

In der optischen Wahrnehmung des Menschen werden Farben weniger stark aufgelöst als Helligkeitsänderungen, daraus leitet sich die schon beim analogen Farbfernsehen bekannte YUV-422 Reduzierung ab. Kanten sind dagegen bedeutsamer und es existiert eine biologische Kontrastanhebung (Machsche Streifen). Mit moderater Tiefpassfilterung zur Farbreduktion, zum Beispiel durch den auf DCT-Transformation basierenden JPEG-Algorithmus oder den neueren auf Wavelet-Transformation basierenden JPEG2000-Algorithmus, verringert sich das Datenvolumen schnell um mehr als 90%. Besteht man auf verlustfreie Kompression so lassen sich fotografisch (oder vergleichbar) erstellte Bilder wegen ihres typischen Rauschanteils nur ungenügend komprimieren. Aus diesem Grund finden verlustlose digitale Kompressionsformate, wie etwas das TIFF-Format, fast nur in der professionellen Fotografie und Bild-Gestaltung ihre Anwendung. Das GIF-Format arbeitet auch verlustlos, reduziert aber den Farbraum auf 256 Farben, so dass es eher für Zeichnungen eignet oder für die Endergebnisse eines Verabeitungsprozesses. Wegen seiner grossen Reduktion findet es auf vielen Webseiten Verwendung, da es hier oftmals auf schnelle Ladezeiten ankommt und weil das GIF-Format auch Animationen erlaubt.

Filme werden mit ca. 25 Bildern pro Sekunde aufgenommen. Da sich die Bilder nur bei Szenenwechsel deutlich ändern, beschränkt sich die Speicherung vornehmlich auf die Speicherung der Änderungen zwischen den Bildern. Es werden Fromate wie MJPG, MPEG sowie diverse andere Formate verwendet. Im Computersektor haben sich die Containerformate AVI (Microsoft) und MOV (Apple) etabliert, wobei der verwendete Codec nahezu frei wählbar ist, zum Beispiel von Intel die Indeo-Codierung, der Cinepack-Codec oder der Soerensen-Codec.

Kompressionsartefakte

Als Kompressionsartefakte bezeichnen wir Qualitätseinbußen, die insbesondere durch die digitale Datenreduktion verursacht wird. Beispiele sind die schnarrende Stimme eines Handys bei schlechtem Empfang oder die gestörten Kanten bei hochkomprimierten Bildern im JPEG oder JPEG2000 Format.

Zeittafel der arithmetischen Kompressions-Algorithmen

1949 Informationstheorie, Claude Shannon

1949 Shannon-Fano-Entropiekodierung

1952 Huffman, static

1964 Kolmogorov complexity concept

1975 Integer coding scheme, Elias

1976 Arithmetic coding (Implementierung)

1977 Lempel-Ziv-Verfahren LZ77

1978 Lempel-Ziv-Verfahren LZ78

1984 Lempel-Ziv-Welch

1985 Apostolico, Fraenkel, Fibonacci coding

1986 Move-To-Front, (Bentley et.al., Ryabko)

1986 ARC-Programm

1987 PKARC (=LZW)

1999 LZMA wird mit dem Frontends 7-zip veröffentlicht

Siehe auch

Bildkompression - Codec - Kanalcodierung - Informationstheorie - Informatik

Weblinks

Data Compression - Systematisation by T.Strutz

Projektarbeit Datenkompression von Martin Fiedler

Data compression FAQ

Lelewer, Debra, A.; Hirschberg, Daniel, S.: "Data Compression"; (ausgezeichneter Übersichtsartikel); ACM Computing Surveys, 19,3 (1987), 261-297; oder direkt von der Homepage von Daniel Hirschberg;

LZ77, LZ78, Lempel-Ziv Welch: http://wombat.doc.ic.ac.uk/foldoc/foldoc.cgi?Lempel-Ziv+compression

LZMA ist erstmals in der freien Software 7-zip umgesetzt worden: http://www.7-zip.org

Biologie

Auch in der Biologie gibt es Kompressionsalgorithmen. So wird bei Eukaryonten die Information für Proteine nicht immer in einer zusammenhängenden DNA-Sequenz codiert. Durch ein System von Introns und Exons und die Verarbeitung der mRNA durch alternatives Splicing kann eine DNA-Sequenz die Information für mehrere unterschiedliche Eiweiße tragen. Der jeweilige Kompressionsalgorithmus wird dabei durch den Spleißvorgang und seine Regulation definiert.