Wege zur Informationstheorie 2 - Lauflängen optim. Mystery Cache

Generelles

Hier soll eine Reihe von Caches entstehen, die sich mit dem kodieren von Informationen beschäftigt - warum nicht auch mal etwas Wissen in einem Mysterie vermitteln. Diese Reihe baut aufeinander auf und daher wird sie auch Schritt für Schritt schwieriger. Alle Abschnitte mit Erinnerung am Anfang sind exakt aus dem vorherigen Cache übernommen. Wer also alles der Reihe nach löst, braucht sie noch nicht nochmal zu lesen, wenn alles behalten wurde.
Während man am Anfang noch alles mit Stift und Papier berechnen kann, wird später der Einsatz von Programmierkenntnissen doch sehr zu empfehlen sein.

Dabei sollt ihr, wie gesagt, auch noch was praktisches Lernen: Wer sich schon immer mal gefragt hat, wieso eine Datei, wenn man sie zippt plötzlich viel kleiner ist gegenüber der ursprünglichen, der wird hier einige Antworten finden. Wir behandeln hier also Kompressionsverfahren.

Prinzipiell unterscheidet man zwischen verlustfreier und verlustbehafteter Kompressionsverfahren. Verlustbehaftete Kompression findet z.B. bei der Bilddatenkomprimierung statt: minimale Farbunterschiede, die für das Auge kaum wahrnehmbar sind, werden nicht mehr dargestellt. Oder bei Audiodateien: bei mp3 werden Töne, die der Mensch nicht oder nur sehr schwer hören kann, einfach weggelassen.

Diese Serie von Caches beschäftigt sich ausschließlich mit verlustfreier Kompression. Diese kommt beispielsweise bei der Verarbeitung von Texten vor, da hier keine Informationen weggelassen werden können sondern der originale Text wiederhergestellt werden muss.

Die Caches der Serie, die bislang veröffentlicht wurden, sind:

• Wege zur Informationstheorie 1 - Lauflängen
• Wege zur Informationstheorie 2 - Lauflängen optim.
• Wege zur Informationstheorie 3 - Shannon-Fano

Erinnerung Grundlagen

Wie jedes Kind weiß, kann ein Computer nur 0 und 1 verarbeiten, eine solche Einheit nennt man 1 Bit. Wenn man Buchstaben darstellen will, muss man diese in eine Folge von 0 und 1 "übersetzen". Eine Tabelle für eine mögliche Übersetzung findet ihr hier (für Experten und solche, die es werden wollen: hier wird latin-1 verwendet, ich will hier nicht auf Details wie Zeichenkodierungen sowie Umrechnung in Binärform aufhalten. Daher: für diejenigen, denen so etwas fremd ist, der kann einfach die Tabelle benutzen.)

Wie aus obiger Tabelle ersichtlich wird jedes Zeichen aus einer Folge von 8 Stellen mit jeweils dem Wert von 0 oder 1 definiert (diese Stellen nennt man Bits). Mit 8 Bits, die man auch als 1 Byte bezeichnet, kann man 256 verschiedene Kombinationen von 0 und 1 erzeugen und somit 256 verschiedene Zeichen darstellen. In unserer obigen Tabelle sind aber nur 30 Zeichen enthalten, man braucht also gar nicht die ganze Bandbreite an Möglichkeiten. Dies eröffnet verschiedene Möglichkeiten die Daten zu komprimieren.

Erinnerung Teil 1 - Lauflängenkodierung

Die Lauflängenkodierung ist ein recht simples Verfahren und funktioniert, abhängig von den Eingangsdaten mal mehr mal weniger gut. Man zählt nun einfach die Anzahl der aufeinander folgenden Nullen und anschließend der aufeinander folgenden Einsen und speichert diese ab. So wäre 1 1 5 1 zu übersetzen in 01000001, was einem "A" entspricht.

Das ist dann eigentlich auch schon alles.

Teil 2 - Lauflängenkodierung optimiert

Wie lässt sich die Optimierung nun noch verbessern, schließlich haben wir im Teil 1 festgestellt, dass die kodierte Zeichenkette sogar länger (im Sinne benötigt mehr Speicher) ist, also die originalen Daten. Nun es fällt auf, dass fast alle Zeichen (bis auf 4 Ausnahmen, die wir nun kurz ignorieren wollen) mit der Folge 010 beginnen. Das ist für Lauflängenkodierung natürlich der ungünstigste Fall, denn für die erste Null benötigt man eine 1, für die folgende Eins auch eine 1 und dann, je nach Anzahl weiterer Nullen, mindestens auch eine 1 oder eine höhere Zahl. Sprich für die ersten 3 Bits 010 benötigt man mind. 3 Zahlen, die wir mit 3 Bits pro Zahl kodiert haben. Also um diese 3 Bits zu kodieren, benötigen wir 9 Bits, was das ungünstige Ergebnis verdeutlicht. Und das schlimmste dabei ist, das die Folge 010 stets am Anfang eines neuen Buchstaben steht und also immer gleich ist, also für uns gar keine zusätzliche Information beinhaltet.  Was liegt also näher, für die gewünschten Zeichen eine andere Tabelle zu verwenden, indem die störende 010 Kombination am Anfang nicht mehr auftritt. Wir ersetzen dazu einfach das 2. Bit jedes Zeichen durch Null, wo nötig, auch bei unseren vier Ausnahmen und erhalten so die Tabelle

Das war es schon - fast! Das Problem dabei ist, dass wir nun mehr als 7 Nullen in Folge haben können, somit genügen uns die 3 Bit beim kodieren nicht. Wir behelfen uns: folgt nach 7 Nullen keine Eins, sondern weitere Nullen, so schreiben wir nach der 7 eine 0 und dann weiter mit der Anzahl der folgenden Nullen. Beispiel:

000000000000 wird zu 705

Der Cache befindet sich nun bei:

4331701112512151113121317023611131111143317012114113511141212170516241611141134122511162416122217031114
1214341222170112251116241612221702421703111427231703211236362311353411111426241703211236362317011224121
5111616111431

Noch eine letzte Anmerkung für die Theoretiker unter uns: die ursprüngliche Zeichenkette ist 66 Zeichen lang, kodiert man jedes Zeichen mit 8 Bit (=1 Byte), benötigt man 528 Bits insgesamt. Die kodierte Zeichenkette sind 219 Zeichen. Es kommt maximal die Zahl 7 vor, dann genügt für jede Stelle 3 Bits (2^3 = 8). Man benötigt also für die kodierte Zeichenkette 657 Bit - immer noch mehr als für die ursprüngliche Zeichenfolge, aber nicht mehr ganz so schlecht, wie bei Wege zur Informationstheorie 1 - Lauflängen . Wie es besser geht, erfahrt ihr im nächsten Teil.

Update 12.03.2022

Da der Container so schnell wieder weg war, ist es nun ein Petling er hängt etwas weiter östlich. Zu den ermittelten Koordinaten rechnet N -0,002' und E +0,012'. Das Privatgrundstück braucht nicht betreten werden.

Update 21.01.2023

Der Petling ist weg, es gelten wieder die ursprünglichen Koordinaten.