Datenkomprimierung und Huffmann-Kodierung

Für die digitale Verarbeitung werden Daten aller Art, wie z.B. Texte, Bilder, Audiosignale und Videos digital repräsentiert bzw. kodiert. Je nach Art der gewählten Kodierung werden für eine gegebene Menge an Informationen mehr oder weniger Bits benötigt, um diese zu repräsentieren. Kompakte (also wenig redundante) Kodierungen haben den Vorteil, dass sie das Datenvolumen minimieren, was eine effizientere Speicherung und Übertragung von Daten ermöglicht. Hingegen können redundantere Kodierungen eine schnellere Verarbeitung und die Fehlererkennung sowie –korrektur ermöglichen.

Das Ziel dieser Unterrichtssequenz ist es, die Grundidee der Datenkomprimierung einzuführen und mit der Huffman-Kodierung eine optimale Kodierung für Texte vorzustellen. Die Schülerinnen und Schüler

• verstehen die Motivation für die Datenkomprimierung,
• lernen, dass verschiedene Kodierungen der gleichen Information zu unterschiedlich langen Darstellungen führen und somit unterschiedlich grosse Datenvolumina benötigen,
• können Texte mit vorgegebenen Kodierungen kodieren und dekodieren,
• verstehen den Zusammenhang zwischen der relativen Häufigkeit von Zeichen in einem Text und der Länge ihrer Kodierungen,
• verstehen den Vorteil der Präfixfreiheit von Kodierungen,
• kennen die Baumdarstellung von Kodierungen und können damit Texte kodieren und dekodieren,
• können den Huffman-Algorithmus für eine gegebene Häufigkeitsverteilung anwenden.