|
|
| (19 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) |
| Zeile 3: |
Zeile 3: |
| == Beschreibung == | | == Beschreibung == |
| Die '''Datenkompression''' ist ein Vorgang, bei dem die [[Datenmenge|Menge]] [[Digitalisierung|digitaler]] Daten verdichtet oder ''reduziert'' wird | | Die '''Datenkompression''' ist ein Vorgang, bei dem die [[Datenmenge|Menge]] [[Digitalisierung|digitaler]] Daten verdichtet oder ''reduziert'' wird |
| | | * Dadurch sinkt der [[Speicherbedarf]], und die [[Datenübertragung|Übertragungszeit]] verkürzt sich |
| * (wohl [[Lehnübersetzung|lehnübersetzt]] und [[Eindeutschung|eingedeutscht]] aus dem [[Englische Sprache|englischen]] ''{{lang|en|data compression}}'') | |
| * auch (weiter eingedeutscht) '''Datenkomprimierung''' genannt
| |
| | |
| Dadurch sinkt der [[Speicherbedarf]], und die [[Datenübertragung|Übertragungszeit]] verkürzt sich | |
| | |
| <!-- Nachrichtentechnik – Nachricht vs. Daten bzw. Informationen in der Informatik -->
| |
| In der [[Nachrichtentechnik]] wird die Komprimierung von Nachrichten aus einer Quelle durch einen Sender als '''Quellenkodierung''' bezeichnet
| |
| | |
| <!-- Keine Begriffe, wie Entropie, Information, Informationsgehalt ohne jede Erklärung
| |
| * Nur Kodieren und Dekodieren
| |
| Sorry, "Information" muss sein, sonst ist es schlicht falsch. -->
| |
|
| |
|
| Grundsätzlich wird bei der Datenkompression versucht, redundante Informationen zu entfernen | | 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 | | * 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'' | | * Diesen Vorgang übernimmt ein Kodierer und man bezeichnet den Vorgang als ''Kompression'' oder ''Komprimierung'' |
| * Die Umkehrung bezeichnet man als ''Dekompression'' oder ''Dekomprimierung'' | | * 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 | | {| class="wikitable options big" |
| | | [[#verlustfrei|verlustfreier Kompression]] || 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 | | * 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 | | | [[#verlustbehaftet|verlustbehafteten Kompression]] ||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 | | * 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
| |
|
| |
| 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
| |
|
| |
| === 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 2<sup>n</sup> 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 → 2<sup>16</sup> = 65536 mögliche Informationen, 15 bits → 2<sup>15</sup> = 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 und 5000 Dollar für die erfolgreiche Kompression einer Datei beliebiger Länge, die vom Preisstifter, Mike Goldman, erzeugt wird, wurden noch nicht ausbezahlt
| |
|
| |
| == Verlustfrei ==
| |
| [[Datenkompression/Verlustfrei]]
| |
|
| |
| == Verlustbehaft ==
| |
| [[Datenkompression/Verlustbehaft]]
| |
|
| |
| == Nachrichtentechnik ==
| |
| ; 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''
| |
| * 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
| |
|
| |
| == Methoden ==
| |
| 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]]<!-- Kein Videoformat!!!! -->
| |
| |-
| |
| | || class="hintergrundfarbe8" | [[Tagged Image File Format|TIFF]]<!-- Ein Dateiformat, das flags für jpg und andere Kompressionsverfahren besitzt, aber doch kein Kompressionsverfahren!!!! --> ||
| |
| |-
| |
| | 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]]
| |
|
| |
|
| <noinclude> | | <noinclude> |
|
| |
| == Anhang == | | == Anhang == |
| === Siehe auch === | | === Siehe auch === |
| * [[Kanalkodierung]]
| | {{Special:PrefixIndex/{{BASEPAGENAME}}/}} |
| * [[Canterbury Corpus]]
| |
| * [[Liste von Datenkompressionsprogrammen]]
| |
| * [[Liste von Dateinamenserweiterungen]]
| |
| * [[Green IT]]
| |
| | |
| {{Special:PrefixIndex/{{BASEPAGENAME}}}} | |
|
| |
|
| ==== Links ====
| | === Links === |
| ===== Weblinks =====
| | ==== Weblinks ==== |
| {{Wikibooks|Datenkompression|Buch zu Datenkompression}}
| | # https://de.wikipedia.org/wiki/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)
| |
|
| |
|
| [[Kategorie:Linux/Datenkompression]] | | [[Kategorie:Linux/Datenkompression]] |