Einführung in die Huffman-Codierung

Theoretische Grundlagen

Die Huffman-Codierung ist ein Verfahren zur verlustfreien Komprimierung von Daten, bei dem häufig auftretende Zeichen kürzere Codes erhalten als selten auftretende. Dies führt in der Regel zu einer effizienteren Speicherung oder Übertragung von Daten. Die Idee wurde von David A. Huffman im Jahr 1952 entwickelt.

Grundprinzip

Beim Huffman-Verfahren wird aus den Häufigkeiten der vorkommenden Zeichen ein binärer Baum erstellt, bei dem häufig vorkommende Zeichen näher an der Wurzel liegen und somit kürzere Bitmuster erhalten. Seltener vorkommende Zeichen werden weiter unten im Baum platziert und erhalten längere Bitmuster. Das Resultat ist ein präfixfreier Code, der unzweideutig dekodiert werden kann.

Beispiel für eine Huffman-Codierung

Nehmen wir an, wir haben das Wort "BAMM". Die Häufigkeiten:

• B: 1
• A: 1
• M: 2

Ein möglicher Code wäre:

• M: 0
• B: 10
• A: 11

"BAMM" => 10 11 0 0

Eigenschaften der Huffman-Codierung

• Optimalität: Huffman liefert für gegebene Häufigkeiten einen der kürzesten binären Präfixcodes.
• Präfixfreiheit: Kein Code ist Präfix eines anderen, eindeutige Dekodierung ist garantiert.

Visuelle Darstellung

Huffman-Baum bauen für: "MISSISIPPI"

Schritt 1:

Nimm einen Stift und Papier oder verwende die Desktopanwendung "Paint", um deinen Huffman-Baum zum Wort "MISSISIPPI" zu erstellen.

Schreibe alle Buchstaben, die im Wort vorkommen, auf und deren Häufigkeit. Zum Beispiel: Der Buchstabe "S" kommt 3-mal vor.

Schritt 2:

Beginne von unten mit dem Aufbauen des Baumes. Zeichne ein Element für die Buchstaben, die am wenigsten vorkommen. Im Beispiel von oben wären das: O, U, X, P, R und L. Du musst mindestens zwei Elemente erstellen. Wenn du also nur einen Buchstaben hast, der am wenigsten vorkommt, kombiniere ihn mit dem zweitwenigsten.

Schritt 3:

Verbinde die Elemente mit einer Linie und schreibe die Summe der Häufigkeiten auf.

Schritt 4:

Wiederhole Schritt 2 und 3, bis du nur noch ein Element hast.

Schritt 5:

Die Huffman-Codierung ist der Pfad von der Wurzel bis zum Blatt. Der Pfad nach links wird mit einer 0 und der Pfad nach rechts mit einer 1 codiert.

Wenn du nun also den Code für einen Buchstaben willst, gehe von oben dem Pfad entlang zu deinem gewünschten Buchstaben, und durch die Nullen und Einsen an den Linien hast du deinen Code.