MINT lernen

Abituraufgaben: Kompression implementieren

Zwei Abituraufgaben zum Implementieren — Lauflänge für einen Pixel-Editor und ein Huffman-Decoder mit BinTree.

Dein Fortschritt:
0 / 0 Aufgaben
1

Zeilen eines Pixel-Editors

14 BEAFB I–II

Ein Pixel-Editor speichert Schwarz-Weiß-Zeilen als Zeichenketten aus . (weiß) und # (schwarz). Zum Speichern wird jede Zeile mit der Lauflängencodierung in der Notation Anzahl-Wert verkürzt. Gegeben sind die Methoden aus dem Unterricht:

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;
}
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;
}
  1. Wenden Sie codiere auf die Zeile "..........###.." an und berechnen Sie das Kompressionsverhältnis (in Zeichen). (3 BE)
  2. Stellen Sie den Ablauf von dekodiere("3#12.") in einer Tracetabelle mit den Spalten i, c, anzahl und text dar. (4 BE)
  3. Implementieren Sie eine Methode static int anzahlPaare(String code), die die Anzahl der Anzahl-Wert-Paare eines Codes zurückgibt. (4 BE)
  4. Erläutern Sie, warum dekodiere(codiere(z)) für jede Pixelzeile z wieder z ergibt, und nennen Sie eine Bedingung, unter der das nicht mehr gilt. (3 BE)

Hinweise

Hinweis zu Aufgabe a)
Drei Läufe; Codelänge durch Zeilenlänge.
Hinweis zu Aufgabe b)
Eine Zeile je Zeichen des Codes; anzahl nach jedem Durchlauf.
Hinweis zu Aufgabe c)
Jedes Paar endet mit genau einem Zeichen, das keine Ziffer ist.
Hinweis zu Aufgabe d)
Welche Zeichen kommen in den Pixelzeilen vor?

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

"10.3#2.": 7 Zeichen statt 15, Kompressionsverhältnis \(\tfrac{7}{15}\approx46{,}7\,\%\), Datenersparnis ≈ 53,3 %.

Erwartungshorizont zu Aufgabe b)
icanzahltext
033""
1#0"###"
211"###"
3212"###"
4.0"###" + 12 Punkte

Ergebnis: "###............" (15 Zeichen).

Erwartungshorizont zu Aufgabe c)
public static int anzahlPaare(String code) {
    int paare = 0;
    for (int i = 0; i < code.length(); i++) {
        char c = code.charAt(i);
        if (!(c >= '0' && c <= '9')) {
            paare++;                            // jeder Wert schließt ein Paar ab
        }
    }
    return paare;
}

anzahlPaare("10.3#2.") liefert 3.

Erwartungshorizont zu Aufgabe d)

Pixelzeilen bestehen nur aus . und #. Jeder Lauf wird als Ziffernfolge plus Wert gespeichert; beim Dekodieren sind Ziffern eindeutig Anzahlen, jedes andere Zeichen ein Wert — genau die Läufe entstehen wieder. Enthält der Text selbst Ziffern (etwa eine Beschriftung „2027“), sind Anzahl und Wert nicht mehr unterscheidbar und das Verfahren arbeitet nicht mehr verlustfrei.

2

Ein Huffman-Decoder mit BinTree

16 BEAFB II–III

Ein Huffman-codierter Text soll wieder lesbar gemacht werden. Der Codebaum liegt als BinTree<Character> mit den Operationen der Abitur-Anlage vor (getLeft(), getRight(), isLeaf(), getItem()); innere Knoten tragen kein relevantes Zeichen. Links steht für 0, rechts für 1.

Codebaum
01010101ENIST
  1. Beschreiben Sie den Weg durch den Baum beim Dekodieren der Bitfolge 1101001. (3 BE)
  2. Implementieren Sie die Methode static String dekodiere(String bits, BinTree<Character> wurzel). (5 BE)
  3. Erweitern Sie die Methode so, dass sie null zurückgibt, wenn am Ende Bits übrig bleiben, die kein vollständiges Codewort bilden (z. B. 11010011). (3 BE)
  4. Zum Codieren wird das Codewort eines Zeichens gebraucht. Entwerfen Sie eine rekursive Methode static String codewort(BinTree<Character> b, char z), die das Codewort von z liefert bzw. null, wenn z nicht im Baum steht. (5 BE)

Hinweise

Hinweis zu Aufgabe a)
Nach jedem Blatt zurück zur Wurzel.
Hinweis zu Aufgabe b)
Ein Knoten-Zeiger wandert; im Blatt Zeichen anhängen und Zeiger zurücksetzen.
Hinweis zu Aufgabe c)
Wo steht knoten nach der Schleife, wenn alles aufging?
Hinweis zu Aufgabe d)
Basisfall Blatt; sonst links suchen und "0" voranstellen, danach rechts mit "1".

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

1 → rechts, 1 → rechts, 0 → links: Blatt S; zurück zur Wurzel. 1 → rechts, 0 → links: Blatt I; zurück. 0 → links, 1 → rechts: Blatt N. Ergebnis: SIN.

Erwartungshorizont zu Aufgabe b)
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;
}
Erwartungshorizont zu Aufgabe c)
public static String dekodiereSicher(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();
            knoten = wurzel;
        }
    }
    if (knoten != wurzel) {
        return null;                            // Bits übrig: kein vollständiges Codewort
    }
    return text;
}

Bei 1101001 steht knoten am Ende wieder auf der Wurzel, bei 11010011 auf einem inneren Knoten → null.

Erwartungshorizont zu Aufgabe d)
public static String codewort(BinTree<Character> b, char z) {
    if (b.isLeaf()) {
        if (b.getItem() == z) {
            return "";                          // gefunden: Weg ist zu Ende
        }
        return null;
    }
    String links = codewort(b.getLeft(), z);
    if (links != null) {
        return "0" + links;
    }
    String rechts = codewort(b.getRight(), z);
    if (rechts != null) {
        return "1" + rechts;
    }
    return null;
}

Für den Baum der Abbildung: E → "00", S → "110", X → null. Jeder Knoten wird höchstens einmal besucht.