Datenkompression

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Die Datenkompression oder Datenkomprimierung ist ein Vorgang, bei dem die Menge digitaler Daten reduziert wird. Dadurch sinkt der benötigte Speicherplatz und die Übertragungszeit der Daten verkürzt sich. In der Nachrichtentechnik wird die Komprimierung von Nachrichten aus einer Quelle durch einen Sender als Quellenkodierung bezeichnet.[1][2]

Grundsätzlich wird bei der Datenkompression versucht, überflüssige Information zu entfernen. Dazu werden die Daten in eine Darstellung überführt, mit der sich alle – oder zumindest die meisten – Informationen in kürzerer Form darstellen lassen. Diesen Vorgang übernimmt ein Kodierer und man bezeichnet den Vorgang als Kompression oder Komprimierung. Die Umkehrung bezeichnet man als Dekompression oder Dekomprimierung.

Man spricht von verlustfreier Kompression (oder verlustfreier Kodierung), wenn aus den komprimierten Daten wieder alle Originaldaten gewonnen werden können. Das ist beispielsweise bei der Kompression ausführbarer Programmdateien notwendig.

Bei der verlustbehafteten Kompression können die Originaldaten nicht mehr aus den komprimierten Daten zurückgewonnen werden, das heißt ein Teil der Information ging verloren. Solche Verfahren werden häufig zur Bild- oder Videokompression und Audiodatenkompression eingesetzt.

Allgemein[Bearbeiten]

Datenkompression findet heutzutage bei jeglicher Übertragung von digitalen Daten statt. Sie hilft Ressourcen bei der Übertragung zu sparen (z. B. Bandbreite oder Speicherplatz) indem die Daten in einer Form übertragen werden, die ̣– abhängig von der Anwendung – möglichst minimal ist. Im Gegenzug ist sowohl auf Sender-, als auch auf Empfängerseite erheblicher Berechnungsaufwand nötig, um die ursprünglichen Daten wiederherzustellen.

Kompressionsverfahren können, abhängig von ihrer Anwendung, auf Datendurchsatz, Energiebedarf oder die Datenreduktion optimiert sein. Die Kompression hat nicht immer eine möglichst kompakte Darstellung als Ziel. Die Reduktion von Daten auf ihr Minimum ist i. d. R. mit erheblichem Aufwand verbunden. Ebenso steigt auch der Aufwand, die ursprünglichen Daten wiederherzustellen. Bei mobilen Geräten ist dies wegen des dafür notwendigen Energiebedarfs unerwünscht; ebenso bei Echtzeit-Anwendungen, wie z. B. bei Audio- oder Video-Streams, um die Verzögerung gering zu halten.

Mitunter werden die Daten vor der Kompression noch in eine andere Darstellung transformiert. Das ermöglicht einigen Verfahren die Daten anschließend effizienter zu komprimieren. Dieser Vorverarbeitungsschritt wird Präkodierung genannt. Ein Beispiel dafür ist die Burrows-Wheeler-Transformation und Move to front bei bzip2.

Das Fachgebiet der Datenkompression überschneidet sich zum Teil mit Informationstheorie und künstlicher Intelligenz, und im Bereich der verlustbehafteten Datenkompression auch mit Wahrnehmungspsychologie (s. weiter unten). Informationstheorie ist insofern betroffen, weil die Dateigrösse eines bestmöglich komprimierten Datensatzes direkt den Informationsgehalt dieses Datensatzes angibt.

Kann ein Kompressionsalgorithmus lernen, unter welchen Umständen auf die Zeichenkette "ABC" ein "D" folgt, muss das "D" in der komprimierten Datei gar nicht gespeichert werden - bei der Wiederherstellung der ursprünglichen Datei weiß der Algorithmus, an welchen Stellen ein "D" einzufügen ist. Obwohl noch kein derartiger Kompressionsalgorithmus in der Praxis verwendet wird, sind diverse Kompressionsverfahren, die neuronale Netzwerke und maschinelles Lernen verwenden, in Entwicklung.[3]

