Datenkompression
aus Wikipedia, der freien Enzyklopädie
Als Datenkompression oder Datenkomprimierung bezeichnet man die Anwendung von Verfahren zur Reduktion des Speicherbedarfs von Daten bzw. zur Vermeidung von Datenaufkommen, bspw. während der Übertragung von Daten.
Die Datenmenge wird reduziert, indem eine günstigere Repräsentation bestimmt wird, mit der sich die gleichen Daten in kürzerer Form darstellen lassen. Diesen Vorgang übernimmt ein Kodierer, und man bezeichnet den Vorgang als Kompression bzw. Kodierung. Man spricht von einer verlustfreien Kompression (oder verlustfreien Kodierung), wenn die kodierten Daten nach Anwendung der entsprechenden Dekodiervorschrift exakt denen des Originals entsprechen. Die Anwendung der Dekodiervorschrift bezeichnet man als Dekompression oder Dekomprimierung. Wenn man von einer verlustbehafteten Kompression (oder verlustbehafteten Kodierung) spricht, so meint man damit, dass sich die Daten nicht in jedem Fall fehlerfrei rekonstruieren lassen.
In der Nachrichtentechnik wird das Kodieren von Nachrichten aus einer Quelle durch einen Sender als Quellenkodierung bezeichnet.
Inhaltsverzeichnis |
[Bearbeiten] Informatik
[Bearbeiten] Redundanz- und Irrelevanzreduktion
Die Datenkompression wird teils durch „günstigere Repräsentation“, das heißt Vermeiden von Redundanz, teils durch Weglassen von Information erreicht. Wenn die Daten mit einem Dekompressionsverfahren wieder originalgetreu hergestellt werden, arbeitet es verlustfrei. Man spricht dann von Redundanzreduktion. Andernfalls ist es verlustbehaftet. In diesem Fall spricht man von Irrelevanzreduktion. Beide Verfahren können kombiniert werden.
Bei der verlustfreien Kompression wird die originäre Information I in eine komprimierte Information I' überführt. Diese Abbildung von I nach I' ist eineindeutig, also eindeutig in beide Richtungen. Man spricht in diesem Zusammenhang auch von einer bijektiven Abbildung.
Die verlustbehaftete Kompression reduziert die Information. Es wird ein Modell zugrunde gelegt, das entscheidet, welcher Anteil der Information für den Empfänger entbehrlich ist. Da eine solche Abbildung nicht mehr eineindeutig ist, kann die ursprüngliche Information mittels Dekompression nicht wiederhergestellt werden.
[Bearbeiten] Verfahren
Die theoretische Grundlage bildet die von Informationswissenschaftlern (Claude Shannon; Andrei Kolmogorow) 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.
Durch geeignete Kompressionsverfahren erreicht man gute Annäherungen an die Kanalkapazität.
In neuerer Zeit gibt es umgekehrt auch Ansätze, den Informationsgehalt auf die „Nichtmehrverkürzbarkeit“ zurückzuführen (Chaitin).
[Bearbeiten] Einsatzgebiete
[Bearbeiten] 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 Wörter 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, Tokens, ersetzt.
Ausgangstext: Print "Hallo"; Print "Hier" Kodiertext: 3F "Hallo"; 3F "Hier"
Verfahren der so genannten Entropiekodierung:
- Huffman-Code (in modifizierter Form zum Beispiel für die Fax-Übertragung)
- Arithmetische Kodierung
[Bearbeiten] Präkodierung
Präkodierung umfasst alle Techniken der Datenkompression, welche in Daten vorhandene statistische Abhängigkeiten ausnutzen. Diese Techniken bilden Symbole aus einem Alphabet auf Symbole eines anderen Alphabets ab bzw. unterstützen diesen Prozess. Die Anzahl der Symbole kann sich dabei verändern (im Gegensatz z. B. zu Verfahren der Dekorrelation, welche ebenfalls Korrelationen im Signal auflösen). Oft werden die Ergebnisse nochmals entropiekodiert.
Sehr verschiedene Algorithmen gehören zur Gruppe der Präkodierung: Lauflängenkodierung, Phrasenkodierung (besser bekannt als wörterbuchbasierte Kodierung wie z. B. LZ78 und LZW), Blocksortierung (auch bekannt als Burrows-Wheeler-Transformation), Quadtree-Kodierung und andere.
Heutzutage stehen viele Datenkompressionsprogramme für den Rechnereinsatz zur Verfügung.
[Bearbeiten] 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 Signalverlä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 (siehe Psychoakustik). Die Verfahren Ogg Vorbis oder MP3 reduzieren das Datenvolumen um Faktoren bis zu 50. Bei einem Faktor von 10 sind für den Menschen kaum noch Qualitätsunterschiede zum Ausgangsformat, wie zum Beispiel PCM, 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. Verzichtet man auf Stereo und nimmt eine weitere Qualitätsverschlechterung in Kauf, ist zum Beispiel ab 24 kbit/s die qualitativ annehmbare Übertragung per Webradio 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 verlustfreier Kompression, so lassen sich fotografisch (oder vergleichbar) erstellte Bilder wegen ihres typischen Rauschanteils nur ungenügend komprimieren. Daher kommen verlustfreie digitale Kompressionsformate, wie etwa das TIFF-Format, fast nur in der professionellen Fotografie und Bild-Gestaltung zur Anwendung. Das GIF-Format arbeitet auch verlustfrei, begrenzt aber den Farbraum auf 256 Farben, so dass es eher für Zeichnungen oder für die Endergebnisse eines Verarbeitungsprozesses geeignet ist. Wegen seiner großen Reduktion findet es auf vielen Webseiten Verwendung, weil es hier oft auf schnelle Ladezeiten ankommt und das GIF-Format auch Animationen erlaubt.
Filme werden mit etwa 25 Bildern pro Sekunde aufgenommen. Da sich die Bilder nur beim Szenenwechsel deutlich ändern, beschränkt sich die Speicherung vornehmlich auf die Speicherung der Änderungen zwischen den Bildern. Es werden Formate wie MJPEG, 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-Kodierung, der Cinepak-Codec, der Sorenson-Codec oder die in letzter Zeit sehr weit verbreiteten Codecs XviD und DivX.
[Bearbeiten] Kompressionsartefakte
Als Kompressionsartefakte bezeichnet man Signalstörungen, die durch die digitale, verlustbehaftete Datenreduktion verursacht werden.
Beispiele:
- schnarrende Stimme beim Mobilfunkempfang
- bei Bildkompression wie JPEG:
- unscharfe Kanten (JPEG, JPEG2000)
- Unschärfe (JPEG, JPEG2000)
- Kästchenmusterbildung, auch Verblockung genannt (JPEG), siehe Bild rechts
- Ringing: eine kleine Fläche um einen Gegenstand mit hohem Kontrast, welcher deutlich aus der Umgebung heraussticht (JPEG, JPEG2000)
- Farbverfälschungen (JPEG, JPEG2000)
- Schwarz/Weiß-Konturen
- Farbkonturen
- bei Audiodatenkompression, wie MP3:
- Pre-echo: vor einem lauten plötzlichen Geräusch (zum Beispiel Schlagzeug) sind klirrend-metallische Artefakte hörbar
- Post-echo: nach einem plötzlichen Geräusch sind deutliche Artefakte zu hören
- verwaschener Klang, insbesondere in Höhen und Tiefen, sowie bei bestimmten Instrumenten (Hi-hat)
- unpassende Lautstärkeänderungen
- Veränderung der Stereofonie, Verringerung des räumlichen Eindrucks
- bei Videokompression, wie MPEG:
- Farbverfälschungen (z. B. Bleeding)
- Wabernder Hintergrund
- Ringing
- Unschärfe, insbesondere bei Kanten
- Kästchenmusterbildung, auch Verblockung genannt
- Schwarz/Weiß-Konturen
- Farbkonturen
[Bearbeiten] Speicherung von ausführbaren Dateien
siehe Kompression ausführbarer Programmdateien. Anwendungsbeispiele sind UPX und Upack.
[Bearbeiten] Zeittafel der Kompressions-Algorithmen
- 1949 Informationstheorie, Claude Shannon
- 1949 Shannon-Fano-Entropiekodierung
- 1952 Huffman, static
- 1964 Kolmogorov complexity concept
- 1975 Integer coding scheme, Elias
- 1977 Lempel-Ziv-Verfahren LZ77
- 1978 Lempel-Ziv-Verfahren LZ78
- 1979 Bereichskodierung (eine Implementierung arithmetischer Kodierung)
- 1982 Lempel-Ziv-Storer-Szymanski (LZSS)
- 1984 Lempel-Ziv-Welch-Algorithmus (LZW)
- 1985 Apostolico, Fraenkel, Fibonacci coding
- 1986 Move to front, (Bentley et. al., Ryabko)
- 1994 Burrows-Wheeler-Transformation
- 1997 Sequitur
- 1998 Lempel-Ziv-Markow-Algorithmus (LZMA)
[Bearbeiten] Bekannte Methoden
[Bearbeiten] Bilder
- GIF (verlustfrei bis zu 256 Farben)
- JPEG (verlustbehaftet)
- PGF (verlustfrei oder -behaftet)
- PNG (verlustfrei)
- TIFF (verlustfrei oder -behaftet)
- DjVu (verlustbehaftet, ebenenorientiert: Text/Bild)
[Bearbeiten] Audio
- Aiff (verlustfrei)
- Apple Lossless (verlustfrei)
- ATRAC (verlustbehaftet oder verlustfrei)
- Dolby Digital (verlustbehaftet)
- DTS (verlustbehaftet oder verlustfrei)
- FLAC (verlustfrei)
- G.729 (verlustbehaftet)
- LA (verlustfrei)
- MPEG
- Musepack (verlustbehaftet)
- (Ogg-)Vorbis (verlustbehaftet)
- WavPack (verlustbehaftet oder verlustfrei)
- WMA (verlustbehaftet oder verlustfrei)
[Bearbeiten] Video
(alle verlustbehaftet)
[Bearbeiten] Datenübertragung
- MNP-1 bis MNP-10 (Microcom Networking Protocol)
-
- Fehlerkorrektur- und Datenkompressionsprotokolle der Firma Microcom Inc. für Modems, ein jahrelanger Standard. Wurde verbessert durch:
- V.42bis Datenkompressionsprotokoll der ITU-T
[Bearbeiten] Komprimierung / Archivierung
[Bearbeiten] Automatische Komprimierung
Manche Dateisysteme erlauben, Dateien beim Speichern automatisch zu komprimieren und beim Lesen automatisch zu entpacken. Je nach Art der gespeicherteten Dateien kann dadurch Speicherplatz gespart werden. Typische Kandidaten mit Sparpotential sind (längere) Textdateien. Schlechte Kandidaten sind Mails oder News, da diese meist kurz sind und unkomprimiert in einen Block passen (die meisten Dateisysteme speichern Dateien blockweise ab; siehe dazu Cluster (Festplatte)).
Es gibt Dateisysteme, die je nach Kompressionsgewinn die Kompression eines Blocks dynamisch an- oder ausschalten. Von dieser Technik wird auch bei Internetprotokollen wie VPN Gebrauch gemacht.
[Bearbeiten] 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 kodiert. 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.
[Bearbeiten] Siehe auch
- Gibbssches Phänomen
- Bildkompression
- Audiodatenkompression
- Kompression ausführbarer Programmdateien
- Codec
- Kanalkodierung
- Informationstheorie
- Liste der Datenkompressionsprogramme
- Liste der Dateinamenserweiterungen
[Bearbeiten] Weblinks
 |
Wikibooks: Buch zu Datenkompression – Lern- und Lehrmaterialien |
- Vergleich der Kompressionsleistung von über 250 Packprogrammen (englisch)
- LA - Verlustfreies Audioformat mit den angeblich höchsten Kompressionsraten (englisch)
- Data Compression - Systematisation by T.Strutz (englisch)
- Data compression FAQ (englisch)
- Lelewer, Debra, A.; Hirschberg, Daniel, S.: „Data Compression“; ACM Computing Surveys, 19,3 (1987), 261-297, Übersichtsartikel (englisch)
- Glossar zur Datenkompression (englisch)
- Liste mit Kompressionsvergleichen (englisch)
