Datenkompression

2025-03-13T13:53:23Z

24.134.182.9: Satzbau und Kommafehler korr

Die '''Datenkompression''' (wohl [[Lehnübersetzung|lehnübersetzt]] und [[Eindeutschung|eingedeutscht]] aus dem [[Englische Sprache|englischen]] ''{{lang|en|data compression}}'') – auch (weiter eingedeutscht) '''Datenkomprimierung'''<ref>[https://www.duden.de/rechtschreibung/Datenkomprimierung Datenkomprimierung] – ''[[Duden]]'', ''[[Bibliographisches Institut]]''; 2016.</ref> genannt – ist ein Vorgang, bei dem die [[Datenmenge|Menge]] [[Digitalisierung|digitaler]] Daten reduziert wird. Dadurch sinkt der [[Speicherbedarf]], und die [[Datenübertragung|Übertragungszeit]] der Daten verkürzt sich.

In der [[Nachrichtentechnik]] wird die Komprimierung von Nachrichten durch einen Sender als '''Quellenkodierung''' bezeichnet.<ref name="QuLKomm. Prof. Brunthaler">{{Internetquelle |autor=Stefan Brunthaler |url=http://www.tm.th-wildau.de/brun/lehre/Material/KT/VL_KT_5_Codierung.pdf |titel=Quellen- und Leitungscodierung |werk=[[Technische Hochschule Wildau|TH Wildau]] |datum=2018 |format=PDF; 528 kB |kommentar=Vorlesungsscript ''Kommunikationstechnik in der [[Telematik]] SS2018'' |abruf=2018-08-12}}</ref><ref name="QC ETH Zürich">{{Internetquelle |autor=Peter Maluck, Jürg Scheidegger |url=https://www.ethz.ch/content/dam/ethz/special-interest/dual/educeth-dam/documents/Unterrichtsmaterialien/informationstechnologien-und-elektrotechnik/quellencodierung/quellencodierung.pdf |titel=Quellencodierung – Gelenktes Entdeckendes Lernen |werk=[[SwissEduc]] |datum=2009-08-24 |format=PDF; 776 kB |kommentar=Seminar ''Kommunikationstechnik'' |abruf=2018-08-12}}</ref>


Grundsätzlich wird bei der Datenkompression versucht, redundante Informationen zu entfernen. Dazu werden die Daten in eine Darstellung überführt, mit der sich alle – oder zumindest die meisten – [[Information]]en 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 ''[[#verlustfrei|verlustfreier Kompression]]'', ''verlustfreier Kodierung'' oder ''Redundanzreduktion'', wenn aus den komprimierten Daten wieder exakt die Originaldaten gewonnen werden können. Das ist beispielsweise bei der [[Kompression ausführbarer Programmdateien]] notwendig.

Bei der ''[[#verlustbehaftet|verlustbehafteten Kompression]]'' oder ''Irrelevanzreduktion'' können die Originaldaten aus den komprimierten Daten meist nicht mehr exakt zurückgewonnen werden, das heißt, ein Teil der Information geht verloren; die [[Algorithmus|Algorithmen]] versuchen, möglichst nur „unwichtige“ Informationen wegzulassen. Solche Verfahren werden häufig zur [[Bildkompression|Bild-]] oder [[Videokompression]] und [[Audiodatenkompression]] eingesetzt.

== Allgemein ==
Datenkompression findet heutzutage bei den meisten Fernübertragungen digitaler Daten statt. Sie hilft, Ressourcen bei der Übertragung oder Speicherung von Daten einzusparen, indem sie in eine Form verwandelt werden, die – abhängig von der Anwendung – möglichst minimal ist. Dabei können ''verlustlos'' nur Daten komprimiert werden, die in irgendeiner Form redundant sind. Ist keine Redundanz vorhanden – zum Beispiel bei völlig zufälligen Daten – ist verlustlose Kompression wegen der [[Kolmogorov-Komplexität]] prinzipiell unmöglich. Ebenso verbietet das [[Schubfachprinzip|Taubenschlagprinzip]], dass jede beliebige Datei verlustlos komprimiert werden kann. Hingegen ist [[#verlustbehaftet|verlustbehaftete Kompression]] immer möglich: Ein Algorithmus ordnet die Daten danach, wie wichtig sie sind und verwirft die „unwichtigen“ dann. In der Auflistung, wie wichtig welche Bestandteile sind, kann stets mehr verworfen werden, indem die „Behalten-Schwelle“ entsprechend verschoben wird.

Bei der Datenkompression ist sowohl auf Sender- als auch auf Empfängerseite Berechnungsaufwand nötig, um die Daten zu komprimieren oder wiederherzustellen. Der Berechnungsaufwand ist jedoch bei verschiedenen Kompressionsmethoden sehr unterschiedlich. So sind etwa [[Deflate]] und [[Lempel-Ziv-Oberhumer|LZO]] sowohl bei Kompression und Dekompression sehr schnell, während etwa [[Lempel-Ziv-Markow-Algorithmus|LZMA]] unter großem Aufwand eine besonders weitgehende Kompression – und somit möglichst kleine Datenmengen – erzielt, während komprimierte Daten sehr schnell wieder in die ursprüngliche Form zurückgewandelt werden können. Dies erzwingt je nach Anwendungsgebiet eine unterschiedliche Wahl der Kompressionsmethode. Daher sind Kompressionsmethoden entweder auf [[Datendurchsatz]], Energiebedarf oder die Datenreduktion optimiert, und die Kompression hat somit nicht immer eine möglichst kompakte Darstellung als Ziel. Deutlich wird der Unterschied bei diesen Beispielen:
* Werden Video- oder Tonaufnahmen live gesendet, müssen Kompression und Wiederherstellung möglichst schnell durchgeführt werden. Qualitätseinbußen sind vertretbar, wenn dafür die maximale (mögliche) Übertragungsrate eingehalten wird. Dies gilt beispielsweise für Telefongespräche, wo der Gesprächspartner oft auch bei schlechter Tonqualität noch verstanden wird.
* Wird eine einzelne Datei von unzähligen Nutzern heruntergeladen, lohnt sich ein langsamer, aber sehr leistungsfähiger Kompressions-Algorithmus. Die reduzierte Bandbreite bei der Übertragung macht den Zeitaufwand der Kompression leicht wett.
* Bei der [[Datensicherung]] und der [[Archivierung]] von Daten muss ein Algorithmus verwendet werden, der gegebenenfalls auch in ferner Zukunft verwendet wird. In diesem Fall kommen nur verbreitete, bewährte Algorithmen in Frage, die mitunter nicht die besten Kompressionsraten aufweisen.
* Auch die Art der Daten ist relevant für die Auswahl der Kompressionsmethode. Zum Beispiel haben die beiden auf [[Unixoides System|unixoiden]] Betriebssystemen gebräuchlichen Kompressions-Programme [[gzip]] und [[bzip2]] die Eigenschaften, dass gzip nur 32.000 Bytes große Blöcke komprimiert, während bzip2 900.000 Bytes Blockgröße aufweist. Redundante Daten werden nur innerhalb dieser Blöcke komprimiert.

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.<ref name="Strutz: Bilddatenkompression.">{{Literatur |Autor=Tilo Strutz |Titel=Bilddatenkompression – Grundlagen, Codierung, Wavelets, JPEG, MPEG, H.264, HEVC |Verlag=[[Springer Vieweg]] |Ort=[[Wiesbaden]] |Datum=2017 |ISBN=978-3-8348-1427-2 |Seiten=421}}</ref>

Das Fachgebiet der Datenkompression überschneidet sich zum Teil mit [[Informationstheorie]] und [[künstliche Intelligenz|künstlicher Intelligenz]], und im Bereich der verlustbehafteten Datenkompression auch mit [[Wahrnehmungspsychologie]] (s. weiter unten). Informationstheorie ist insofern betroffen, weil die Dateigröße 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 [[Künstliches neuronales Netz|künstliche neuronale Netzwerke]] und [[maschinelles Lernen]] verwenden, in Entwicklung.<ref>{{Literatur |Autor=Matthew V. Mahoney |Hrsg=[[Association for the Advancement of Artificial Intelligence|AAAI]] |Titel=Fast Text Compression with Neural Networks |Sammelwerk=Proceedings of the Thirteenth International Florida Artificial Intelligence Research Society Conference |Datum=2000 |ISBN=1-57735-113-4 |Seiten=5}}</ref>

=== Grenzen der Komprimierbarkeit ===
==== Verlustbehaftete Kompression{{Anker|verlustbehaftet}} ====
Verlustbehaftete Kompression ist, wie oben beschrieben, stets möglich – die Schwelle, was als „redundant“ gilt, kann so lange heraufgesetzt werden, bis nur noch 1 Bit übrig bleibt. Die Grenzen sind fließend und werden durch den Anwendungsfall bestimmt: Zum Beispiel könnte "Das Haus ist groß" zu "Das Haus ist gr" komprimiert werden; will der Leser wissen "welche Eigenschaft hat das Haus?", so ist nicht mehr unterscheidbar, ob es "grau", "grün" oder "groß" ist. Will der Leser wissen "wurde etwas über ein Haus gesagt?", so kann das noch immer eindeutig bejaht werden.

Bei verlustbehafteter Bildkompression gehen zunehmend Details verloren/werden unscharf, schließlich „verschwimmt alles“ zu einer Fläche mit einheitlicher Farbe; eine Audio-Aufnahme wird meist dumpfer und undeutlicher, sie würde nach größtmöglicher Kompression bei den meisten Algorithmen nur noch einen einfachen [[Sinuston]] aufweisen.

==== Verlustfreie Kompression{{Anker|verlustfrei}} ====
Bei verlustfreier Kompression gelten sehr viel engere Grenzen, da gewährleistet sein muss, dass die komprimierte Datei wieder in die Originaldatei rücktransformiert werden kann.

Die Kolmogorow-Komplexität befasst sich mit der kleinstmöglichen "Anleitung", die notwendig ist, um aus den komprimierten Daten die Originaldaten wiederherzustellen. So zum Beispiel lässt sich die Zahl "100000000000000000000000000000000000" sehr einfach komprimieren: "Schreibe 1 und dann 35 Nullen", was eine Kompression von 36 auf 29 Zeichen darstellt. Ebenfalls lassen sich beliebig viele Nachkommastellen der Kreiszahl [[Kreiszahl|Pi]] mit ihrer Berechnungsvorschrift komprimieren – wobei der Kompressionsalgorithmus dann erkennen müsste, dass es sich um die Zahl Pi handelt. Zu beachten ist, dass bei komprimierten Dateien der Wiederherstellungs-Algorithmus ebenfalls zur Dateigröße hinzugerechnet werden müsste, da jede komprimierte Datei ohne einen solchen Algorithmus wertlos ist. So ließe sich die obige Zahl auch mit "10^35" oder "1e35" komprimieren, wobei dann der Leser von der Wiederherstellungsmethode, nämlich der [[Potenzschreibweise]], Kenntnis haben muss. Weist eine Zeichenkette aber keinerlei erkennbare Struktur/Besonderheiten auf, dann ist eine Kompression nicht möglich – die Anleitung müsste die unveränderten Originaldaten beinhalten.

Ein weiterer Grund für die Unkomprimierbarkeit mancher Daten ist das sogenannte [[Schubfachprinzip|Taubenschlagprinzip]]: Gibt es weniger Nistplätze für [[Tauben]] als es Tauben im [[Taubenschlag]] gibt, müssen sich zwangsläufig zwei oder mehr Tauben einen Nistplatz teilen. Auf einem n bit großen Speicherplatz kann man eine von 2n möglichen Informationen abspeichern, und auf einem Speicherplatz, der um ein bit kleiner ist, kann man folglich nur eine von halb so viel möglichen Informationen speichern: 16 bits → 216 = 65536 mögliche Informationen, 15 bits → 215 = 32768 mögliche Informationen. Unter der Annahme, man könne jede mögliche Datei um ein bit verkleinern, würde dies nach dem Taubenschlagprinzip bedeuten, dass jeder Speicherplatz gleichzeitig zwei verschiedene komprimierte Dateien enthalten müsste. Da aber in der verlustfreien Kompression eine umkehrbar eindeutige Zuordnung zwischen komprimierter und unkomprimierter Datei bestehen muss, verbietet sich dies.

Gälte das Taubenschlagprinzip nicht, und gäbe es einen Algorithmus, der jede beliebige Datei um mindestens ein Bit komprimieren kann, könnte dieser rekursiv auf die jeweils komprimierte Datei angewendet werden – jede beliebige Information ließe sich auf 0 bit reduzieren. In der Praxis lassen sich nur dann bereits komprimierte Daten nochmals komprimieren, wenn im vorherigen Durchlauf ein nicht 100%ig effizienter Algorithmus verwendet wurde, welcher die Redundanz noch nicht vollständig entfernt hat (z. B. eine sehr große Datei voller Nullen wird zwei Mal mit gzip komprimiert).

Aus diesen beiden Tatsachen ergibt sich die Schlussfolgerung, dass rein zufällige Daten (höchstwahrscheinlich) unkomprimierbar sind (da sie zumeist keine Struktur aufweisen), und dass zwar viele, aber nicht alle, Daten komprimiert werden können. Zwei Preisgelder, 100 Dollar für die erfolgreiche Kompression von einer Million zufälliger Ziffern<ref>{{Internetquelle |autor=Mark Nelson |url=https://marknelson.us/posts/2006/06/20/million-digit-challenge.html |titel=The Million Random Digit Challenge Revisited |datum=2006-06-20 |sprache=en |abruf=2018-08-12}}</ref><ref>{{Internetquelle |autor=Mark Nelson |url=http://www.drdobbs.com/architecture-and-design/the-enduring-challenge-of-compressing-ra/240049914 |titel=The Enduring Challenge of Compressing Random Data |hrsg=[[Dr. Dobb’s Journal|DrDobbs.com]] |datum=2012-11-06 |sprache=en |abruf=2018-08-12}}</ref> und 5000 Dollar für die erfolgreiche Kompression einer Datei beliebiger Länge, die vom Preisstifter, Mike Goldman, erzeugt wird,<ref>{{Internetquelle |autor=Patrick Craig |url=https://www.patrickcraig.co.uk/other/compression.php |titel=The $5000 Compression Challenge |sprache=en |abruf=2018-08-12}}</ref> wurden noch nicht ausbezahlt.

== {{Anker|Verlustlose Kompression}} Verlustfreie Kompression ==
Bei der verlustfreien Kompression können die Originaldaten exakt aus den komprimierten Daten wiederhergestellt werden. Dabei geht keinerlei Information verloren. Im Wesentlichen nutzen verlustfreie Kompressionsverfahren die [[Redundanz (Informationstheorie)|Redundanz]] von Daten aus, man spricht auch von '''Redundanzreduktion'''.

Die theoretische Grundlage bildet die [[Informationstheorie]] (verwandt mit der [[Algorithmische Informationstheorie|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 (Informationstheorie)|Entropie]] möglichst gut annähern.

=== Beispiele anhand von Texten ===
Der Vorteil von Texten besteht darin, dass deren kleinste Informationseinheit (das Textzeichen) aller Regel einem Byte entspricht. Im einfachsten Fall kann eine Häufigkeitsanalyse der Bytes erstellt werden, und diese Bytes werden durch die kürzestmögliche Abfolge von Bits ersetzt, wobei ein umkehrbar eindeutiger Zusammenhang bestehen muss. Hier werden Kompressionsmethoden mittels Text-Beispielen erklärt, auch wenn Software zur Datenkompression immer binäre Daten verarbeiten.

Textdateien können in der Regel auf 15–30 % der ursprünglichen Größe komprimiert werden. Bei Programmcode etwa ist der Kompressionsgrad natürlich höher, da der Programmierer zwangsläufig Schlüsselwörter in ganz bestimmten, vorgegebenen Zusammenhängen einsetzen muss. Eine bloße Liste von Worten ohne Zusammenhang wird relativ schlecht komprimiert, während bei natürlichem Text der Kompressionsgrad mittelmäßig ausfällt.

In der Praxis werden verschiedene Methoden nacheinander angewendet. [[gzip]] und [[ZIP-Dateiformat|ZIP]] verwenden zuerst eine Wörterbuchmethode, und danach eine Entropiekodierung. Sehr schnelle Methoden wie [[Lempel-Ziv-Oberhumer]] verwenden lediglich eine Wörterbuch-Kompression. In der komprimierten Datei wird auch eine [[Prüfsumme]] der ursprünglichen Daten abgelegt – um zu gewährleisten, dass bei der Dekompression die originalen Daten wieder hergestellt werden.

==== Wörterbuchmethode ====
Die einfachste Kompression von Text 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"

Für die Zuordnung der Tokens zu den eigentlichen Wörtern muss entweder ein externes Wörterbuch vorhanden sein, oder in der komprimierten Datei ersichtlich/mit enthalten sein.

Der zu komprimierende Text kann aber auch als sein eigenes Wörterbuch dienen. Dafür muss aber eine Referenz eingefügt werden:

Ausgangstext: AUCH EIN KLEINER BEITRAG IST EIN BEITRAG
Kodiertext: AUCH EIN KLEINER BEITRAG IST /2 /4

Hier wurde erkannt, dass die Wörter EIN und BEITRAG zweimal auftauchen, und dadurch angegeben, dass diese mit den Wörtern übereinstimmen, die 2 beziehungsweise 4 Stellen zurückliegen. Bei genauerer Betrachtung könnte dann auch das in KLEINER enthaltene EIN entsprechend kodiert werden.

Da in der Praxis keine Texte mit erkennbaren Wörtern, sondern Abfolgen von Bytes komprimiert werden müssen, muss eine eindeutige Referenz eingefügt werden

Kodiertext 1: AUCH EIN KLEINER BEITRAG IST[24,5]BEITRAG
Kodiertext 1: AUCH EIN KLEINER BEITRAG IST[24,5][11,7]

Im ersten Durchlauf wurde die Wiederholung des "EIN" erkannt, und durch eine Referenz ersetzt, mit Angabe der Länge: " EIN " (mit Leerzeichen) kommt 24 Bytes vorher schon einmal vor, und der ersetzte Text ist 5 Bytes lang. Im zweiten Durchlauf wurde "BEITRAG" erkannt und auf die gleiche Weise ersetzt.

==== Run length encoding (RLE) ====
Bei der RLE, deutsch [[Lauflängenkodierung]], werden identische Textbestandteile, die hintereinander stehen, nur 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]], bekannt von [[bzip2]], 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 ====
Verfahren der so genannten [[Entropiekodierung]]:
* [[Huffman-Code]] (in modifizierter Form zum Beispiel für die Fax-Übertragung).
* [[Arithmetische Kodierung]]<ref name="Strutz: Bilddatenkompression." />

Der bekannte [[Morsecode|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 = '''_ _ . _''').

Als Beispiel ein Ausgangstext von 66 Zeichen Länge (Datenmenge 462 Bit bei 7 Bit pro Zeichen, siehe [[ASCII]]):
WENN HINTER FLIEGEN FLIEGEN FLIEGEN, FLIEGEN FLIEGEN FLIEGEN NACH.
Eine sehr einfache, aber nicht sehr effiziente Entropiekodierung besteht darin, alle Teile einer Nachricht (siehe Tabelle; „_“ steht für das Leerzeichen) nach ihrer Häufigkeit zu sortieren, und mittels binären Zahlen zu nummerieren:
{| class="wikitable"
|-
! Textteil… !! …wird ersetzt durch…
|-
| _FLIEGEN || 1
|-
| WENN_ || 10
|-
| _NACH. || 11
|-
| HINTER || 100
|-
| , || 101
|}
Der mit diesem Wörterbuch komprimierte Text lautet
10 100 1 1 1 101 1 1 1 11
und benötigt in binärer Kodierung 50 Bit, denn das Ergebnis enthält drei verschiedene Zeichen (0, 1 und das Trennzeichen „ “), also 2 Bit pro Zeichen. Die Trennzeichen sind hier notwendig, da dieser Code nicht [[präfixfrei]] ist. Der präfixfreie Huffman-Code, also folgendes Wörterbuch,
{| class="wikitable"
|-
! Textteil… !! …wird ersetzt durch…
|-
| _FLIEGEN || 1
|-
| WENN_ || 011
|-
| _NACH. || 010
|-
| HINTER || 001
|-
| , || 000
|}
ist effizienter, denn es führt direkt zu einem binären Ergebnis von 18 Bit Länge:
011001111000111010

In beiden Fällen muss aber auch das Wörterbuch in der komprimierten Datei abgespeichert werden – sonst lässt sich der Ausgangstext nicht rekonstruieren.

Ähnlich wie die oben erwähnte Burrows-Wheeler-Transformation bereitet [[Move to front|Move-to-Front]] die Daten vor, damit sie besser mit einem Entropiekodierer komprimiert werden können.

==== Markow-Ketten ====
Einen Schritt weiter geht die Verwendung von Techniken, die den [[Markow-Kette]]n ähneln. Diese werden beispielsweise in der [[Lempel-Ziv-Markow-Algorithmus|LZMA]]-Methode eingesetzt. Dabei wird berechnet, wie hoch die Wahrscheinlichkeit ist, dass ein bestimmter Text als Nächstes erscheint – abhängig von einer definierten Anzahl aktueller Zeichen.

In diesem Beispiel (ohne Komma) tastet der Algorithmus alle Buchstaben ab und berechnet die Häufigkeiten der darauf folgenden Textbestandteile. Diese Häufigkeiten werden dann für die oben beschriebene Entropiekodierung eingesetzt. Bei „N“ würde Folgendes geschehen:

WE'''NN''' HI'''N'''TER FLIEGE'''N''' FLIEGE'''N''' FLIEGE'''N''' FLIEGE'''N''' FLIEGE'''N''' FLIEGE'''N''' '''N'''ACH.
Es folgt auf ein „N“ sehr häufig der Text „ FLIEGE“, während das Leerzeichen „ “ zwei Mal und die restlichen Fälle nur je einmal vorkommen. Das Resultat ist:
WEN'''N1'''HINTER FLIEGE'''N0N0N0N0N0N1'''NACH.
Dabei ist <code>N0</code> die Entropiekodierung von „N FLIEGE“, und „N1“ bedeutet „N “. Das „N“ ohne Leerzeichen und die anderen Fälle (z. B. „NACH“) werden ignoriert, da eine Substitution den Text noch länger machen würde, oder weil es sinnlos ist, den ohnehin nur einmal vorkommenden Textteil in die Entropiekodierung auszulagern.

Markow-Ketten eignen sich sehr gut für die Kompression von natürlichem Text. Etwa ist die Wahrscheinlichkeit, dass auf die Buchstaben „Ka“ die Zeichen „nada“, „tze“, [[Kastration|„stration“]], „sse“ oder [[Kantate|„ntate“]] folgen, je nach Text unterschiedlich hoch. Bei der Erstellung der Markow-Kette wird dies berücksichtigt; die jeweils häufigeren Fortsetzungen von „Ka“ erhalten durch die Entropiekodierung den kürzeren Platzhalter. Erwähnt der Text „Katze“ sehr häufig, „Kasse“ gelegentlich und „Kastration“ selten, würde ersteres wohl mit <code>Ka0</code> ersetzt, und die beiden letzten mit <code>Ka10</code> und <code>Ka11</code>. Ebenso können Markow-Ketten grammatikalische Strukturen abbilden: Auf "Ich" folgt sehr oft ein Verb in der [[Person (Grammatik)|1. Person]]; nach "ist" steht oft ein Adjektiv. [[Prediction by Partial Matching]] und Context Mixing führen diese Idee noch weiter.

== {{Anker|Irrelevanzreduktion}}Verlustbehaftete Kompression ==
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 Frequenzmuster entfernt, die der Mensch schlecht oder gar nicht hört.

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 ===
[[Datei:Jpegartefakt jpegartefact.jpg|mini|Bei stark komprimierten Bildern im JPEG-Format zeichnen sich 8 × 8 Pixel große Quadrate als [[Artefakt (Technik)|Kompressionsartefakte]] ab. Oben Originalgröße, unten Ausschnittsvergrößerung]]
[[Datei:Comparison of JPEG and PNG.png|mini|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 [[Wahrnehmung]]seigenschaften des Menschen. Die Kompression durch [[Algorithmus|Algorithmen]] bedient sich dabei typischerweise der Wandlung von Signalverläufen von Abtastsignalen in eine Frequenzdarstellung.

In der [[Akustik|akustischen]] Wahrnehmung des Menschen werden [[Frequenz]]en 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 digitalisierter, akustischer Ereignisse (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 [[Optik|optischen]] Wahrnehmung des Menschen werden [[Farbe]]n 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 [[Tiefpass]]filterung zur Farbreduktion, zum Beispiel durch den auf [[Diskrete Kosinustransformation|DCT-Transformation]] basierenden [[JPEG]]-Algorithmus oder den neueren auf [[Wavelet-Transformation]] basierenden [[JPEG2000]]-Algorithmus, lässt sich die Datenmenge meist auf 10 % oder weniger der ursprünglichen Datenmenge reduzieren, ohne deutliche Qualitätsverringerungen.

Bewegtbilder (Filme) bestehen aus aufeinanderfolgenden Einzelbildern. Erster Ansatz war, jedes Bild einzeln gemäß JPeg-Algorithmus zu komprimieren. Das resultierende Format ist [[Motion JPEG]] (entspricht [[MPEG-1]], wenn dieses nur I-Frames enthält). Die heutzutage sehr viel höheren Kompressionsraten sind nur erreichbar, wenn man bei der Kodierung die Ähnlichkeit von benachbarten Bildern (englisch 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. Zusätzlich wird aus den Änderungen vom vorherigen zum aktuellen Bild gefolgert, in welche Richtung sich Bildinhalte wie weit verschoben haben; für den entsprechenden Bereich wird dann nur ein Verschiebungsvektor gespeichert.

==== Kompressionsartefakte ====
{{Hauptartikel|Kompressionsartefakt}}

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

== Anwendung in der Nachrichtentechnik ==
[[Datei:Fehlerkorrektur1.png|mini|Nutzung von [[Quellenkodierung|Quellen-]], [[Kanalcodierung|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''.<ref name="QuLKomm. Prof. Brunthaler" /><ref name="QC ETH Zürich" /> Die Quellenkodierung wird dabei häufig zusammen mit [[Kanalkodierung]] und [[Leitungscode|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 Übertragungs- bzw. Speicherfehler im Rahmen der Datenübertragung erkennen und korrigieren zu können. Die Leitungskodierung hingegen nimmt eine [[Frequenzspektrum|spektrale]] Anpassung des Signals an die Anforderungen des Übertragungskanals vor.

== Zeittafel der Kompressions-Algorithmen ==

Die jahrhundertealte [[Stenografie]] kann als Datenkompression angesehen werden, welche der Handschrift eine möglichst hohe Datenrate verleiht.

1833–1865 Entwicklung des Morse-Codes, welcher häufige Buchstaben in kurze Zeichen übersetzt und seltene Buchstaben in längere, was die Idee der Entropiekodierung vorzeichnet

1883 [[David Forsyth (Schachspieler)|David Forsyth]], Schachspieler und Journalist, publiziert eine Methode, mit welcher auf platzsparende Weise die Position von [[Schach]]-Figuren mit Lauflängenkodierung festgehalten wird → [[Forsyth-Edwards-Notation]]

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 [[Arithmetisches Kodieren|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]] ([[bzip2]])

1995 [[zlib]], freie Standardbibliothek für [[Deflate]]

1996 [[Lempel-Ziv-Oberhumer]]-Algorithmus (LZO), sehr schnelle Kompression

1997 [[Sequitur]]

1998 [[Lempel-Ziv-Markow-Algorithmus]] (LZMA)

2006 [[Hutter-Preis]] für beste Datenkompression

2009 [[PAQ]], höchste Kompressionsraten auf Kosten sehr langer Laufzeit; Verwendung eines neuronalen Netzwerks (heute [[ZPAQ]])

2011 [[Snappy (Datenkompressionssoftware)|Snappy]], schneller Kodierer von Google

2011 [[LZ4]], sehr schneller Kodierer

2013 [[zopfli]], verbesserter Deflate-Kodierer

2015 [[Brotli]], starke Kompression

== Bekannte Methoden zur Quellcodierung ==
{| class="wikitable"
|-
! align="center" width="150"| verlustbehaftet
! align="center" width="100"| beides möglich
! align="center" width="100"| verlustfrei
|-
| class="hintergrundfarbe6" | [[Advanced Audio Coding|AAC]] ([[Moving Picture Experts Group|MPEG]]) || ||
|-
| || || class="hintergrundfarbe6" | [[Aiff]]
|-
| || || class="hintergrundfarbe6" | [[Audio Lossless Coding|ALS]] ([[Moving Picture Experts Group|MPEG]])
|-
| || || class="hintergrundfarbe6" | [[Apple Lossless]]
|-
| || class="hintergrundfarbe6" | [[ATRAC]] ||
|-
| class="hintergrundfarbe8" | [[DjVu]] || ||
|-
| class="hintergrundfarbe6" | [[Dolby Digital]] || ||
|-
| || class="hintergrundfarbe6" | [[DTS]] ||
|-
| || || class="hintergrundfarbe6" | [[FLAC]]
|-
| || || class="hintergrundfarbe6" | [[Monkey’s Audio]]
|-
| class="hintergrundfarbe6" | [[G.729]] || ||
|-
| || || class="hintergrundfarbe8" | [[Graphics Interchange Format|GIF]]
|-
| || || class="hintergrundfarbe9" | [[HuffYUV]]
|-
| || class="hintergrundfarbe8" | [[JPEG]] ||
|-
| || class="hintergrundfarbe8" | [[JPEG 2000]] ||
|-
| || || class="hintergrundfarbe6" | [[Lossless Audio|LA]]
|-
| class="hintergrundfarbe9" | [[MJPEG]] || ||
|-
| class="hintergrundfarbe6" | [[MPEG-1 Audio Layer 2|MP2]] ([[Moving Picture Experts Group|MPEG]]) || ||
|-
| class="hintergrundfarbe6" | [[MP3]] ([[Moving Picture Experts Group|MPEG]]) || ||
|-
| class="hintergrundfarbe9" | [[MPEG-1]] || ||
|-
| class="hintergrundfarbe9" | [[MPEG-2]] || ||
|-
| class="hintergrundfarbe9" | [[MPEG-4]] (siehe [[H.264]], [[Xvid]], [[DivX]]) || ||
|-
| class="hintergrundfarbe6" | [[Musepack]] || ||
|-
| || class="hintergrundfarbe8" | [[Progressive Graphics File|PGF]] ||
|-
| || || class="hintergrundfarbe8" | [[Portable Network Graphics|PNG]]
|-
| || || class="hintergrundfarbe8" | [[Targa Image File|TGA]]
|-
| || class="hintergrundfarbe8" | [[Tagged Image File Format|TIFF]] ||
|-
| class="hintergrundfarbe6" | [[Vorbis]] ([[Ogg]]) || ||
|-
| || class="hintergrundfarbe6" | [[WavPack]] ||
|-
| || class="hintergrundfarbe8" | [[WebP]] ||
|-
| || class="hintergrundfarbe6" | [[Windows Media Audio|WMA]] ||

|-
| class="hintergrundfarbe9" | [[Windows Media Video|WMV]] || ||
|}

{| class="wikitable"
|-
! class="hintergrundfarbe8" width="10"| || Bilder
! class="hintergrundfarbe6" width="10"| || Audio
! class="hintergrundfarbe9" width="10"| || Video
|}

=== Datenübertragung ===
* MNP-1 bis MNP-10 (Microcom Networking Protocol)
:: Fehlerkorrektur- und Datenkompressionsprotokolle der Firma Microcom Inc. für [[Modem]]s, ein jahrelanger Standard. Wurde verbessert durch:
* V.42bis – Datenkompressionsprotokoll der [[Internationale Fernmeldeunion|ITU-T]]

== Biologie ==
[[Sinneswahrnehmung]]en 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. Ebenso kann das menschliche Auge Helligkeitsunterschiede wesentlich besser wahrnehmen als Unterschiede im Farbton – diesen Umstand nutzt das in JPEG-Bildern verwendete [[YCbCr-Farbmodell]] und speichert den Farbwert mit einer wesentlich geringeren Präzision ab.

Auch beim [[Hören]] werden schwache oder fehlende Signale unbewussterweise ersetzt, was sich Algorithmen wie MPEG ([[MP3]]) oder [[Vorbis]] zunutze machen.

== Siehe auch ==
* [[Kanalkodierung]]
* [[Kompression ausführbarer Programmdateien]]
* [[Canterbury Corpus]]
* [[Liste von Datenkompressionsprogrammen]]
* [[Liste von Dateinamenserweiterungen]]
* [[Green IT]]

== Weblinks ==
{{Wikibooks|Datenkompression|Buch zu Datenkompression}}
{{Wiktionary}}
* [http://www.squeezechart.com/ Vergleich der Kompressionsleistung von über 250 Packprogrammen] (englisch)
* [http://www.lossless-audio.com/ LA – Verlustfreies Audioformat mit den angeblich höchsten Kompressionsraten] (englisch)
* [http://navatrump.de/Technology/Datacompression/compression.html Data Compression – Systematisation by T. Strutz] (englisch)
* [http://www.faqs.org/faqs/compression-faq/ Data compression FAQ] (englisch)
* [http://www.ics.uci.edu/~dan/pubs/DataCompression.html Lelewer, Debra, A.; Hirschberg, Daniel, S.: „Data Compression“; ACM Computing Surveys, 19, 1987, S. 261–297.] Übersichtsartikel (englisch)
* [http://www.compression.ca/act/ Liste mit Kompressionsvergleichen] (englisch)

== Einzelnachweise ==
<references />

[[Kategorie:Datenkompression| ]]

Demo Wiki - Benutzerbeiträge [de]

Datenkompression