Verlustlose Kompression[Bearbeiten]

Bei der verlustlosen Kompression können die Originaldaten exakt aus den komprimierten Daten wiederhergestellt werden. Dabei geht keinerlei Information verloren. Im Wesentlichen nutzen verlustlose Kompressionsverfahren die Redundanz von Daten aus, man spricht auch von Redundanzreduktion.

Die theoretische Grundlage bildet die Informationstheorie (verwandt mit der algorithmischen Informationstheorie). Sie gibt durch den Informationsgehalt eine minimale Anzahl an Bits vor, die zur Kodierung eines Symbols benötigt werden. Verlustlose Kompressionsverfahren versuchen nun Nachrichten so zu kodieren, dass sie sich ihrer Entropie möglichst gut annähern.

Text[Bearbeiten]

Texte, sofern sie aus Buchstaben bestehen oder als Zeichenketten abgespeichert sind, und somit nicht als Bild (Rastergrafik, typischerweise eine Bilddatei nach dem Einscannen eines Buches), belegen vergleichsweise wenig Speicherplatz. Dieser lässt sich durch ein Verfahren zur verlustfreien Kompression auf 20 % bis 10 % des ursprünglich von ihr benötigten Platzes reduzieren.

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.

Wörterbuchmethode[Bearbeiten]

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" 

Die Zuordnung von den Tokens zu den eigentlichen Wörtern muss in der komprimierten Datei ersichtlich sein.

Run length encoding (RLE)[Bearbeiten]

Identische Textbestandteile, die hintereinander stehen, werden bloss einmal abgespeichert - mit der Anzahl ihrer Wiederholungen. Hier wird " 10 Grad," drei Mal wiederholt:

Ausgangstext: In den letzten Tagen betrug die Temperatur 10 Grad, 10 Grad, 10 Grad, und dann 14 Grad.
  Kodiertext: In den letzten Tagen betrug die Temperatur/3/ 10 Grad,/ und dann 14 Grad.

Die Burrows-Wheeler-Transformation ist eine umkehrbare Operation, welche einen gegebenen Text so umformt, dass dieselben Buchstaben möglichst oft gleich hintereinander stehen. So können die Daten dann mit RLE komprimiert werden.

Entropiekodierung[Bearbeiten]

Verfahren der so genannten Entropiekodierung:

Der bekannte Morse-Code funktioniert nach einem ähnlichen Prinzip, und dient als gutes Beispiel: Häufige Buchstaben der englischen Sprache (z.B. E = .) werden als kurze Codes abgespeichert, seltene als lange Codes (z.B. Q = _ _ . _).

Eine sehr einfache, aber nicht sehr effiziente Entropiekodierung besteht darin, alle Teile einer Nachricht nach ihrer Häufigkeit zu sortieren, und mittels binären Zahlen zu nummerieren:

Ausgangstext: WENN HINTER FLIEGEN FLIEGEN FLIEGEN, FLIEGEN FLIEGEN FLIEGEN NACH.

Das Wörterbuch lautet nun wie folgt, mit "_" als Leerzeichen:

Textteil... ...wird ersetzt durch...
_FLIEGEN 1
WENN_ 10
_NACH. 11
HINTER 100
, 101

Der komprimierte Text lautet nun:

Kodiertext: 10 100 1 1 1 101 1 1 1 11

Der Entropiekodierung entsprechend werden die häufigsten Textbestandteile durch die kürzesten Symbole ersetzt.

66 Zeichen wurden nun zu 25 Zeichen komprimiert. Unter der Annahme, dass der ursprüngliche Text als ASCII-Text gespeichert wurde (7 bits pro Zeichen), wurden somit 462 bits zu 25 Zeichen komprimiert - wovon 16 Zeichen bereits einzelne bits darstellen (Nullen und Einsen), und keine ASCII-Textzeichen. Allerdings muss auch das Wörterbuch berücksichtigt und in der komprimierten Datei abgespeichert werden - ohne dieses lässt sich die ursprüngliche Datei nicht rekonstruieren.

