Wege zur Informationstheorie 3- Shannon-Fano Mystery Cache

Generelles
(bei allen Caches der Wege zur Informationstheorie identisch)

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. 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

Grundsätzliche Überlegungen

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" und später z.B. für die Anzeige am Monitor wieder zurück übersetzen. Die Folge von 0 und 1 für ein einzeles Zeichen nennt man dann auch Kodewort. Für das Umwandeln in die eine oder andere Richtung gibt es verschiedene Standardtabellen, die z.B. das Betriebssystem mitbringt. Je nach verwendeter Tabelle und natürlich den zu komprimierenden Daten, kann sich eine bessere oder schlechtere Kompression ergeben, wie wir in Lauflängenkodierung 1 vs. Lauflängenkodierung 2 gesehen haben.

Da man auf die zu komprimierenden Daten keinen Einfluss hat (niemand möchte die Formulierungen in seinem Brief seltsam gestalten, nur damit er dann die Textdatei besser komprimieren kann), kann man nur an der Tabelle arbeiten.

Teil 3 - Shannon-Fano Kodierung

Dieser Algorithmus ist nach seinen Erfindern Claude Shannon und Robert Fano benannt. Ein paar Dinge sind aber grundsätzlich anders als bei der Lauflängenkodierung, es gibt aber ein paar generelle Anforderungen an solch ein Verfahren:

1. die Tabelle zur Übersetzung von Buchstaben in Kodewörter soll so generiert werden, dass sie möglichst "optimal" ist, d.h. die Ausgabe insgesamt möglichst kurz ist.
2. dazu übersetzt man die einzelnen Zeichen, im Gegensatz zu den Tabellen bei der Lauflängenkodierung, in Kodewörter, die im Allgemeinen nicht alle die gleiche Länge haben
   Es gilt, salopp gesagt: Zeichen, die ziemlich häufig vorkommen, bekommen kurze Kodewörter (da kann man am meisten sparen), ganz selten vorkommende Zeichen erhalten lange Kodewörter (da sie nur selten vorkommen, ist das ja nicht so schlimm)
3. Damit man später den Text wieder leserlich machen kann, muss die Kodierung eindeutig umkehrbar sein. Bei einer festen Länge von Kodewörtern (wie bei den Tabellen bei den Lauflängen-Caches), ist das automatisch gegeben. Hier wird dagegen ein sogenannter präfixfreier Code generiert: Kein Kodewort ist gleich dem Beginn eines anderen Kodeworts.
   Beispiel 1: ist A = 0, B = 1, C = 01, könnte der Code 01 für C oder auch für AB stehen, ist also nicht eindeutig.
   Beispiel 2: ist A = 0, B = 10, C = 11: dies ist ein präfixfreier Code, denn kein Kodewort ist Beginn eines anderen

Insbesondere Punkt 2 ist zunächst interessant: wie weiß man denn, welches Zeichen besonders oft im Ausgangstext vorkommt?
Antwort: man zählt sie einfach und schreibt sich das Ergebebnis auf. Hochtrabend spricht man dann davon eine Statistik der Auftrittswahrscheinlichkeit zu erstellen und das Verfahren gehört damit zu den Entropiekodierern.

Aber lassen wir uns nicht von den schwülstigen Fachbegriffen beeinndrucken, sondern schauen und die Grundlage des Verfahrens an:

1. Wir zählen, wie oft jedes Zeichen (Buchstabe) in dem zu komprimierenden Text vorkommt
2. Wir halten das in einer Liste fest und sortieren diese Liste absteigend nach Anzahl der Vorkommen
3. Wir teilen diese Liste in zwei Teile und zwar so, dass die Summe der Anzahl der Zeichen in beiden Teilen möglichst gleich groß ist. Gleich groß soll in unserem Fall heißen, wenn wir die Anzahl der auftretenden Buchstaben in einem Teil durch die Anzahl der Buchstaben im anderen Teil teilen, möchten wir möglichst nahe an den Wert 1 kommen. Dabei teilen wir immer die kleiner Zahl durch die größere.
4. Für die Kodierung erhält der erste Teil die 0, der zweite die 1 als Code
5. Man betrachtet nun den oberen und den unteren Teil als zwei neue (voneinander unabhängige) Listen und wiederholt das Verfahren ab Schritt 3, bis sich in jeder Gruppe nur noch ein Element befindet

