Datenkompression/Komprimierbarkeit

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