Programmdateien[Bearbeiten]

Bei Programmdateien ist es kritisch, dass sie nach erfolgter Dekomprimierung wieder im ursprünglichen Zustand sind. Andernfalls wäre eine fehlerfreie bzw. korrekte Ausführung unwahrscheinlich. Komprimierte Programmdateien sind meist selbst wieder ausführbare Dateien. Sie bestehen aus einer Routine, die den Programmcode wieder dekomprimiert und anschließend ausführt. Dadurch ist die Kompression des Programms für den Benutzer vollkommen transparent.

Anwendungsbeispiele sind UPX und Upack.

Verlustbehaftete Kompression[Bearbeiten]

Bei der verlustbehafteten Kompression werden irrelevante Informationen entfernt, man spricht auch von Irrelevanzreduktion. Dabei geht ein Teil der Information aus den Originaldaten verloren, sodass aus den komprimierten Daten nicht mehr das Original rekonstruiert werden kann.

Es wird ein Modell benötigt, das entscheidet, welcher Anteil der Information für den Empfänger entbehrlich ist. Verlustbehaftete Kompression findet meist in der Bild-, Video- und Audio-Übertragung Anwendung. Als Modell wird dort die menschliche Wahrnehmung zugrunde gelegt. Ein populäres Beispiel ist das Audio-Format MP3, das für Menschen nicht wahrnehmbare Frequenzen weglässt.

Die theoretische Grundlage bildet die Rate-Distortion-Theorie. Sie beschreibt, welche Datenübertragungsrate mindestens nötig ist, um Informationen mit einer bestimmten Güte zu übertragen.

Bilder, Videos und Tonaufnahmen[Bearbeiten]

Bei stark komprimierten Bildern im JPEG-Format zeichnen sich 8 × 8 Pixel große Quadrate als Kompressionsartefakte ab. Oben Originalgröße, unten Ausschnittsvergrößerung
Vergleich der Kompressionsartefakte im JPEG-Format mit dem verlustfreien PNG-Format

Ton, Bild und Film sind Einsatzgebiete verlustbehafteter Kompression. Anders wären die oftmals enormen Datenmengen sehr schwer 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 von ca. 20 kHz nicht mehr wahrgenommen und können bereits im Aufnahmesystem beschnitten werden. Ebenso werden existierende, leise Nebentöne in einem Klanggemisch nur schwer wahrgenommen, wenn zur exakt gleichen Zeit sehr laute Töne auftreten, so dass die unhörbaren Frequenzanteile vom Daten-Kompressions-System entfernt werden können (siehe Psychoakustik), ohne dass dies als störend vom Hörer wahrgenommen würde. Der Mensch kann bei einer Reduktion von digitalisierten, akustischen Ereignissen (Musik, Sprache, Geräusche) auf Werte um etwa 192 kbit/s (wie bei vielen Internet-Downloads) kaum oder gar keine Qualitätsunterschiede zum unkomprimierten Ausgangsmaterial (so bei einer CD) feststellen.

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 lässt sich die Datenmenge auf 10 % oder weniger der ursprünglichen Datenmenge ohne sichtbare Qualitätsverringerungen reduzieren.

Bewegtbilder (Filme) bestehen aus aufeinanderfolgenden Phasen-Bildern. Die heutzutage erreichbaren Kompressionraten sind dabei nur erreichbar, wenn man bei der Kodierung die Ähnlichkeit von benachbarten Bildern (engl. Frames) berücksichtigt. Dazu wird das Bild in kleinere Kästchen (typische Größen liegen zwischen 4×4 und 16×16 Pixel) zerlegt und es werden ähnliche Kästchen in schon übertragenen Bildern gesucht und als Vorlage verwendet. Die Einsparung ergibt sich daraus, dass statt des gesamten Bildinhalts nur noch die Unterschiede der an sich ähnlichen Kästchen übertragen werden müssen.

