MINT üben

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?