par Johan1951 » Ven 15 Oct 2010, 16:45
From: Sozialist
EDIT: kB steht im folgenden für 1000 Byte, nicht für 1024 Byte.
Bei verlustloser Datenkompression muss ich jedes Objekt immer noch einwandfrei identifizieren können. Die absolute Untergrenze für verlustlose Kompression einer Klasse von Objekten, die über n mögliche Konfigurationen verfügt, wäre also Schlüssel von 0 (mit einem Bit Länge) bis der Binärrepräsentation von n-1 zu haben, die Rekonstruktion der Daten aus den Schlüsseln wäre dann noch eine andere Frage. Dafür ist natürlich ein fixes Format notwendig. Nehmen wir als Beispiel die Kompression von Bitmaps mit der Dimensionierung 100x100 Pixel bei einer Farbtiefe von 8 Bit. Würde ich für diese limitierte Objektklasse das effizientmöglichste Speicherformat verwenden, würde ich die Information in 10000 Farbcodes von einem Byte speichern, der 70. Code z.B. für den Pixel (1,70), der 3030. Code für den Pixel (30,30) und so fort. Dann hätte ich 256 hoch 10000 mögliche Konfigurationen, die benötigte Länge zur Darstellung dieser Zahl entspricht genau der Größe des oben spezifizierten Formats nämlich 100 x 100 x 1 Byte = 10 kByte.
Der absolute Idealfall wäre also, dass ich jeder Zahl zwischen 0 und 256^10000 -1 genau eines der möglichen Bilder zuordnen kann. Das geht schon, wenn ich die normale oben vereinbarte Repräsentation nehme und als lange Zahl interpretiere, bei der ich alle führenden Nullen streiche, die dann bei der Interpretation so wieder vorne angefügt werden, dass die Datei wieder exakt 10 kB lang ist. Dabei muss man sich aber im Klaren sein, dass man in nur 50% aller möglichen Konfigurationen überhaupt mindestens ein Bit einspart, will man gar 2 Byte einsparen, kommen gar nur noch 0,001526% der möglichen Konfigurationen in Frage. Um einen signifikanten Teil an Einsparungen zu gewinnen (z.B. 1-2 kB von den 10 kB) müssen also alle relevanten Bilder zu einer astronomisch winzigen Teilmenge der denkbaren Bildkonfigurationen gehören.
Der interessante Aspekt ist aber, dass wir die Untergrenze der eindeutigen Identifikation jeder möglichen Konfiguration mit einem Schlüssel nicht unterschreiten können. Bei der Hälfte können wir ein Bit einsparen, bei einem Viertel ein weiteres Bit, bei einem Achtel ein weiteres Bit etc. Insgesamt kommen wir darauf, dass die mittlere Größe aller erdenklichen Bildkonfigurationen unseres 10kB-Bitmapformats auch bei der besten verlustfreien Kompression nicht 79999 Bit unterschreiten kann (sprich, ein mittlerer Gewinn von maximal einem Bit). Der Trick bei verlustfreier Kompression ist es, dass die immense Vielzahl der möglichen Konfigurationen für unsere Zwecke sinnloser Datenmüll (im Falle unseres Bitmapbeispiels Farbrauschabfall) ist und wir die für uns interessanten Konfigurationen also möglichst in Richtung der ersten Positionen der Schlüsselliste schieben müssen.
4 kB repräsentiert zwar sicherlich eine immense Zahl, namentlich etwa 9,117 x 10 hoch 9632, aber die Zahl der theoretisch denkbaren Spielfilme bis zwei Stunden Länge ist mit 100% Sicherheit um astronomische Größenordnungen größer.
Da hilft auch keine Gödelisierung oder was auch immer mehr weiter. Denn die Identifkationsuntergrenze zu unterschreiten, würde heißen eine Abbildung von N nach N (Bereich der natürlichen Zahlen) f(a) := b zu finden, wobei b,max < a,max ist, aber die Funktion immer noch eineindeutig bleibt. Dies würde in der Tat alle bisherige Mathematik und Logik in der Menschheitsgeschichte auf den Kopf stellen.
EDIT: Bei dem vorhergehenden Stück Mathematik bin ich davon ausgegangen, dass man kein größeres a oder b als Schlüssel wählt, solange noch eine kleinere Zahl im Definitions- bzw. Wertebereich frei ist, sodass a,max gleich der Anzahl der verschiedenen tatsächlichen Argumente der Funktion ist und b,max gleich der Anzahl der verschiedenen Werte im Wertebereich (im Verständnis der Zahlenmenge N ohne die 0).