Codiere die Folge WWWWWWBBWW mit der Lauflängencodierung in der Schreibweise Anzahl-Zeichen. Aus wie vielen Zeichen besteht das Ergebnis?
2
Welches Verfahren passt?
AFB II
Ordne jeder Situation das Verfahren zu, das den größten Gewinn bringt.
Ein gescanntes Formular, fast nur weiße Fläche mit wenigen schwarzen Linien
Ein deutscher Aufsatz, in dem E und N sehr häufig, X und Y fast nie vorkommen
Ein Programmtext, in dem ganze Zeilengruppen mehrfach fast gleich auftauchen
Ein bereits gepacktes ZIP-Archiv soll noch kleiner werden
Frage dich jeweils: Stehen die Wiederholungen direkt nebeneinander, weiter auseinander — oder geht es gar nicht um Wiederholungen, sondern um Häufigkeiten?
Was ein Verfahren bereits herausgeholt hat, kann ein zweites nicht noch einmal finden. Die Redundanz ist dann schon weg.
3
Rechnung für ein Schwarz-Weiß-Bild
AFB II
Ein Schwarz-Weiß-Bild ist 200 × 100 Pixel groß, jedes Pixel braucht 1 Bit. Jede Zeile besteht aus genau vier Blöcken gleicher Farbe. Rechne die Lauflängencodierung durch.
Rechne die Kette Schritt für Schritt: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
Wie viele Pixel hat das Bild? (200 · 100)Pixel
Wie viele Byte sind das unkomprimiert? (1 Bit pro Pixel, 8 Bit = 1 Byte)Byte
Wie viele Blöcke hat das ganze Bild? (4 pro Zeile, 100 Zeilen)Blöcke
Wie groß ist die RLE-Datei? (2 Byte pro Block)Byte
Auf wie viel Prozent der Originalgröße schrumpft das Bild?%
Fast auf ein Drittel — und das verlustfrei: Aus 800 Byte lässt sich das Bild pixelgenau wiederherstellen. RLE lohnt sich aber nur bei großen einfarbigen Flächen.
Bei RLE speicherst du pro Block nur die Länge und die Farbe — hier 2 Byte pro Block.
4
Trickfrage: der Wunderpacker
AFB III
Jemand verspricht einen Packer, der jede Datei verlustfrei auf die Hälfte schrumpft. Ordne zuerst die Verfahren richtig zu.
Ordne jeden Begriff einem der drei Bereiche zu. Mit der Tastatur: Enter zum Auswählen, dann 1–3 für den Bereich, 0 zurück.
1 nur verlustfrei
2 beides
3 nur verlustbehaftet
Der Wunderpacker kann es nicht geben: Es gibt 8 verschiedene 3-Bit-Folgen, aber nur 4 verschiedene 2-Bit-Folgen. Was ein verlustfreier Packer bei einer Datei einspart, muss er bei einer anderen draufschlagen (Schubfachprinzip). Nur verlustbehaftete Verfahren schaffen jede Datei — aber nicht verlustfrei.
Verlustfrei heißt: Das Original lässt sich Bit für Bit wiederherstellen. Verlustbehaftet heißt: Ein Teil ist endgültig weg.
Und jetzt begründen: Warum wird eine bereits gepackte ZIP-Datei durch ein zweites Packen meist sogar größer? Erkläre es mit dem Schubfachprinzip.
Erwartete Begründung
Verlustfreie Verfahren leben von Wiederholungen und ungleichen Häufigkeiten. Nach dem ersten Packen sind genau diese Muster verschwunden — das Ergebnis sieht fast wie Zufall aus, und Zufall lässt sich nicht kürzen. Das Schubfachprinzip sagt: Wenn ein Verfahren manche Dateien kürzt, muss es andere verlängern. Bei einer schon gepackten Datei landet man fast immer in der zweiten Gruppe — dazu kommen noch die Verwaltungsdaten des neuen Archivs.
5
Rechne nach: Wie stark wird gepackt?
AFB II
Eine Datei ist 4,8 MB groß und schrumpft nach dem Packen auf 1,2 MB. Wie groß ist der Kompressionsfaktor? Trage nur die Zahl ein.
Rechne selbst und trage das Ergebnis ein — Enter prüft direkt.
Der Faktor ist 4 — die Datei ist auf ein Viertel geschrumpft. Achte auf den Unterschied zwischen Faktor (4) und Einsparung (75 %). In Aufgabentexten wird oft nach der Einsparung in Prozent gefragt: Sie ist 1 − 1/Faktor.
Der Faktor ist der Quotient aus Originalgröße und komprimierter Größe: 4,8 geteilt durch 1,2.
6
Fehlersuche: Behauptungen über Kompression
AFB III
In diesem Merkzettel stecken drei Fehler. Klicke genau diese drei Zeilen an.
In diesem Text stecken Fehler. Klicke genau die falschen Zeilen an — die richtigen musst du stehen lassen.
Die drei Fehler zeigen die drei typischen Denkfallen: ZIP für verlustbehaftet zu halten, an einen „Wunderpacker“ zu glauben und verlustbehaftete Verfahren auf Daten anzuwenden, bei denen jedes Zeichen zählt.
Zwei Fehler betreffen die Frage, ob Daten verloren gehen. Ein dritter behauptet etwas, das mathematisch unmöglich ist.
7
Lückentext: die Sprache der Kompression
AFB I
Setze die passenden Fachbegriffe ein. Zwei bleiben übrig.
Wort anklicken, dann Lücke anklicken (oder umgekehrt) — mit Tab und Enter geht es genauso. Ein Klick auf eine gefüllte Lücke legt das Wort zurück.
Wiederholungen und Vorhersagbares in Daten nennt man . Verfahren, die beim Entpacken exakt das Original zurückliefern, arbeiten . MP3 und JPG entfernen zusätzlich Unwichtiges — sie sind . Damit ein Huffman-Code ohne Trennzeichen lesbar bleibt, muss er sein; abgelesen werden die Codes an einem .
Diese fünf Begriffe bilden das Grundgerüst des Häppchens: Redundanz ist der Rohstoff, aus dem jede Kompression ihren Gewinn zieht — ohne Wiederholungen gibt es nichts zu sparen.
Zwei Begriffe beschreiben die beiden großen Verfahrensfamilien — mit und ohne Rückweg zum Original.
8
Paare finden: Verfahren und Trick
AFB I
Acht Begriffe der Kompression — finde zu jedem die passende Beschreibung. Du hast höchstens 16 Versuche.
Decke zwei Karten auf, die zusammengehören. Mit der Tastatur: Tab zur Karte, Enter aufdecken, Pfeiltasten zum Wandern.
Versuche: 0 von 16
Drei Karten sind Verfahren, und jedes greift eine andere Art von Redundanz an: RLE die direkten Wiederholungen, Huffman die ungleichen Häufigkeiten, das Wörterbuchverfahren die wiederkehrenden Textstücke. Moderne Packer wie ZIP kombinieren deshalb mehrere davon.
Ordne zuerst die drei Verfahren zu — die übrigen fünf Karten sind Eigenschaften und Maße.
9
Stimmt das? Fünf Aussagen zur Kompression
AFB II
Stimmt die Aussage? Eine Fehleinschätzung beendet die Serie.
5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann startest du die Serie mit „Neue Runde“ neu.
Aussage 1 von 5
Aussage 2 und 3 sind zwei Seiten derselben Medaille: Kompression lebt von Redundanz. Einmal entfernt, ist sie weg — deshalb gibt es weder den Wunderpacker noch den Doppel-Zip-Trick.
Denke bei jeder Aussage an die Grundfrage: Wo steckt hier noch Redundanz — und wo ist keine mehr?
10
Vier Verfahren im Steckbrief
AFB II
Kreuze für jedes Verfahren an, was zutrifft. Mehrere Kreuze pro Zeile sind möglich.
Setze in jeder Zeile überall dort ein Kreuz, wo die Aussage zutrifft — es können mehrere pro Zeile sein. Enter setzt und löscht.
Verfahren
arbeitet verlustfrei
kurze Codes für häufige Zeichen
ersetzt unmittelbare Wiederholungsfolgen
verweist auf frühere Textstellen
wirft für Menschen Unwichtiges weg
RLE
Huffman
Wörterbuchverfahren
JPG-Kompression
Drei der vier Zeilen tragen das Kreuz „verlustfrei“ — nur JPG nicht. Und jedes verlustfreie Verfahren hat genau einen eigenen Trick. Wer die Tabelle im Kopf hat, kann für jede Datenart das passende Verfahren begründen.
Jede Zeile bekommt höchstens zwei Kreuze — und eines davon entscheidet über verlustfrei oder nicht.
11
Das Wörterbuchverfahren bei der Arbeit
AFB II
Der Text „TO BE OR NOT TO BE“ soll gepackt werden. Spiele durch, wie das Wörterbuchverfahren vorgeht.
Spiele den Ablauf Schritt für Schritt durch: Was passiert als Nächstes? Nur die richtige Karte bringt dich weiter.
Genau nach diesem Prinzip — Verweise auf schon Gesehenes — arbeitet das ZIP-Format. Kombiniert mit Huffman für die Restzeichen entsteht daraus die Kompression, die du täglich benutzt.
Das Verfahren sucht nach Zeichenfolgen, die es schon einmal gelesen hat.
12
Rückblick: Bildbearbeitung aus 2.1.6
AFB II
Du verkleinerst ein Foto von 4000 × 3000 auf 2000 × 1500 Pixel. Warum ist das keine Kompression im Sinne dieses Kapitels?
Kompression will dieselbe Information kürzer speichern. Beim Verkleinern verschwindet dagegen Information, die auch ein Packer nicht zurückholen könnte.
