|
|
| Zeile 17: |
Zeile 17: |
| * 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 |
| |} | | |} |
|
| |
| == 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 [[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
| |
|
| |
|
| |
| <noinclude>
| |
|
| |
|
| == Anhang == | | == Anhang == |