Mit Huffman codieren: Übungen – Informatik Grundkurs

Ihr Fortschritt:

0 / 0 Aufgaben

Übungsaufgaben

Dreißig Übungen in gemischter Reihenfolge — Sie klicken, ziehen, ordnen, rechnen und knobeln. Jede Übung gibt Ihnen sofort eine Rückmeldung, und zu jeder Aufgabe gibt es zwei gestufte Tipps: Der erste zeigt die Richtung, der zweite den entscheidenden Schritt. Die Chips zeigen das Anforderungsniveau: AFB I heißt wiedergeben und direkt anwenden, AFB II selbst entscheiden und verknüpfen, AFB III begründen, beurteilen oder eine Falle durchschauen. Aufgaben mit dem Chip Mix verbinden Wissen aus früheren Unterkapiteln, bei Trick steckt eine Falle drin. Fahren Sie über ein unterstrichenes Arbeitswort, sehen Sie, was es genau von Ihnen verlangt.

Fachbegriffe zum Codieren

AFB I

Lösen Sie das Kreuzworträtsel: Tragen Sie zu jedem Hinweis den passenden Fachbegriff ein.

Klicken Sie einen Hinweis oder ein Kästchen an und tippen Sie das Wort — der Cursor springt von selbst weiter. ←→↑↓ wandern, Leertaste wechselt die Richtung, ⌫ löscht, Enter prüft. Umlaute als Ä, Ö, Ü eintippen.

Waagerecht

Senkrecht

PRÄFIXFREI kreuzt HÄUFIGKEIT im I und WURZEL im E; CODEWORT kreuzt HÄUFIGKEIT im E, BLATT im T. Das Ä tippen Sie als Ä ein, nicht als AE.

Beginnen Sie mit dem langen waagerechten Wort: Es beschreibt die Eigenschaft, die das Decodieren ohne Trennzeichen möglich macht.

Zählen Sie die Buchstaben der Kästchen und nutzen Sie die Kreuzungen: Der Buchstabe, in dem sich zwei Wörter treffen, gehört zu beiden Begriffen.

Der Kreis beim Decodieren

AFB II

Erklären Sie das Decodieren eines Bitstroms: Schalten Sie jedes Feld mit „?“ so weiter, dass der Kreis einen Durchlauf für ein Zeichen zeigt.

Schalten Sie jedes Feld mit „?“ per Klick weiter, bis der Kreislauf stimmt — die Pfeile laufen im Uhrzeigersinn. Mit der Tastatur: Tab zum Feld, Enter oder ↓ weiter, ↑ zurück.

Decodieren

Jedes Zeichen beginnt an der Wurzel. Bit für Bit wird abgebogen (0 links, 1 rechts), bis ein Blatt erreicht ist; dort steht das Zeichen. Dann geht es zurück zur Wurzel, solange noch Bits übrig sind. Im Blatt weiterzulaufen ist der typische Fehler: Jedes Codewort beginnt neu.

Überlegen Sie, wo jedes Zeichen im Baum beginnt und woran Sie merken, dass es zu Ende ist.

Ein Blatt beendet ein Codewort. Danach beginnt das nächste Zeichen wieder an der Wurzel — und das wiederholt sich, bis der Bitstrom aufgebraucht ist.

Welches Verfahren passt?

AFB IIMix

Vergleichen Sie drei Verfahren (Code fester Länge, Lauflängencodierung, Huffman-Code) für sechs Datensätze: Ziehen Sie jeden Datensatz unter das Verfahren, das sich dafür am besten eignet, und in die Zeile, die zur erwarteten Einsparung passt.

Ziehen Sie jedes Kärtchen in das passende Feld — oder klicken Sie es an und dann das Feld. Mit der Tastatur: Enter wählt ein Kärtchen, die Pfeiltasten schieben es von Feld zu Feld, Esc legt es zurück. Nach dem Prüfen heißt ↔: waagerecht falsch, ↕: senkrecht falsch.

Lauflänge lohnt bei wenigen langen Läufen (Faxseite, zwei Läufe), Huffman bei sehr ungleichen Häufigkeiten ohne Läufe (Zeichen E, 90 %). Beim Schachbrett gibt es nur Läufe der Länge 1, bei 8 gleich häufigen Zeichen haben alle Huffman-Codewörter 3 Bit — beide sparen gegenüber dem festen Code nichts.

Fragen Sie bei jedem Datensatz: Gibt es lange Folgen gleicher Zeichen, oder sind nur die Häufigkeiten stark verschieden?

Sind alle Zeichen gleich häufig oder wechselt jedes Pixel, hilft weder Lauflänge noch Huffman gegenüber dem festen Code.