Wikipedia · einfach zusammengefasst · Stand
Datenkompression
Datenkomprimierung [1] genannt – ist ein Vorgang, bei dem die Menge digitaler Daten reduziert wird. Dadurch sinkt der Speicherbedarf,
Inhalt5 Abschnitte
Grundidee und Zweck
Datenkompression, auch Datenkomprimierung, ist ein Vorgang, bei dem die Menge digitaler Daten reduziert wird. Dadurch sinkt der Speicherbedarf, und die Übertragungszeit verkürzt sich. In der Nachrichtentechnik heißt die Komprimierung von Nachrichten durch einen Sender Quellenkodierung.
Grundsätzlich versucht Datenkompression, redundante Informationen zu entfernen. Die Daten werden durch einen Kodierer in eine Darstellung überführt, in der alle oder zumindest die meisten Informationen kürzer darstellbar sind. Dieser Vorgang heißt Kompression oder Komprimierung. Die Umkehrung heißt Dekompression oder Dekomprimierung.
Man unterscheidet zwei Hauptarten. Bei verlustfreier Kompression, auch verlustfreie Kodierung oder Redundanzreduktion, können aus den komprimierten Daten wieder exakt die Originaldaten gewonnen werden. Das ist etwa bei ausführbaren Programmdateien nötig. Bei verlustbehafteter Kompression, auch Irrelevanzreduktion, können die Originaldaten meist nicht exakt zurückgewonnen werden; ein Teil der Information geht verloren. Solche Verfahren versuchen, möglichst nur „unwichtige“ Informationen wegzulassen, und werden häufig für Bild-, Video- und Audiodaten genutzt.
Auswahl von Verfahren und Grenzen
Datenkompression wird heute bei den meisten Fernübertragungen digitaler Daten eingesetzt, um Ressourcen bei Übertragung oder Speicherung zu sparen. Verlustlos lassen sich nur Daten komprimieren, die in irgendeiner Form redundant sind. Bei völlig zufälligen Daten ist verlustlose Kompression wegen der Kolmogorov-Komplexität prinzipiell unmöglich. Auch das Taubenschlagprinzip zeigt, dass nicht jede beliebige Datei verlustlos komprimiert werden kann.
Kompression und Dekompression brauchen Rechenaufwand auf Sender- und Empfängerseite. Verfahren unterscheiden sich stark: Deflate und LZO sind bei Kompression und Dekompression sehr schnell. LZMA benötigt bei der Kompression viel Aufwand, erreicht dafür aber besonders kleine Datenmengen; die Dekompression ist sehr schnell. Je nach Anwendung wird daher eher auf Datendurchsatz, Energiebedarf oder Datenreduktion optimiert, nicht immer auf die kleinstmögliche Datei.
Bei Live-Übertragungen von Video oder Ton müssen Kompression und Wiederherstellung schnell sein; Qualitätsverluste können akzeptabel sein, solange die maximale Übertragungsrate eingehalten wird. Wird eine Datei von sehr vielen Nutzern heruntergeladen, lohnt sich dagegen ein langsamer, aber starker Algorithmus, weil die eingesparte Bandbreite den Aufwand ausgleicht. Für Datensicherung und Archivierung sind verbreitete und bewährte Algorithmen wichtig, die auch in ferner Zukunft verwendbar sind. Auch die Datenart spielt eine Rolle: gzip komprimiert 32.000 Bytes große Blöcke, bzip2 nutzt 900.000 Bytes Blockgröße; Redundanz wird nur innerhalb dieser Blöcke genutzt.
Manchmal werden Daten vor der eigentlichen Kompression in eine andere Darstellung transformiert. Dieser Schritt heißt Präkodierung. Beispiele sind die Burrows-Wheeler-Transformation und Move to front bei bzip2. Das Fachgebiet überschneidet sich mit Informationstheorie und Künstlicher Intelligenz, bei verlustbehafteter Kompression auch mit Wahrnehmungspsychologie. Die Dateigröße eines bestmöglich komprimierten Datensatzes gibt direkt seinen Informationsgehalt an.
Verlustfreie Kompression
Bei verlustloser Kompression können die Originaldaten exakt aus den komprimierten Daten wiederhergestellt werden. Es geht keinerlei Information verloren. Verlustfreie Verfahren nutzen vor allem Redundanz aus. Die theoretische Grundlage ist die Informationstheorie, verwandt mit der algorithmischen Informationstheorie. Sie gibt über den Informationsgehalt eine minimale Anzahl an Bits vor, die zur Kodierung eines Symbols nötig ist. Verlustlose Verfahren versuchen, Nachrichten so zu kodieren, dass sie sich ihrer Entropie möglichst gut annähern.
Textdateien können in der Regel auf 15–30 % ihrer ursprünglichen Größe komprimiert werden. Programmcode lässt sich oft stärker komprimieren, weil Schlüsselwörter in vorgegebenen Zusammenhängen auftreten. Eine bloße Liste von Wörtern ohne Zusammenhang wird relativ schlecht komprimiert; natürlicher Text liegt dazwischen. In der Praxis werden oft mehrere Methoden nacheinander genutzt: gzip und ZIP verwenden zuerst eine Wörterbuchmethode und danach eine Entropiekodierung. Sehr schnelle Verfahren wie Lempel-Ziv-Oberhumer nutzen nur Wörterbuch-Kompression. In der komprimierten Datei wird außerdem eine Prüfsumme der ursprünglichen Daten gespeichert, damit geprüft werden kann, ob bei der Dekompression die Originaldaten wiederhergestellt wurden.
Die Wörterbuchmethode ersetzt häufig wiederkehrende Textbestandteile durch kürzere Zeichenfolgen oder Verweise. Zum Beispiel kann ein wiederholtes Wort durch ein Token ersetzt werden. Der Text kann auch sein eigenes Wörterbuch sein: Wiederholungen werden durch Referenzen auf frühere Stellen beschrieben, etwa mit Angabe von Abstand und Länge.
Run length encoding (RLE), deutsch Lauflängenkodierung, speichert identische direkt aufeinanderfolgende Bestandteile nur einmal zusammen mit der Anzahl ihrer Wiederholungen. Die Burrows-Wheeler-Transformation formt einen Text umkehrbar so um, dass gleiche Buchstaben möglichst oft hintereinander stehen; dadurch kann RLE besser wirken.
Entropiekodierung gibt häufigen Zeichen oder Textteilen kurze Codes und seltenen längere. Der Morse-Code ist ein anschauliches Beispiel: Häufige Buchstaben wie E erhalten kurze Zeichen, seltene wie Q längere. Huffman-Code ist präfixfrei, sodass keine Trennzeichen nötig sind. Da binäre Bäume nicht immer optimal sind, wurden arithmetische Kodierung und Bereichskodierung entwickelt. Asymmetric Numeral Systems, besonders die tANS-Variante, setzt die Idee eines Binärbaums mit finite-state entropy effizient um und wird etwa in Zstandard verwendet.
Grenzen der Komprimierbarkeit
Bei verlustbehafteter Kompression sind die Grenzen fließend und hängen vom Anwendungsfall ab. Die Schwelle dafür, was als entbehrlich gilt, kann immer weiter erhöht werden, bis nur noch 1 Bit übrig bleibt. Dabei kann aber die für eine bestimmte Frage nötige Information verloren gehen. Bei Bildern gehen zunehmend Details verloren oder werden unscharf, bis alles zu einer einheitlichen Farbfläche verschwimmt. Bei Audio wird die Aufnahme dumpfer und undeutlicher; nach größtmöglicher Kompression würde sie bei den meisten Algorithmen nur noch einen einfachen Sinuston enthalten.
Bei verlustfreier Kompression sind die Grenzen strenger, weil die Originaldatei exakt rekonstruierbar sein muss. Die Kolmogorow-Komplexität beschreibt die kleinstmögliche „Anleitung“, die nötig ist, um aus den komprimierten Daten die Originaldaten wiederherzustellen. Die Zahl „100000000000000000000000000000000000“ kann etwa beschrieben werden als „Schreibe 1 und dann 35 Nullen“, was eine Kompression von 36 auf 29 Zeichen darstellt. Auch viele Nachkommastellen von Pi könnten mit einer Berechnungsvorschrift beschrieben werden, wenn der Algorithmus erkennt, dass es sich um Pi handelt. Der Wiederherstellungs-Algorithmus müsste zur Dateigröße mitgerechnet werden, weil eine komprimierte Datei ohne ihn wertlos ist.
Das Taubenschlagprinzip erklärt, warum nicht jede Datei verlustlos kleiner werden kann. Auf n Bit lassen sich 2^{n} mögliche Informationen speichern; auf einem um ein Bit kleineren Speicherplatz nur halb so viele. 16 Bits erlauben 2^{16} = 65536 mögliche Informationen, 15 Bits nur 2^{15} = 32768. Wenn jede Datei um ein Bit verkleinert werden könnte, müssten verschiedene Dateien denselben komprimierten Zustand teilen. Das wäre für verlustfreie Kompression unmöglich, weil die Zuordnung eindeutig umkehrbar sein muss.
Daraus folgt: Rein zufällige Daten sind höchstwahrscheinlich unkomprimierbar, weil sie meist keine Struktur enthalten. Bereits komprimierte Daten lassen sich in der Praxis nur dann nochmals komprimieren, wenn der vorherige Algorithmus nicht vollständig effizient war. Zwei Preisgelder, 100 Dollar für die Kompression von einer Million zufälliger Ziffern und 5000 Dollar für die Kompression einer beliebig langen Datei des Preisstifters Mike Goldman, wurden noch nicht ausbezahlt.
Verlustbehaftete Medienkompression
Bei verlustbehafteter Kompression werden irrelevante Informationen entfernt; deshalb spricht man auch von Irrelevanzreduktion. Aus den komprimierten Daten kann das Original nicht vollständig rekonstruiert werden. Dafür braucht man ein Modell, das entscheidet, welcher Anteil der Information für den Empfänger entbehrlich ist. Bei Bild-, Video- und Audio-Übertragung ist dieses Modell meist die menschliche Wahrnehmung. Ein bekanntes Beispiel ist MP3: Das Format entfernt Frequenzmuster, die Menschen schlecht oder gar nicht hören. Die theoretische Grundlage ist die Rate-Distortion-Theorie; sie beschreibt, welche Datenübertragungsrate mindestens nötig ist, um Informationen mit einer bestimmten Güte zu übertragen.
Ton, Bild und Film erzeugen sehr große Datenmengen. Ihre Kompression orientiert sich an physiologischen Eigenschaften des Menschen. Häufig werden Signalverläufe von Abtastsignalen in eine Frequenzdarstellung umgewandelt. In der akustischen Wahrnehmung werden Frequenzen oberhalb von ca. 20 kHz nicht mehr wahrgenommen und können bereits im Aufnahmesystem abgeschnitten werden. Leise Nebentöne sind in einem Klanggemisch schwer hörbar, wenn gleichzeitig sehr laute Töne auftreten; solche unhörbaren Frequenzanteile können entfernt werden. Bei digitalisierten akustischen Ereignissen wie Musik, Sprache und Geräuschen kann der Mensch bei etwa 192 kbit/s oft kaum oder gar keine Qualitätsunterschiede zum unkomprimierten Ausgangsmaterial einer CD feststellen.
In der optischen Wahrnehmung werden Farben weniger stark aufgelöst als Helligkeitsänderungen. Daraus leitet sich die YUV-422-Reduzierung ab. Kanten sind dagegen wichtig, und es gibt eine biologische Kontrastanhebung, die Machschen Streifen. Mit moderater Tiefpassfilterung zur Farbreduktion, etwa durch den auf DCT-Transformation basierenden JPEG-Algorithmus oder den auf Wavelet-Transformation basierenden JPEG2000-Algorithmus, lässt sich die Datenmenge meist auf 10 % oder weniger der ursprünglichen Datenmenge reduzieren, ohne deutliche Qualitätsverluste.
Bei stark komprimierten JPEG-Bildern können 8 × 8 Pixel große Quadrate sichtbar werden. Solche Signalstörungen heißen Kompressionsartefakte. Bei Filmen werden nicht nur Einzelbilder komprimiert. Moderne Verfahren nutzen zusätzlich die Ähnlichkeit benachbarter Frames: Das Bild wird in kleine Kästchen zerlegt, typische Größen liegen zwischen 4×4 und 16×16 Pixel. Es werden ähnliche Kästchen in schon übertragenen Bildern gesucht, und statt des ganzen Inhalts werden nur Unterschiede oder Verschiebungsvektoren gespeichert.
