der Chaosforschung auf der Spur...

[Sven Rautenberg]

Moin!

Aber mir ist bei dieser ganzen Sache ein ganz anderer Gedanke gekommen: je stärker der String komprimiert wird, desto zufälliger - "chaotischer" - wird die Zeichenverteilung. Sonst - wenn es noch Muster gäbe - könnte man ja weiterkomprimieren. Aber dieser komprimierte Chaos-String enthält ja troztdem die gleiche Information, wie der entpackte, sonst ließe er sich ja nicht eindeutig entpacken. Also schlußfolgere ich: je komplexer oder chaotischer ein Muster, desto höher ist die darin enthaltene Informationsdichte. Ist das der Inhalt der "Chaosforschung"?

Nein, die Chaosforschung hat dann doch ein etwas anderes Themengebiet.

Aber die Informationstheorie behandelt solche Dinge, wie z.B. die Zunahme der zufällig wirkenden Muster bei Komprimierungsalgorithmen.

In Kurzform: Jede Abfolge von Informationen (z.B. Textstrings) bestehen aus unterschiedlichen "Symbolen" eines "Alphabets". Bei Textstrings sind die Symbole die einzelnen Zeichen, und das Alphabet ist die gesamte Zeichentabelle. Jedes Symbol wird repräsentiert durch ein bestimmtes Bitmuster.

Einfaches Konstrukt: Die Symbole sind alle Zeichen der ASCII-Tabelle, jedes Zeichen ist 8 Bit lang. Wenn jetzt aber im String nur Kleinbuchstaben vorkommen, oder anders gesagt: Nur eine definiert kleine Untermenge aller 8-Bit-Symbole, dann ist ja die Definition der ungenutzten Symbole reine Platzverschwendung.

Die Informationstheorie definiert nun zwei Begriffe: Entropie und Redundanz, die beide direkt miteinander zusammenhängen. Die Entropie ist ein Maß für die Zufälligkeit einer Information, die Redundanz das Gegenteil. Kurzes Rechenbeispiel: Wenn ich 8 Bit für die Codierung von Kleinbuchstaben nutze, in Wirklichkeit sind aber nur 5 Bit notwendig (Bytes 0 bis 31), dann habe ich in dem 8-Bit-Datenstrom eine Entropie von 5 Bit, und eine Redundanz von 3 Bit. Eine verlustfreie Komprimierung kann im Idealfall die gesamte Redundanz der Information "wegrechnen". Das Ergebnis ist, dass die Zufälligkeit des Datenstroms steigt, denn statt 5 von 8 Bit Entropie sind es jetzt 5 von 5 Bit (also 100%).

In Wirklichkeit ist es noch komplexer: Ein deutscher Text in Kleinbuchstaben hat ja nicht 32 verschiedene Buchstaben, sondern nur 26. Außerdem kommen bestimmte Buchstaben wie E, R, N, S, T, L viel häufiger vor, als andere. Auf den Buchstaben Q folgt beispielsweise auch extrem häufig ein U. All diese Abweichungen von kompletter Zufälligkeit senken die Entropie und heben die Redundanz. Dabei kommt es (siehe Berechnungsvorschrift) rechnerisch zu Kommazahlen für Redundanz und Entropie. Vielleicht hat der Kleinbuchstabentext also keine Entropie von 5 Bit, sondern eventuell nur 4,1 Bit. Man könnte also bis zu 3,9 Bit Redundanz herauskomprimieren.

Das funktioniert aber nur, wenn das Kompressionsverfahren exakt auf den konkreten Text abgestimmt ist. Allgemeine Verfahren nutzen Ansätze, die meistens gute Ergebnisse bringen, aber eben nicht überall ideale.

Als Extrembeispiel: Angenommen, der Text bestünde nur aus den zwei Worten "ja" und "nein" - dann wäre die Entropie des Textes vermutlich 1 Bit - für jedes "nein" benutzt man also lieber ein Nullbit, für jedes "ja" ein Einsbit. Die Redundanz, die der Text bei 8 Bit Zeichenbreite hätte, wären 7 Bit.

Wobei auch das nicht stimmt, denn die Folge von "ja" und "nein", als Bitfolge betrachtet, ist vermutlich auch nicht komplett zufällig, sondern hat gewisse Wahrscheinlichkeiten, und damit auch weiter komprimierbare Redundanz. :)

- Sven Rautenberg