Zweckmäßig hält man die Daten in einer Tabelle vor, wie wir es in dem folgenden Beispiel machen. Nehmen wir beispielsweise an, wir hätte für den jeweiligen Buchstaben folgende Anzahl im Text ermittelt: A = 40, B = 28, C = 14, D = 11, E = 8, F = 8, G = 2.

Dann schreibt man in Tabellenform gemäß 2.
 

Jetzt müssen wir bei 3. überlegen, wo wir die Tabelle schneiden. Schneiden wir zwischen A und B hätte man oben 40 und unten 71 (=28+14+11+8+8+2), gibt ein Verhältnis (wir teilen immer die kleinere durch die größere Zahl) von 40/71 = 0,563. Schneidet man zwischen B und C, hätte man oben 68 (=40+28) und unten 43 (=14+11+8+8+2), ergibt ein Verhältnis (wir teilen immer die kleinere durch die größere Zahl) von 43/68 = 0.632. Schneiden wir zwischen C und D, hätte man oben 82 (=40+28+14) und unten 29 (=11+8+8+2), gibt ein Verhältnis (wir teilen immer die kleinere durch die größere Zahl) von 29/82 = 0,353. Schneiden wir noch weiter unten wird das Verhältnis noch schlechter (wer es nicht glaubt kann gerne nachrechnen).

Wir schneiden also zwischen B und C, den ersten (=oberen Teil) kodieren wir gemäß 4. mit 0, den unteren mit 1. Somit erhalten wir die aktualisierte Tabelle:

Der obere Teil enthält nur 2 Elemente A und B. Das teilen wir einfach in der Mitte (bleibt ja nichts übrig) und kordieren den oberen Teil wieder mit 0 und den unteren mit 1.
Der untere Teil C-G wird nun nach gleicher Vorgehensweise wieder zerstückelt: Schneidet man zwischen C und D hätte man 14 oben zu 29 (=11+8+8+2) unten ergibt im Verhältnis 14/29 = 0.48.., beim Schnitt zwischen D und E ergäbe sich oben 25 (=14+11) und unten 18 (=8+8+2) mit dem Verhältnis 18/25 = 0,72, beim Schnitt zwischen E und F ergäbe sich 33 (=14+11+8) zu 10, also 10/33 = 0,3, danach wird es noch schlechter, also schneiden wir zwischen D und E und erhalten damit:

Mit A und B ist man bereits fertig, bei C und D sind nur diese 2 Elemente enthalten; man teilt hier einfach wieder in der Mitte und fügt C die 0 und D die 1 an. Für E, F, G muss man wieder die Verhältnisse ausrechnen. Ergebnis, schneide zwischen E und F.
Final ergibt sich dann, die Teilungen und die Kodewörter, die man von links nach rechts ablesen kann.

Noch eine letzte Anmerkung für die Theoretiker unter uns:: In unserem Beispiel hätte man 111 Buchstaben. Werden die mit 8 Bit pro Zeichen im PC gespeichert (das wäre ein üblicher Standard), benötigt man dafür 111*8 = 888 Bits. Durch das komprimieren benötigt man nur noch 275 Bits (40*2+28*2+14*3+11*3+8*3+8*4+2*4). Die Einsparung ist also doch beträchtlich. Da jedoch für das Decodieren der Nachricht, die Kodier-Tabelle notwendig ist, muss man die auch mit ablegen/abspeichern, was die Einsparung wieder etwas abschwächt, aber der Effekt ist immer noch immens.

Das ist dann eigentlich auch schon alles.

Der Cache

Folgende Buchstaben / Zeichen kommen in den Koordinaten mit der jeweiligen Häufigkeit vor.

Der Cache befindet sich dann bei

0110011101100010101100011010101001100111001011010100000111010110011000011110001110110001010110001101010
1001100111001011010100000100001010001111111000101000111111100111001011010100111101101101001001111010011
011010010011110100011101011001100

Noch eine letzte Anmerkung für die Theoretiker unter uns: die ursprüngliche Zeichenkette ist 72 Zeichen lang, kodiert man jedes Zeichen mit 8 Bit (=1 Byte), benötigt man 576 Bits insgesamt. Die kodierte Zeichenkette sind 239 Bits lang. Man sieht hier also, es wurden über die Hälfte der Bits eingespart.

Update 22.05.2022

Aufgrund der versifften Stelle am Final wurde die Dose etwas verlegt. Von der Nordkoordinate zieht ihr 0.006' und von der Ost 0.011' ab. Der Checker funktioniert dann mit den angepassten Koordinaten.