Die Webseiten der Fachschaft Informatik am ERG Saalfeld

Der Huffmann-Algorithmus

Dieses Verfahren beruht darauf, häufig vorkommende Zeichen in einem kürzeren und selten vorkommende Symbole in einem längeren Code zu verschlüsseln.
 

Reihenfolge	Beispiel: MISSISSIPPI
Häufigkeitsanalyse - die Ermittlung der Häufigkeit jedes vorkommenden Zeichen	Zeichen M P I S Häufigkeit 1 2 4 4
Ein binärer Baum, aus dem sich der Huffman-Code jedes einzelnen Zeichens ableiten lässt, wird erzeugt. Man beginnt immer mit den zwei Buchstaben, welche die kleinste Häufigkeit besitzen und addiert deren Häufigkeiten. Mit dieser Summe wird dann weitergerechnet und die nächste Häufigkeit addiert. Häufigkeit des nächsten Buchstaben > Summe -> Buchstabe wird auf die rechte Seite geschrieben Häufigkeit des nächsten Buchstaben < Summe -> Buchstabe wird auf die linke Seite geschrieben Dies wird nun solange wiederholt, bis alle Zeichen in einem einzigen Baum sind. Wenn man an einer Verzweigung des Baumes nach links eine "0" und an einer Verzweigung nach rechts eine "1" zuordnet, ergibt sich ein eindeutiger Code für jedes einzelne Zeichen.
Dem häufigsten Zeichen wird der kürzest mögliche Code, dem seltensten der optimal längste Code zugeordnet.	Zeichen S I M P Code 0 11 100 101
In der Ursprungsdatei wird jedes Zeichen durch seinen neuen Code ersetzt.	M I S S I S S I P P I = 100 11 0 0 11 0 0 11 101 101 11
Die Information, welcher Code welchem Zeichen entspricht, wird an die Datei angehängt. Meist werden dort noch weitere diverse statistische und technische Parameter gespeichert. Dadurch vergrößert sich die Datei wieder geringfügig. Mit dem Huffman-Verfahren lässt sich ein Text typischerweise auf ca. 2/3 seiner ursprünglichen Größe reduzieren.	Vergleich: MISSISSIPPI (ASCII): 11 BYTE = 88 Bit MISSISSIPPI (Huffman-verschl.): 21 Bit Einsparung bei diesem Wort: 67 Bit = 76%

Es lässt sich mit mathematischen Mitteln beweisen, dass keine einfach durchgeführte Kodierungsstrategie zu einem besseren Ergebnis führen kann.

Hier das ganze noch als animiertes Gif:
 

Aufgaben

1. Wenden Sie diesen Algorithmus auf das Wort "ABRAKADABRA" an.
2. Beschreiben Sie diesen Algorithmus in Worten.
3. Informieren Sie sich über den Erfinder dieses Algorithmus. (5 Fakten)
4. Zeigen Sie, dass es sich um einen Algorithmus handelt.

zurück