Datenkompression: Unterschied zwischen den Versionen

Version vom 30. Januar 2025, 11:39 Uhr

Datenkompression - Datenkomprimierung

Beschreibung

Die Datenkompression ist ein Vorgang, bei dem die Menge digitaler Daten verdichtet oder reduziert wird

Dadurch sinkt der Speicherbedarf, und die Übertragungszeit verkürzt sich

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 – 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

verlustfreier Kompression	Man spricht von 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
verlustbehafteten Kompression	Bei der 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 Algorithmen versuchen, möglichst nur „unwichtige“ Informationen wegzulassen Solche Verfahren werden häufig zur Bild- oder Videokompression und Audiodatenkompression eingesetzt

Komprimierbarkeit

Grenzen der Komprimierbarkeit

Verlustbehaftete Kompression

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

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 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 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ⁿ 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¹⁶ = 65536 mögliche Informationen, 15 bits → 2¹⁵ = 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

Anhang

Siehe auch

Links

Weblinks

https://de.wikipedia.org/wiki/Datenkompression

@@ Zeile 17: / Zeile 17: @@
 * 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.&nbsp;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
 == Komprimierbarkeit ==