MINT lernen

Übungen: Codierung im Abitur

Lauflänge, Huffman und Kompressionsverhältnis — zehn Aufgaben zur Codierung.

Dein Fortschritt:
0 / 0 Aufgaben
1

Übungsaufgaben

Zehn Aufgaben vom Wiedererkennen der Notation (AFB I) bis zur Beurteilung, wann Kompression lohnt (AFB III).

A1
Eigenschaften des Huffman-Codes
AFB I

Gib alle zutreffenden Aussagen zum Huffman-Verfahren an.

Mehrere Antworten sind richtig. Markiere alle zutreffenden und klicke dann auf „Prüfen“.
Huffman ist verlustfrei: Die Originaldaten lassen sich exakt wiederherstellen. Bei Gleichstand sind mehrere Bäume möglich, alle mit derselben Gesamtbitzahl.
Frage: Woher weiß der Empfänger, welcher Code zu welchem Zeichen gehört?Warum? Ohne Codetabelle ist die Bitfolge nicht lesbar.
Hilfe: Präfixfrei heißt: Man erkennt das Codeende ohne Trennzeichen.
A2
Stimmt's? — Lauflänge
AFB I

Fünf Aussagen zur Lauflängencodierung in der Notation Anzahl-Wert. Ordne sie als richtig oder falsch ein.

5 Aussagen nacheinander. Eine falsche Einschätzung reicht — dann startest du die Serie mit „Neue Runde“ neu.
Aussage 1 von 5

Lauflänge lohnt sich nur bei langen Wiederholungen.
Frage: Was steht zuerst: Anzahl oder Wert?Warum? Die Prüfungsvorgaben legen Anzahl-Wert fest.
Hilfe: Einzelne Zeichen werden zu zwei Zeichen.
A3
Kompressionsmaße
AFB I

Erkläre die beiden Kennzahlen, indem du die Lücken füllst — ein Wort bleibt ü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.

Das Kompressionsverhältnis ist die Größe der Daten geteilt durch die Größe der . Je es ist, desto stärker die Kompression. Die Datenersparnis gibt man in an. Lauflänge und Huffman arbeiten .

Ein Verhältnis über 1 heißt: Die „komprimierten“ Daten sind größer geworden.
Frage: Was steht im Zähler, was im Nenner?Warum? Komprimiert durch Original.
Hilfe: 0,8 bedeutet 20 % Ersparnis.
A4
Welche Codierung passt?
AFB I

Ordne jedem Datenbeispiel das Verfahren zu, das hier am meisten spart.

Ziehe jede Karte in den passenden Korb — oder wähle sie mit Enter aus und drücke dann die Ziffer des Korbs (0 legt sie zurück).
1Lauflänge
2Huffman
3kaum komprimierbar
Zufällige und bereits komprimierte Daten enthalten kaum Muster — keine der beiden Methoden spart dort etwas.
Frage: Gibt es lange Wiederholungen oder ungleiche Häufigkeiten?Warum? Lauflänge braucht Wiederholungen, Huffman ungleiche Häufigkeiten.
Hilfe: Zufall hat weder das eine noch das andere.
A5
Bits zählen
AFB I

Für das Wort ANANAS gilt der Huffman-Code A = 0, N = 10, S = 11. Berechne die Anzahl der Bits des codierten Wortes.

Überlege selbst und trage das Ergebnis ein — Enter prüft direkt.
A: 3 · 1 Bit, N: 2 · 2 Bit, S: 1 · 2 Bit → 3 + 4 + 2 = 9 Bit.
Frage: Wie oft kommt jeder Buchstabe vor?Warum? Häufigkeit mal Codelänge.
Hilfe: A dreimal, N zweimal, S einmal.
A6
Huffman Schritt für Schritt
AFB II

Stelle das Vorgehen zur Erstellung eines Huffman-Codes in der richtigen Reihenfolge dar.

