Datenkompression

Datenkompression

Datenkompression oder Datenkomprimierung ist ein Verfahren auf digitaler Ebene, um Speicherplatz einzusparen oder um die Übertragungszeit von Daten zwischen zwei Computern (oder Teilnehmern) zu verkürzen. Die Organisation (Struktur) der Daten wird hierfür geändert und muss bei der schließlichen Nutzung reorganisiert werden. Man spricht vom Kodieren und Dekodieren.

Die Datenmenge wird reduziert, indem eine günstigere Repräsentation bestimmt wird, mit der sich die gleichen Informationen in kürzerer Form darstellen lassen. Diesen Vorgang übernimmt ein Kodierer, und man bezeichnet den Vorgang als Kompression bzw. Kodierung. Die Umkehrung bezeichnet man als Dekompression oder Dekomprimierung. Man spricht von einer verlustfreien Kompression (oder verlustfreien Kodierung), wenn die kodierten Daten nach Anwendung der entsprechenden Dekodiervorschrift exakt denen des Originals entsprechen. Dies ist beispielsweise bei der Kompression ausführbarer Programmdateien notwendig. Verlustbehaftet wird die Kompression oder Kodierung genannt, wenn sich die Daten im Allgemeinen nicht fehlerfrei rekonstruieren lassen. Solche Verfahren werden häufig zur Bildkompression oder Audiodatenkompression eingesetzt. Werden mehrere Dateien komprimiert, können diese vorher durch ein Packprogramm zusammengefasst werden. Enthalten die Dateien Gemeinsamkeiten, so wird dadurch die Kompression verbessert.

In der Nachrichtentechnik wird das Kodieren von Nachrichten aus einer Quelle durch einen Sender als Quellenkodierung bezeichnet.

Inhaltsverzeichnis

Informatik

Redundanz- und Irrelevanzreduktion

Die Datenkompression wird teils durch „günstigere Repräsentation“, das heißt Vermeiden von Redundanz und Erhöhen der Entropie, teils durch Weglassen von Information erreicht. Wenn die Daten mit einem Dekompressionsverfahren wieder originalgetreu hergestellt werden, arbeitet es verlustfrei. Man spricht dann von Redundanzreduktion. Andernfalls ist es verlustbehaftet. In diesem Fall spricht man von Irrelevanzreduktion. Beide Verfahren können kombiniert werden.

Bei der verlustfreien Kompression werden die originären Daten in komprimierte Daten überführt, die die ursprünglichen Informationen vollständig enthalten. Die Überführung muss nicht eindeutig sein, aber auf jeden Fall umkehrbar. Verschiedene Kompressionsprogramme und Heuristiken können unterschiedlich hohe Kompressionsraten eines Kompressionsformates erzeugen.

Die verlustbehaftete Kompression reduziert die Information. Es wird ein Modell zugrunde gelegt, das entscheidet, welcher Anteil der Information für den Empfänger entbehrlich ist. Da eine solche Abbildung nicht mehr eindeutig ist, kann die ursprüngliche Information mittels Dekompression nicht wiederhergestellt werden.

Symmetrische und asymmetrische Kompression

Ein Verfahren zur asymmetrischen Kompression benötigt zum Kodieren (Komprimieren) einen wesentlich höheren zeitlichen Aufwand als zum Dekodieren. Im Gegensatz dazu benötigt ein symmetrisches Verfahren ungefähr gleichviel Zeit für Kompression und Dekompression.

Verfahren

Die theoretische Grundlage bildet die von Mathematikern (Claude Shannon; Andrei Kolmogorow) 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.

Durch geeignete Kompressionsverfahren erreicht man gute Annäherungen an die Kanalkapazität.

In neuerer Zeit gibt es umgekehrt auch Ansätze, den Informationsgehalt auf die „Nichtmehrverkürzbarkeit“ zurückzuführen (Chaitin).

Einsatzgebiete