Kompressionsartefakte[Bearbeiten]

Hauptartikel: Kompressionsartefakt

Als Kompressionsartefakte bezeichnet man Signalstörungen, die durch die verlustbehaftete Kompression verursacht werden.

Anwendung in der Nachrichtentechnik[Bearbeiten]

Nutzung von Quellen-, Kanal- und Leitungskodierung zur Übertragung eines Signals

Bei der Datenübertragung wird häufig die zu übertragende Datenmenge durch Kompression reduziert. In so einem Fall spricht man dann auch von Quellenkodierung.[1][2] Die Quellenkodierung wird dabei häufig zusammen mit Kanalkodierung und Leitungskodierung verwendet, sollte aber nicht mit diesen verwechselt werden: Während die Quellencodierung überflüssige (redundante) Information einer Datenquelle reduziert, hat die Kanalcodierung die Aufgabe, durch zusätzlich eingebrachte Redundanz Übertrags- bzw. Speicherfehler im Rahmen der Datenübertragung erkennen und korrigieren zu können. Die Leitungskodierung hingegen nimmt eine spektrale Anpassung des Signals an die Anforderungen des Übertragungskanals vor.

Zeittafel der Kompressions-Algorithmen[Bearbeiten]

1949 Informationstheorie, Claude Shannon
1949 Shannon-Fano-Kodierung
1952 Huffman-Kodierung, static
1964 Konzept der Kolmogorow-Komplexität
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)
1991 Reduced Offset Lempel Ziv (ROLZ, auch LZRW4, Lempel Ziv Ross Williams)
1994 Burrows-Wheeler-Transformation
1996 Lempel-Ziv-Oberhumer-Algorithmus (LZO)
1997 Sequitur
1998 Lempel-Ziv-Markow-Algorithmus (LZMA)

Bekannte Methoden zur Quellcodierung[Bearbeiten]

verlustbehaftet beides möglich verlustfrei
AAC (MPEG)
Aiff
ALS (MPEG)
Apple Lossless
ATRAC
DjVu
Dolby Digital
DTS
FLAC
Monkey’s Audio
G.729
GIF
HuffYUV
JPEG
JPEG 2000
LA
MJPEG
MP2 (MPEG)
MP3 (MPEG)
MPEG-1
MPEG-2
MPEG-4 (siehe H.264, Xvid, DivX)
Musepack
PGF
PNG
TGA
TIFF
Vorbis (Ogg)
WavPack
WebP
WMA
WMV
Bilder Audio Video

Datenübertragung[Bearbeiten]

  • 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

Biologie[Bearbeiten]

Sinneswahrnehmungen werden gefiltert, was auch eine Art der Kompression darstellt, genauer eine verlustbehaftete Kompression, da nur aktuell relevante Informationen wahrgenommen werden. Fehlendes wird bei Bedarf unbewusst ersetzt. So sehen menschliche Augen beispielsweise nur in einem kleinen Bereich (Fovea centralis) scharf, außerhalb dieses engen Blickfeldes werden fehlende Informationen durch Muster unbewusst ersetzt. Aber auch beim Hören von Geräuschen werden schwache oder fehlende Signale ersetzt, was sich auch Algorithmen wie MPEG (MP3) oder Vorbis zunutze machen.

Siehe auch[Bearbeiten]

Weblinks[Bearbeiten]

 Wikibooks: Buch zu Datenkompression – Lern- und Lehrmaterialien

Einzelnachweise[Bearbeiten]

  1. a b Quellen- und Leitungscodierung - Skript Kommunikationstechnik, SS 08, Prof. Dr. Stefan Brunthaler (PDF; 136 kB) auf tfh-wildau.de
  2. a b Quellencodierung - Gelenktes Entdeckendes Lernen Peter Maluck, Jürg Scheidegger, ETH Zürich (PDF; 795 kB) auf educ.ethz.ch
  3. Matthew V. Mahoney: "Fast Text Compression with Neural Networks", American Association for Artificial Intelligence, 2000.