Datenkompression
Als Datenkompression bezeichnet man Verfahren, zur zeitweiligen Verkleinerung der benötigten Speicherkapazität von Daten.
Zu einem solchen Verfahren gehört in der Regel nicht nur eine Methode zur Reduktion der benötigten Speicherkapazität (Kompression), sondern auch der Wiederherstellung der Daten in ursprünglicher Form (Dekompression).
Die Datenkompression wird teils durch günstigere Repräsentation, d.h. Vermeiden von redundanten und oft wiederholten Informationen, teils durch Weglassen von mehr oder weniger unwichtigen Informationen erreicht.
Man unterscheidet verlustfreie und verlustbehaftete Datenkompression, je nachdem, ob die Daten mit einem Dekompressionsverfahren wieder originalgetreu hergestellt werden können (verlustfrei) oder nicht (verlustbehaftet). Bei der verlustfreien Datenkompression werden also nur redundante Informationen verkürzt dargestellt, während bei der verlustbehafteten Datenkompression zusätzlich weniger wichtig erscheinende Informationen weggelassen werden.
Verlustfreihe Kompression wird insbesondere dort eingesetzt, wo verlustbehaftete Datenkompression die Daten vollständig unbrauchbar machen kann, wie zum Beispiel bei Texten, insbesondere Quelltexten von Computerprogrammen. Populäre Verfahren zur verlustfreien Datenkompression sind zum Beispiel das Lempel-Ziv-Welsh-Verfahren oder die Huffmann-Kodierung, die in vielen populären Computerprogrammen, insbesondere Kompressionstools wie WinZip unter Windows oder pkzip, gzip und bzip2 unter den verschiedenen Linux-Derivaten zur Anwendung kommmen.
Verlustbehaftete Kompression wird insbesondere dort eingesetzt, wo sehr große Datenmengen anfallen, aber auf viele Detailinformationen verzichtet werden kann. Bei Audiodateien kann man zum Beispiel nicht bzw. kaum hörbare Frequenzanteile ausfiltern. Bei Bild- und Videodateien kann man beispielsweise geringe Farbunterschiede in benachbarten Bildpunkten vernachlässigen. Es handelt sich also um Detailinformationen, die in der Regel nicht relevant sind und kaum vom Betrachter wahrgenommen werden, bzw. die für einen bestimmten Zweck irrelevant sind. Je nachdem, wieviel und welche Informationen weggelassen werden, kann die Qualität der Daten aber auch mehr oder weniger stark sinken. Oft muss hier nach Kosten (benötigte Speicher- oder Übertragungskapazität) und Qualität abgewogen werden. Bei der verlustbehafteten Datenkompression, kommt es also auch zu einer Datenreduktion. Populäre Verfahren zur verlustbehafteten Datenkompression sind zum Beispiel MP3 oder Ogg-Vorbis für Komprimierung von Audiodateien, JPEG zur Komprimierung von Bilddateien oder MPEG zur Komprimierung von Videodateien.
Die Datenkompression ist nicht nur auf die Informatik beschränkt, sie findet auch in der Natur (Biologie) statt: Bei Eukaryonten liegt die Erbinformation für zahlreiche Gene gestückelt vor; sie wird durch alternatives Splicing dekomprimiert. Dadurch werden bestimmte DNA-Abschnitte für die Codierung mehrerer unterschiedlicher Proteine verwendet.
Hintergrund
Datenkompression hat auch wesentliche Elemente von Kodierung, d.h. es beschäftigt sich mit Fragen, wie Information mit Hilfe von Symbolen (z.B. Ketten von 0 und 1) zweckmäßig aufgeschrieben (kodiert) und wieder zurückgelesen (dekodiert) werden kann. Dabei wird oft eine Darstellung in eine andere umgewandelt. Das Hauptziel hier jedoch ist eine kompakte, verkürzte Version herzustellen oder gar eine _maximal_ mögliche Verkürzung der Daten zu erreichen. Andere übliche Fragen bei der Kodierung, etwa: Fehlerrobustheit für Übertragungssicherheit, Verschlüsselung von Information, Verwendung bestimmter Symbolfolgen etc, können dann noch als weitere, zusätzliche Nebenaspekte eine Rolle spielen.
Zur Verkürzung eines Textes werden zwei wesentliche Ideen verwendet. (a) Zur Verkürzung werden einerseits bestimmte häufiger vorkommende Zeichen oder Gruppen von Zeichen im Ausgangstext durch kurze Zeichenfolgen und andererseits selten vorkommende Zeichen durch längere Zeichen im Kodiertext kodiert. (b) Ein anderer wesentlicher Aspekt ist die Betrachtung von möglicher Verschwendung bei der Repräsentation, d.h. es wird im Gegensatz zum Ausgangstext jede Kombination von Zeichen mit einer Bedeutung verbunden, was zumeist sonst nicht der Fall ist. (c) Bei verlustbehafteten Verfahren wird in der einen oder anderen Weise entschieden, dass Information im Ausgangstext überflüssig ist (etwa auf die Hörfähigkeit des menschlichen Ohres bezogen, bei MP3) und dass diese Information weggelassen (oder mit geringerer Detailliertheit aufgezeichnet) werden kann. Diese wird dann auch nicht in den Kodiertext übernommen.
Ein Verfahren, welches nur einzelne Symbolketten durch einzelne andere ersetzt, erreicht im Allgemeinen keine Kompression. Kompression benötigt mehr als Kodierung.
Beispiel
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. (Im Sinne von Kodierung ist -3 ein Code für BEITRAG)
Analyse von Kompressionsverfahren
Die Untersuchung von Kompressionsverfahren ist eine Aufgabe im Bereich Informatik. Sie bedient sich ausgefeilter Methoden der mathematischen Statistik, um gesicherte Aussagen über Güte und den Grad eines Verfahrens zu erreichen. Bei Verfahren, die kompakte, aber veränderte, ähnliche Versionen herstellen, muss genau festgestellt werden, welche Veränderungen möglich sind, ohne den Wesensgehalt oder die Gebrauchsfähigkeit der Daten einzuschränken. Die theoretische Grundlage bildet dabei 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. Diese Länge kann aus der Entropie berechnet werden. In neuerer Zeit gibt es umgekehrt auch Ansätze, den Informationsgehalt auf die 'Nichtmehrverkürzbarkeit' zurückzuführen (Chaitin).
Jedes Verfahren praktiziert in direkter oder indirekter Weise auch solch eine Form von wahrscheinlichkeitsgesteuerter Vorgehensweise. Einige Verfahren verwenden dazu explizit Statistik im Verfahren (Huffman). Andere verwenden radikal einfache Mechanismen der Wiedererkennung über Zwischenspeicher (Lempel-Ziv) um die gleiche Wirkung zu erzielen. Eine typische Rolle spielen auch die natürlichen Zahlen als natürliche Codes, indem sie als Index oder Adresse auf einen originalen Inhalt verweisen. Hier kommt zum Tragen, dass kleine Zahlen kürzer sind als große Zahlen.
Gemeinsam ist den Verfahren die interne Verwendung einer Datenbasis (Gedächtnis, Statistik, Modell von Zeichenabhängigkeiten), die während der Analyse eines Textes geführt wird. Diese kann bei statischen Verfahren als Ganzes vor der eigentlichen Herstellung des Kodiertextes geschehen oder bei dynamischen Verfahren on-the-fly, kontinuierlich während des Aufschreibens bzw. Übertragens eines komprimierten Textes. Aus praktischen Gründen haben sich Verfahren durchgesetzt, die kontinuierlich verkürzen und Zeichen für Zeichen kodieren und umgekehrt (beim Entpacken) kontinuierlich auslesen und die ursprüngliche (lange) Version in gleicher Reihenfolge wiederherstellen. Eine wichtiges Konzept ist die Idee einer mitgeführten Modellierung bzw. interner Statistik, die beim Kodieren Zeichen für Zeichen intern statistisch erfasst. Diese Statistik wird beim Auspacken (dann mit Hilfe der entpackten Zeichen) noch einmal erstellt, um das gleiche Wissen um die Häufigkeit wie beim Einpacken verwenden zu können. Auf diese Weise muss keine besondere Statistik und keine Art von Kodebuch übertragen werden.
Wichtige Datenkompressions-Verfahren
Huffman-Code. (siehe dort)
Lempel/Ziv-I. Es wird ein Zwischenspeicher mitgeführt, der einen Teil des bereits gelesen Textes speichert. Zu kodierende Zeichen oder Textstücke werden als Referenzen (einer Adresse vergleichbar) auf diesen Zwischenspeicher kodiert. Der Zwischenspeicher dient hier als eine Art lokale Version eines Kodebuches. Dies hat den Vorteil, dass dieses nicht getrennt erstellt und/oder übertragen werden muss und dass der Packer sich etwaigen Veränderungen im Text automatisch anpassen kann (lokal adaptiv).
Lempel/Ziv-II. Die zweite Lempel-Ziv-Konzeption ist bis heute eine der bedeutsamsten Komprimiermethoden und in vielen Varianten in fast allen typischen Anwendungen enthalten. Sie liest Zeichen für Zeichen ein und vergleicht diese Kette mit bereits vorhanden Einträgen. Schließlich entsteht ein neuer Eintrag in dem internen Verzeichnis. Dieser besteht aus einem bereits vorhandenen Eintrag und dem neu eingelesenen Zeichen. Dieses enthält mit der Zeit immer längere tatsächlich vorkommende Textfragmente. Tatsächlich übertragen werden jedoch nur jeweils Adressen (Indizes) dieser Fragmente und jeweils ein neuer Buchstabe. Das interne Wörterbuch der bekannten Textstücke ist somit zugleich auch Kodebuch. Es gibt dann unterschiedliche Varianten, die sich mit der Frage des Managements dieses internen Gedächtnisses befassen. Die Umsetzung liefert eine auch unter praktischen Gesichtspunkten optimale Methode. Es ist bemerkenswert, welche Grade von Kompression und Allgemeinverwendbarkeit mit diesem Verfahren erreicht werden, das im Kern nur auf Wiedererkennung, Kombination und Referenz aufbaut.
Arithmetisches Kodieren. (siehe dort)
MP3 Kodierung. Diesem Verfahren für die Kodierung von akustischen Medieninhalten (Musik, Filmsound, etc.) liegt die genaue Untersuchung der Hörfähigkeit des menschlichen Gehörs zugrunde. Ergebnis ist die Möglichkeit bestimmte Folgen von Höreindrücken verändern zu können, ohne dass es zu einer subjektiv feststellbaren Veränderung des Gehörten kommt. Dies wird bei der eigentlichen Kodierung als Quelle für Kompaktifizierung genutzt.
Wavelet-Kompression. (siehe dort)
Zeittafel
- 1949 Informationstheorie, Claude Shannon
- 1949 Shannon Fano coding
- 1952 Huffmann, static
- 1964 Kolmogorov complexity concept
- 1975 Integer coding scheme, Elias
- 1976 Arithmetic coding (Implementierung)
- 1977 Lempel-Ziv-Verfahren
- 1984 LZW (Lempel-Ziv-Welch)
- 1985 Apostolico, Fraenkel, Fibonacci coding
- 1986 Move-To-Front, (Bentley et.al., Ryabko)
- 1986 ARC-Programm
- 1987 PKARC (=LZW)
Stichworte
Archiv - Archivierungsformat - Arc - ARJ - CAB - Codec - Entpacken - Exe-Archive - JAR - Kompressionsstufen - Komprimieren - LHARC - LZH - MP3 - Multivolumen-Archiv - Packen - Packer-Formate - RAR - selbstextrahierend - Stuffit - tar - Unzip - virtuelles Entpacken - WinZip - WMA - Zip
siehe auch: Kodierung, Informationstheorie, Claude Shannon, Packer, Datenkompressionsprogramme, Informatik
Weblinks
- 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;