Komische Bäume Mystery Cache

In der Informatik gibt es "komische" Bäume: die Wurzel ist oben und die Blätter sind unten.

Ein solcher Baum ist der Huffman-Baum, der zur längenoptimierten Kodieren von Nachrichten verwendet wird.

Um an die finalen Koordinaten des Caches zu gelangen, muss in einem ersten Schritt der Huffman-Baum aufgestellt werden. Mit Hilfe dieses Baumes kann dann die Nachricht entschlüsselt werden. Die zu entschlüsselnde Nachricht findet ihr am Ende des Listings ...

Huffman-Baum

(Quelle: Wikipedia Huffman-Kodierung)

Definitionen

• X ist das Quellsymbolalphabet – der Zeichenvorrat, aus dem die Quellsymbole bestehen
• p_x ist die A-priori-Wahrscheinlichkeit des Symbols x (die relative Häufigkeit)
• C ist das Codealphabet – der Zeichenvorrat, aus dem die Codewörter bestehen
• m ist die Mächtigkeit des Codealphabetes C – die Anzahl der verschiedenen Zeichen

Aufbau des Baumes

1. Ermittle für jedes Quellsymbol die relative Häufigkeit, d. h. zähle, wie oft jedes Zeichen vorkommt, und teile durch die Anzahl aller Zeichen.
2. Erstelle für jedes Quellsymbol einen einzelnen Knoten (die einfachste Form eines Baumes) und notiere im/am Knoten die Häufigkeit.
3. Wiederhole die folgenden Schritte so lange, bis nur noch ein Baum übrig ist:
   1. Wähle die m Teilbäume mit der geringsten Häufigkeit in der Wurzel, bei mehreren Möglichkeiten die Teilbäume mit der geringsten Tiefe.
   2. Fasse diese Bäume zu einem neuen (Teil-)Baum zusammen.
   3. Notiere die Summe der Häufigkeiten in der Wurzel.

Um einen eindeutigen Baum zu erhalten, wird Punkt 3.1. erweitert: bei mehreren Möglichkeiten die Teilbäume mit dem niedrigsten ASCII-Wert eines Zeichen.

Hier ein einfaches Beispiel: angenommen wir wollen die Nachricht abcaaad in einer binären Nachricht kodieren. Die Quellsymbole sind somit X={a, b, c, d} und das Codealphabet C={0, 1}. Damit ist m gleich 2.

Schritt 1.: es müssen nun die relativen Häufigkeiten bestimmt werden: P_a=4/7, P_b=1/7, P_c=1/7 und P_d=1/7

Schritt 2: die einzelnen Teilbäume sehen dann wie folgt aus (wobei der Einfachheit halber die Häufigkeiten verwendet wurden):

Schritt 3.1: es gibt drei Teilbäume mit identischer Häufigkeit und Tiefe (b, c und d). Jetzt findet die erweiterte Regel Anwendung womit b und c sind zu wählen sind.

Schritt 3.2 und 3.3: die zusammengefassten Teilbäume mit der kumulierten Häufigkeit sehen dann so aus:

Der Schritt 3 muss solange ausgeführt werden, bis der Baum diese Gestalt hat:

Nachdem der Huffman-Baum aufgestellt ist, können die Kodierungen für das Quellalphabet bestimmt werden (das sogenannte Codebuch).

Konstruktion des Codebuchs

1. Ordne jedem Kind eines Knotens eindeutig ein Zeichen aus dem Codealphabet zu.
2. Lies für jedes Quellsymbol (Blatt im Baum) das Codewort aus:
   1. Beginne an der Wurzel des Baums.
   2. Die Codezeichen auf den Kanten des Pfades (in dieser Reihenfolge) ergeben das zugehörige Codewort.

Auch hier muss der Algorithmus, um einen eindeutigen Baum zu bekommen, erweitert werden: die Kindknoten mit der geringeren Häufigkeit bekommen das Codezeichen 0 zugeordnet (entsprechend der andere Knoten die 1). Ist die Häufigkeit gleich, bekommt der Knoten das Codezeichen 0, dessen Baum das Zeichen mit dem neidrigsten ASCII-Wert hat.

Für obiges Beispiel sieht das dann so aus:

Damit ergeben sich folgende Kodierungen: a=1, b=010, c=011 und d=00. Die Nachricht abcaaad ist also kodiert 101001111100.

Zum dekodieren einer Nachricht, wird der Huffman-Baum anhand des Codealphabets traversiert. Beginnend an der Wurzel bis man auf ein Blatt trifft, das dann das Quellzeichen enthält. Dekodiert man 101001111100, so kommt man von der Wurzel mit der 1 direkt zum Blatt a, dann wieder bei der Wurzel beginnend 010 was zum Knoten b führt.  Dies ist zu wiederholen, bis die komplette Nachricht dekodiert ist ...

Aufgabe

Genug Theorie ... hier die Daten für Eure Aufgabe:

X={0, 1, 3, 4, 5, 6, 8, 9, E, N, .}

P₀=3/19, P₁=3/19, P₃=1/19, P₄=1/19, P₅=2/19, P₆=1/19, P₈=1/19, P₉=3/19, P_E=1/19, P_N=1/19, P_.=2/19

C={0,1}

Um an die finalen Koordinaten zu gelangen, muss folgende Nachricht dekodiert werden:

100101011110011100001101010011000101101011101001110001100110111

Wie bei Mysteries üblich, befindet sich der Cache nicht an den Listing-Koordinaten.

Vielen Dank an Tulip1952 für den Beta-Test.