Ziehe die Karten in die richtige Reihenfolge — mit der Tastatur: ↑/↓ verschiebt, Shift+↑/↓ wechselt nur den Fokus.
1Häufigkeit jedes Zeichens zählen
2Jedes Zeichen als Knoten mit seiner Häufigkeit notieren
3Die zwei kleinsten Knoten zu einem neuen Knoten zusammenfassen
4Wiederholen, bis nur noch ein Baum übrig ist
5Kanten beschriften (links 0, rechts 1) und Codes ablesen
Die Beschriftung der Kanten kommt erst zum Schluss — vorher steht die Form des Baumes noch nicht fest.
Frage: Was braucht man, bevor man irgendetwas zusammenfasst?Warum? Die Häufigkeiten.
Hilfe: Zusammenfassen wird wiederholt, bis ein Baum bleibt.
A7
Lauflänge rechnen
AFB II

Eine Bildzeile lautet wwwwbbbwwwwwwbb (w = weiß, b = schwarz). Ermittle die Kennzahlen, wenn jedes Zeichen gleich viel Speicher braucht.

Arbeite die Kette Schritt für Schritt ab: Erst wenn ein Schritt stimmt, wird der nächste freigeschaltet. Enter prüft.
  1. Länge des Originals (Zeichen):
  2. Länge der Codierung 4w3b6w2b (Zeichen):
  3. Kompressionsverhältnis (2 Nachkommastellen):
  4. Datenersparnis (ganze Prozent): %
8 : 15 ≈ 0,53; (1 − 0,53) · 100 % ≈ 47 %.
Frage: Wie viele Zeichen hat die codierte Folge?Warum? Jede Folge wird zu Anzahl + Wert.
Hilfe: Vier Folgen × 2 Zeichen.
A8
Code und Eigenschaft
AFB II

Analysiere die Codes für die Zeichen A, B, C, D und verbinde jeden mit der zutreffenden Eigenschaft.

Klicke links einen Eintrag an und dann rechts den passenden — es entsteht eine Verbindungslinie. Mit der Tastatur: Enter zum Auswählen, ↑/↓ zum Wandern.
Der erste Code könnte ein Huffman-Code sein. Beim dritten kann „010“ als B A oder als A D gelesen werden — ohne Trennzeichen nicht eindeutig.
Frage: Ist ein Code der Anfang eines anderen?Warum? Das verhindert eindeutiges Decodieren.
Hilfe: Vergleiche jedes Codewort mit dem Anfang der anderen.
A9
Jonas rechnet Kompression
AFB II

Jonas vergleicht eine Datei von 200 KB mit ihrer komprimierten Fassung von 150 KB. Überprüfe seine Notizen.

In diesem Text stecken Fehler. Klicke genau die falschen Zeilen an — die richtigen musst du stehen lassen.
Verhältnis und Ersparnis ergänzen sich zu 1 bzw. 100 %.
Frage: Was misst die Datenersparnis?Warum? Den eingesparten Anteil.
Hilfe: Ersparnis = 1 − Verhältnis.
A10
Lohnt sich das?
AFB III

Beurteile für jeden Fall, wie gut sich Lauflängencodierung eignet.

Wähle für jede Zeile eine Stufe: 1 = wird länger, 2 = kein Gewinn, 3 = kleiner Gewinn, 4 = deutlicher Gewinn, 5 = sehr großer Gewinn. Mit der Tastatur: Tab zur Zeile, ←/→ zwischen den Stufen, Enter setzt.
1 = wird länger5 = sehr großer Gewinn
abcdefgh
aabbccdd
aaaaaaaabbbbbbbb
eine Zeile mit 1000 weißen Pixeln
aaabbbcc
aabbccdd → 2a2b2c2d, genauso lang. aaabbbcc → 3a3b2c, 8 → 6 Zeichen.
Frage: Wie lang wird die Codierung im Vergleich?Warum? Jede Folge kostet zwei Zeichen.
Hilfe: Folgen der Länge 1 verdoppeln, der Länge 2 gleichen aus.