Kompression implementieren

In 8.1.2 wurde von Hand codiert. Jetzt übernehmen zwei Java-Methoden die Arbeit — eine packt Läufe zu Anzahl-Wert-Paaren, die andere wickelt sie wieder ab.

• Zeichenketten:nur die zugelassenen Operationen: Länge, Zeichen an Position i, Verbinden, Vergleichen.
• Codieren:die äußere Schleife beginnt einen Lauf, die innere zählt, solange dasselbe Zeichen folgt.
• Paar anhängen:code + anzahl + wert: beim Verbinden wird die Zahl als Ziffernfolge angehängt — Notation Anzahl-Wert wie 3r4s1g2r.

public static String codiere(String text) {
    String code = "";
    int i = 0;
    while (i < text.length()) {
        char wert = text.charAt(i);
        int anzahl = 0;
        while (i < text.length() && text.charAt(i) == wert) {
            anzahl++;                       // Lauf zählen
            i++;
        }
        code = code + anzahl + wert;        // Paar anhängen
    }
    return code;
}

• Dekodieren:Ziffern sammeln, bis ein Wert kommt: \(\text{anzahl}\leftarrow\text{anzahl}\cdot 10+\text{Ziffer}\); dann den Wert anzahl-mal anhängen.
• Mehrstellig:13W heißt 13-mal W — nicht 1 und dann 3-mal W.
• Ziffernwert:c - '0' nutzt den ASCII-Wert: '7' - '0' ergibt 7.

public static String dekodiere(String code) {
    String text = "";
    int anzahl = 0;
    for (int i = 0; i < code.length(); i++) {
        char c = code.charAt(i);
        if (c >= '0' && c <= '9') {
            anzahl = anzahl * 10 + (c - '0');   // Ziffer an die Anzahl hängen
        } else {
            for (int k = 0; k < anzahl; k++) {
                text = text + c;                  // Lauf abwickeln
            }
            anzahl = 0;
        }
    }
    return text;
}

Aufruf: codiere("WWWWWWWWWWWWWSSSW") liefert "13W3S1W", dekodiere("13W3S1W") wieder die 17 Zeichen.

Ziehe den Griff unter dem Text nach rechts (Tastatur: Griff mit Tab, dann →) oder starte mit ▶. Beim Dekodieren wickeln sich die Rollen ab, beim Codieren wickeln sich die gelesenen Zeichen zu Rollen auf. Probiere alle drei Beispiele.

Halte fest: Jedes Paar ist eine aufgewickelte Rolle. Dekodieren wickelt sie Zeichen für Zeichen ab, Codieren wickelt jeden Lauf wieder auf — dazwischen geht kein Zeichen verloren.

Für Huffman braucht der Empfänger den Codebaum. Mit den Baum-Operationen aus der Abitur-Anlage wird das Dekodieren zu einer einzigen Schleife.

• Baum:der Huffman-Baum aus 8.2.1 als BinTree; Zeichen stehen nur in den Blättern.
• Wandern:Bit 0 → getLeft(), Bit 1 → getRight().
• Blatt:isLeaf() wahr → getItem() anhängen und zurück zur Wurzel.
• Aufwand:jedes Bit ist genau ein Schritt im Baum — die Laufzeit wächst linear mit der Anzahl der Bits.

public static String dekodiere(String bits, BinTree<Character> wurzel) {
    String text = "";
    BinTree<Character> knoten = wurzel;
    for (int i = 0; i < bits.length(); i++) {
        if (bits.charAt(i) == '0') {
            knoten = knoten.getLeft();
        } else {
            knoten = knoten.getRight();
        }
        if (knoten.isLeaf()) {
            text = text + knoten.getItem();     // Zeichen im Blatt
            knoten = wurzel;                    // zurück zur Wurzel
        }
    }
    return text;
}

Mit dem Baum zu ANANASBANANE aus 8.2.2 (A 0, N 11, S 100, B 1010, E 1011) liefert dekodiere("10100110111011", wurzel) den Text "BANANE".