Datenkompression ist ein technisches Verfahren zur systematischen Verminderung der Menge an Daten, die notwendig ist, um einen gegebenen Inhalt (einen Text, eine Bilddatei, etc.) in einer computerlesbaren Form wiederzugeben. Dazu wird ein originaler Quellentext, ein Quellbild oder eine andere Computerdatei mit Hilfe eines Kompressionsverfahrens untersucht und in eine komprimierte, d.h. verkürzte Form umgeschrieben (gepackt). Mit Hilfe eines zu dem gewählten Verfahren passenden Leseverfahrens wird die verkürzte Fassung des Textes oder der Daten wieder in die ursprüngliche, längere zurückverwandelt (entpackt). Dabei wird unterschieden, ob die ursprüngliche Information letztlich wortgetreu (verlustfrei) oder auch mit gewissen Änderungen (verlustbehaftet) rekonstruiert wird (Datenreduktion). Texte sollen meist wortgetreu, Bilder häufig nur detail- und farbgetreu verarbeitet werden.
Kompression:
- LANGE-ORIGINAL-QUELLDATEI (->Komprimierprogramm->) KOMPR.DATEI
Dekompression:
- KOMPR.DATEI (->Entkomprimierprogramm->) LANGE-ORIGINAL-QUELLDATEI
Populäre Anwendungen
,die solche Komprimierungsverfahren beinhalten, sind etwa im Personal-Computerbereich ZIP-Programme, Huffman-Kodierung für Faxübermittlung, JPG-Bildformate mit Komprimierung von Bild- und MP3 für die Komprimierung von Klangdaten. Diese erstellen die verkürzten, gepackten Dateiversionen in einem entsprechenden Format und entpacken diese Archive genannten Dateien oder Dateisammlungen wieder hin zu den ursprünglichen Originalen.
- COMPUTERDATEI(EN) (<- ZIP-Programm ->) ZIP-Datei
Datenkompressionsprogramme
Siehe dort
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 Detailiertheit 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 würde 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, das 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 Information theory, Shannon
- 1949 Shannon Fano coding
- 1952 Huffmann, static
- 1964 Kolmogorov complexity concept
- 1975 Integer coding scheme, Elias
- 1976 Arithmetic coding (implementation)
- 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)
Literatur und Links:
- 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;
siehe auch: Kodierung, Informationstheorie, Shannon, Packer
Zurück zu Informatik