Huffman-Codierung

Du hast erkannt, dass man beim Morsen in Wirklichkeit ein drittes Symbol benötigt, um die einzelnen Codewörter voneinander zu trennen. Die Funker haben dies mit einer etwas längeren Pause gekennzeichnet.

 So geht es ganz einfach: 0000-00-11-01-0100-01-1011-01

 Drei Basissymbole sind nun überaus unpraktisch. Kann man Codes mit veränderlicher Codelänge auch aus zwei Symbolen aufbauen?

 Die Huffman-Codierung

 Die amerikanischen Mathematiker David A. Huffman und Claude Shannon haben diese Frage untersucht und solche Codes entwickelt. Die Idee ist wiederum nicht schwer zu verstehen: Man muss der Codierung ansehen können, wo Codewörter enden. Also darf kein Codewort so aussehen wie das "Anfangsstück" eines anderen Codewortes. Solche Codes werden "präfixfrei" genannt.

 Beispiel (mit vier Codewörtern)

Damit können wir jetzt auch Bilddateien codieren. Dabei müssen wir die Bilddatei aber zunächst untersuchen, damit wir die Codierung so einrichten können, dass sie sich "lohnt".

1. Aufgabe:

Nimm das Bild mit dem Pfeil. Betrachte immer Paare von zwei (aufeinander folgenden) Pixeln und erstelle eine Häufigkeitstabelle.

Ordne nun die vier Code-Wörter möglichst geschickt den "Pixelpaaren" zu. Wie viele Bits benötigt man, wenn man die Bilddatei so codiert? (Hinweis: Das kannst Du ausrechnen, ohne die Bilddatei zu codieren.)

2. Aufgabe:

Finde zwei verschiedene Beispiele für einen präfixfreien Code mit 5 Codewörtern.

3. Aufgabe:

Was hältst Du von der Idee, mit einem solchen Code eine Bilddatei wie den Pfeil mit Hilfe der folgenden Tabelle zu codieren:

4. Aufgabe:

Warum wäre es nicht sinnvoll, das folgende Bild mit der Codierung aus Aufgabe 1 zu codieren? Welche Alternative schlägst Du vor?