Speicherung von Text

Texte, sofern sie aus Buchstaben bestehen bzw. als Zeichenketten abgespeichert sind, und somit nicht als Bild (Rastergrafik, typischerweise z. B. 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.

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" 

Verfahren der so genannten Entropiekodierung:

Präkodierung

Präkodierung umfasst alle Techniken der Datenkompression, welche in Daten vorhandene statistische Abhängigkeiten ausnutzen. Diese Techniken bilden Symbole aus einem Alphabet auf Symbole eines anderen Alphabets ab bzw. unterstützen diesen Prozess. Die Anzahl der Symbole kann sich dabei verändern (im Gegensatz z. B. zu Verfahren der Dekorrelation, welche ebenfalls Korrelationen im Signal auflösen). Oft werden die Ergebnisse nochmals entropiekodiert.

Sehr verschiedene Algorithmen gehören zur Gruppe der Präkodierung: Lauflängenkodierung, Phrasenkodierung (besser bekannt als wörterbuchbasierte Kodierung wie z. B. LZ78 und LZW), Blocksortierung (auch bekannt als Burrows-Wheeler-Transformation), Quadtree-Kodierung und andere.

Heutzutage stehen viele Datenkompressionsprogramme für den Rechnereinsatz zur Verfügung.

Speicherung von Bildern und Ton

Ton, Bild und Film sind Einsatzgebiete verlustbehafteter Kompression. Anders wären die oftmals enormen Datenmengen nicht 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 z.B. 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 (z.B. 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 4x4 und 16x16 Pixel) zerlegt und es werden ähnliche Kästchen in schon übertragenen Bildern gesucht und als Vorlage verwendet. Die Einsparung ergibt sich daraus, das statt dem gesamten Bildinhalt nur noch die winzigen Unterschiede der an sich ähnlichen Kästchen übertragen werden müssen.

Kompressionsartefakte
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- und im PNG-Format

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

Beispiele:

  • schnarrende Stimme beim Mobilfunkempfang
  • typischer Klang des Telefons (Frequenzclipping)
  • bei Bildkompression wie JPEG, auch bei Videokompression, wie MPEG:
    • unscharfe Kanten (JPEG, JPEG2000)
    • Unschärfe (JPEG, JPEG2000)
    • Blockartefakte (JPEG – siehe Bild rechts, MPEG)
    • Gibbssches Phänomen: eine kleine Fläche um einen Gegenstand mit hohem Kontrast, welcher deutlich aus der Umgebung heraussticht (JPEG, JPEG2000)
    • Farbverfälschungen (JPEG, JPEG2000)
    • Schwarz/Weiß-Konturen
    • Farbkonturen
    • Wabernder Hintergrund: wechselnde Artefakte in Bildfolgen (animierte Grafiken, Video)
  • bei Audiodatenkompression, wie MP3 oder Vorbis:
    • Pre-echo: vor einem lauten plötzlichen Geräusch (zum Beispiel Schlagzeug) sind klirrend-metallische Artefakte hörbar
    • Post-echo: nach einem plötzlichen Geräusch sind deutliche Artefakte zu hören
    • verwaschener Klang, mangelnde Brillanz, insbesondere in Höhen und Tiefen, sowie bei bestimmten Instrumenten (Hi-hat)
    • Scheppern (typisch für MP3 bei zu hoher Kompression)
    • unpassende Lautstärkeänderungen
    • Veränderung der Stereofonie, Verringerung des räumlichen Eindrucks

Speicherung von ausführbaren Dateien

siehe Kompression ausführbarer Programmdateien. Anwendungsbeispiele sind UPX und Upack.

Zeittafel der Kompressions-Algorithmen

1949 Informationstheorie, Claude Shannon
1949 Shannon-Fano-Entropiekodierung
1952 Huffman, static
1964 Kolmogorov complexity concept
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
1997 Sequitur
1998 Lempel-Ziv-Markow-Algorithmus (LZMA)

Bekannte Methoden zur Quellcodierung

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
WMA
WMV
WebP
Bilder Audio Video

Datenübertragung

  • 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

Komprimierung/Archivierung

Biologie

Auch in der Biologie gibt es Kompressionsalgorithmen. So wird bei Eukaryonten die Information für Proteine nicht immer in einer zusammenhängenden DNA-Sequenz kodiert. Durch ein System von Introns und Exons und die Verarbeitung der mRNA durch alternatives Splicing kann eine DNA-Sequenz die Information für mehrere unterschiedliche Eiweiße tragen. Der jeweilige Kompressionsalgorithmus wird dabei durch den Spleißvorgang und seine Regulation definiert. 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 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

Weblinks

Wikibooks Wikibooks: Buch zu Datenkompression – Lern- und Lehrmaterialien

Wikimedia Foundation.

Игры ⚽ Нужна курсовая?
Synonyme:

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Datenkompression — Dateikompression * * * Datenkompression,   Komprimierung …   Universal-Lexikon

  • Datenkompression — duomenų spūda statusas T sritis radioelektronika atitikmenys: angl. data compression vok. Datenkompression, f rus. сжатие данных, n pranc. compression de données, f …   Radioelektronikos terminų žodynas

  • Datenkompression — Da|ten|kom|pres|si|on*, auch Da|ten|kom|pri|mie|rung die; , en: Veränderung von Daten od. Zeichen mit dem Ziel, den Bedarf an Speicherplatz zu verringern oder die Übertragungsgeschwindigkeit zu erhöhen …   Das große Fremdwörterbuch

  • Datenkompression — eine Technik, um redundante Informationen in Dateien auf ein Minimum zu kürzen. Die Dateigröße und somit die Zeit zur Datenübermittlung z. B. im Internet wird deutlich verringert. Es gibt Verlust freie Kompression und Verlustkompression. Verlust… …   Erläuterung wichtiger Begriffe des Bauwesens

  • Verlustbehaftete Datenkompression — Datenkompression oder Datenkomprimierung ist die Anwendung von Verfahren zur Reduktion des Speicherbedarfs von Daten bzw. zur Vermeidung von Datenaufkommen, bspw. während der Übertragung von Daten. Die Datenmenge wird reduziert, indem eine… …   Deutsch Wikipedia

  • Verlustfreie Datenkompression — Datenkompression oder Datenkomprimierung ist die Anwendung von Verfahren zur Reduktion des Speicherbedarfs von Daten bzw. zur Vermeidung von Datenaufkommen, bspw. während der Übertragung von Daten. Die Datenmenge wird reduziert, indem eine… …   Deutsch Wikipedia

  • LZ78-Datenkompression — LZ78 ist ein von Jacob Ziv und Abraham Lempel entwickeltes Verfahren zur Datenkompression. LZ78 ist der Nachfolger vom ein Jahr zuvor erschienen Algorithmus LZ77. Während der LZ77 Algorithmus mit alten Daten arbeitet, zielt LZ78 auf neue Daten ab …   Deutsch Wikipedia

  • LZW-Datenkompression — Der LZW oder auch Lempel Ziv Welch Algorithmus ist ein häufig bei Grafikformaten zur Datenkompression, also zur Reduzierung der Datenmenge, eingesetzter Algorithmus. Ein Großteil der Funktionsweise dieses Algorithmus wurde 1978 von Abraham Lempel …   Deutsch Wikipedia

  • Dateikompression — Datenkompression …   Universal-Lexikon

  • Dateiarchivierung — Datenkompression oder Datenkomprimierung ist die Anwendung von Verfahren zur Reduktion des Speicherbedarfs von Daten bzw. zur Vermeidung von Datenaufkommen, bspw. während der Übertragung von Daten. Die Datenmenge wird reduziert, indem eine… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”