Huffmann-Codierung (Leitprogramm)
Autorin:
Julia Imhof
Kompressionsverfahren sind in der heutigen mobilen Zeit wichtiger denn je. Text, Musik, Bilder und Videos sollen so schnell wie möglich im Internet übertragen oder platzsparend abgespeichert werden.
David Huffman entwickelte im Jahre 1952 ein heute noch sehr beliebtes Verfahren zur verlustlosen Kompression von Daten. Dieses Verfahren, die Huffman-Codierung, zeichnet sich durch ihre Präfixfreiheit und Optimalität aus. Präfixfreiheit bedeutet, dass ein Codewort, welches durch eine Kompression entsteht, nie der Anfang eines anderen Codeworts ist. So kann jedes Codewort auch eindeutig dekodiert werden. Weiter ist die Huffman-Codierung optimal, d.h. man kann einen Text (mit Hilfe der Häufigkeitsverteilung) nicht besser codieren. Aus diesen Gründen ist die Kenntnis der Kompression von Daten und insbesondere der Kompression durch die Huffman- Codierung Teil der Allgemeinbildung und muss im Unterricht behandelt werden.
Die intensive Auseinandersetzung mit dem Huffman-Algorithmus und seinen Teilschritten, also dem Aufbau der Häufigkeitstabelle, dem Aufbau des Huffman-Baums aus der Häufigkeitstabelle und das Bestimmen der Codewörter aus dem Huffman- Baum, fördert die Kompetenz des algorithmischen Denkens. Die SuS sollen das Konzept der Huffman-Codierung auch kennenlernen als weiteres Beispiel für einen Greedy-Algorithmus.