Binärbaum-Dekodierung: Archivierte Nachrichten mit Java rekonstruieren

Binärbaum-Dekodierung: So entschlüsselst du archivierte Nachrichten in Java – Ein Tutorial für COMS 228 Projekt 4

Stell dir vor, du erhältst eine komprimierte Nachricht, die mit einem binären Baum codiert wurde. Deine Aufgabe: Rekonstruiere die ursprüngliche Botschaft. Dieses Tutorial führt dich durch die Kernkonzepte des Projekts „Archived Message Reconstruction“ aus dem Kurs COMS 228. Du lernst, wie du einen binären Präfixbaum aus einer Zeichenkette aufbaust, Nachrichten dekodierst und sogar Statistiken wie die durchschnittliche Bitlänge pro Zeichen berechnest. Egal, ob du ein Java-Programmierer in der Ausbildung bist oder deine Kenntnisse in Datenstrukturen auffrischen möchtest – hier findest du eine verständliche Anleitung.

Was ist ein binärer Präfixbaum?

Ein binärer Präfixbaum (auch Huffman-Baum genannt) ist eine Datenstruktur, bei der jedes Blatt ein Zeichen (z. B. 'a', '!') speichert. Die Kanten repräsentieren Bits: 0 für links, 1 für rechts. Der Pfad von der Wurzel zu einem Blatt ergibt die Bitfolge (den Code) für dieses Zeichen. Wichtig: Kein Code ist Präfix eines anderen – das ermöglicht eindeutiges Dekodieren. Stell dir vor, du spielst ein Quizspiel wie „Wer wird Millionär?“, bei dem jede Antwortmöglichkeit durch einen eindeutigen Binärcode repräsentiert wird. Der Baum hilft dir, die richtige Antwort zu finden, ohne dass Codes sich überschneiden.

Das Problem verstehen

Die Eingabedatei (z. B. monalisa.arch) besteht aus zwei Zeilen: Die erste (oder ersten beiden) Zeilen enthalten die Codierungsstruktur als Präorder-Darstellung des Baums. Das Zeichen ^ steht für einen internen Knoten, alle anderen Zeichen sind Blätter. Die zweite (oder dritte) Zeile enthält die komprimierte Bitfolge als Zeichenkette aus '0' und '1'. Dein Programm soll diese einlesen, den Baum rekonstruieren, die Bitcodes ausgeben und schließlich die Nachricht dekodieren.

Schritt 1: Aufbau des Baums (rekursiv)

Die Klasse MsgTree enthält ein Zeichen payloadChar, Referenzen auf linkes und rechtes Kind sowie einen statischen Index staticCharIdx. Der Konstruktor MsgTree(String encodingString) erzeugt den Baum rekursiv: Wenn das aktuelle Zeichen ^ ist, erstelle einen internen Knoten (leeres Zeichen) und rufe rekursiv buildTree für linkes und rechtes Kind auf. Andernfalls erstelle ein Blatt mit dem Zeichen. Der statische Index wird bei jedem Schritt erhöht. Ein rekursiver Ansatz ist elegant und leicht verständlich – perfekt für Java-Projekte im Studium.

public MsgTree(String encodingString) {
    if (encodingString == null || encodingString.length() == 0) return;
    char c = encodingString.charAt(staticCharIdx);
    staticCharIdx++;
    if (c == '^') {
        payloadChar = '\0';
        left = new MsgTree(encodingString);
        right = new MsgTree(encodingString);
    } else {
        payloadChar = c;
        left = null;
        right = null;
    }
}

Schritt 2: Bitcodes ausgeben mit printCodes()

Die statische Methode printCodes(MsgTree root, String code) durchläuft den Baum präorder. Für jedes Blatt wird das Zeichen und der aktuelle Code ausgegeben. Für interne Knoten wird rekursiv printCodes(left, code + "0") und printCodes(right, code + "1") aufgerufen. So erhältst du eine Tabelle aller Zeichen und ihrer Binärcodes – nützlich, um die Dekodierung zu überprüfen.

Schritt 3: Nachricht dekodieren mit decode()

Die Methode decode(MsgTree codes, String msg) liest die Bitfolge Bit für Bit. Starte an der Wurzel, folge bei '0' dem linken, bei '1' dem rechten Kind. Erreichst du ein Blatt, gib das Zeichen aus und kehre zur Wurzel zurück. Wiederhole dies, bis die gesamte Nachricht verarbeitet ist. So entsteht der ursprüngliche Text – wie das Lösen eines Rätsels, bei dem jeder Binärcode ein Puzzleteil ist.

public void decode(MsgTree codes, String msg) {
    MsgTree current = codes;
    for (int i = 0; i < msg.length(); i++) {
        current = (msg.charAt(i) == '0') ? current.left : current.right;
        if (current.left == null && current.right == null) {
            System.out.print(current.payloadChar);
            current = codes;
        }
    }
}

Bonus: Iterativer Ansatz (15 % Extra-Credit)

Ein iterativer Algorithmus zum Baumbau vermeidet Rekursion und verwendet einen expliziten Stack. Das ist anspruchsvoller, aber eine tolle Übung für fortgeschrittene Java-Entwickler. Du musst den Präorder-String Zeichen für Zeichen verarbeiten und dabei den Stack nutzen, um die Elternknoten zu verwalten. Der Lohn: 15 % Bonus und ein tieferes Verständnis für Baumkonstruktion.

Statistiken ausgeben (5 % Extra-Credit)

Berechne nach der Dekodierung die durchschnittliche Bitlänge pro Zeichen, die Gesamtzahl der Zeichen und die Speicherersparnis im Vergleich zu 16-Bit-Unicode. Die Formel: (1 - compressedBits / uncompressedBits) * 100. Diese Werte zeigen, wie effizient die Komprimierung ist – ein Thema, das auch bei Datenkompression in Apps wie WhatsApp oder Instagram eine Rolle spielt.

Praktische Tipps für dein Projekt

• Teste mit einfachen Beispielen: Erstelle kleine .arch-Dateien wie ^a^^!^dc^rb und überprüfe die Ausgabe.
• Achte auf Zeilenumbrüche: Wenn die erste Zeile mit ^ endet, könnte die zweite Zeile Teil des Baums sein. Lies beide Zeilen ein und entscheide.
• Verwende Javadoc: Dokumentiere deine Methoden mit @author und @param – das gehört zur guten Programmierpraxis.
• Bonus früh einreichen: Der Early-Submission-Bonus lässt sich mit den anderen Boni kombinieren.

Fazit

Mit diesem Tutorial hast du das Rüstzeug, um archivierte Nachrichten mit einem binären Präfixbaum in Java zu dekodieren. Ob rekursiv oder iterativ – du trainierst wichtige Datenstrukturen und Algorithmen, die in der Informatikausbildung und in der Praxis unverzichtbar sind. Viel Erfolg bei deinem Projekt!