Datenkompression
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
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ässig aufgeschrieben (kodiert) und wieder zurückgelesen (dekodiert) werden kann. Dabei wird oft die 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)
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 (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 kann. 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 orginalen Inhalt verweisen. Hier kommt zum Tragen, das kleine Zahlen kürzer sind als grosse 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 - Verfahrensind:
Huffmann. Hier wird eine Statistik zumeist für den Text als Ganzes erstellt. (Es gibt jedoch auch dynamische Varianten.) Entsprechend der Häufigkeit werden für Gruppen von Ausgangssymbolen (z.B. Wörtern) bestimmte Folgen von 0 und 1 in einem Kodebuch definiert. Die Festlegung im Kodebuch erfolgt geschickterweise so, dass Untergruppen von Code, die sich durch eine folgende 0 und 1 unterscheiden, einer etwa gleichgrosse Menge an Ausgangszeichen entspricht. Im Kodiertext wird jeweils nur der Code aufgeschrieben. Beim Entpacken wird aufgrund des Codes im Kodebuch das dazu passende Originalwort nachgesehen, ausgelesen und damit der Orginaltext wieder hergestellt.
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. Schliesslich 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, welches im Kern nur auf Wiedererkennung, Kombination und Referenz aufbaut.
Arithmetisches Kodieren. Bei diesem Verfahren wird eine kontinuierliche Berechnung durchgeführt, die gewissermassen in einer einzigen sehr langen Zahl (= komprimierte Datei) Information speichert. Dabei bestimmen die Häufigkeiten im Ausgangstext Anteile beim jeweiligen Rechenschritt. Die verwendeten Rechenoperationen werden beim Auslesen durch die gelieferte 'lange Zahl' ersichtlich und lassen den Rückschluss auf das jeweils kodierte, gepackte Zeichen zu. Die Kernidee ist, dass sich häufigere Symbole in einer geringeren Veränderung der globalen Zahl (eigentlich ein Teilungsinterval) wiederspiegeln. Arithmetisches Kodieren besticht dadurch, dass es wesentlich die Bitgrenzen aufhebt und eigentlich einen rein mathematischen Formalismus verwendet. Dieser macht eigentlich notwendig, riesige Zahlen zu berechnen. Durch geschickte Wahl von Randparametern kann aber dennoch eine praktikable Implementation erreicht werden.
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 Kodierung. (Sorry, darüber weiss ich zu wenig. Schreib Du mal.)
Zeittafel
- 1949, Information theory, Shannon, 1949
- 1949, Shannon Fano coding, 1949
- 1952, Huffmann, static, 1952
- 1964, Kolmogorov complexity concept (1964)
- 1975, Integer coding scheme, Elias,1975
- 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:
- 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