Huffman-Codierung
Du möchtest wissen, was es genauer mit der Huffman-Codierung auf sich hat? Im Folgenden erklären wir dir an einem einfachen Beispiel, wie du mithilfe dieser Codierung den optimalen Code finden kannst.
Inhaltsübersicht
Huffman-Kodierung
Die Huffman-Codierung ist ein Codierungsverfahren, das zu einem optimalen Code mit möglichst kleiner mittlerer Codewortlänge führt. Bei der Nachrichtenübertragung mit optimalen Codes werden die Übertragungszeiten reduziert. Der Empfänger deiner Nachricht erfährt dadurch deutlich schneller, was du ihm mitteilen möchtest.
Die Formel für die mittlere Codewortlänge lautet:
Ganz allgemein gilt, die mittlere Codewortlänge bei der Huffman-Codierung ist kleiner als die bei der Shannon-Fano-Codierung. Daraus folgt, dass die Huffman-Codierung allgemein besser ist.
Beispiel
Aber das wollen wir nun nicht einfach so stehen lassen, sondern selbst nachprüfen! Deshalb codieren wir nun ein Beispiel nach dem Huffman-Verfahren. Du willst mit deiner Freundin mal wieder eine gute Bar besuchen. Du hast die Anzahl der bisherigen Besuche in euren Lieblingsbars in einer Strichliste notiert. Gegeben ist eine Strichliste, die die Anzahl deiner Besuche in Bars angeben. Je mehr Striche eine Bar schon hat, desto wahrscheinlicher wirst du diese wieder besuchen. Meistens landest du in der Soju Bar, denn an 8 von 34 Abenden warst du dort. Daher sollte das Codewort für Soju Bar kurz sein, um die Nachricht schnell zu übermitteln.
Zunächst einmal bestimmen wir die relative Häufigkeit der Besuche, damit wir die Bars nach aufsteigender Wahrscheinlichkeit sortieren können. Bei zwei gleich häufigen Ereignissen ist es egal, welches zuerst kommt. Da die Namen etwas zu lang sind, kürzen wir diese im Folgenden einfach ab, sodass Barbie Deinhoff’s zu BD und die Weinerei zu DW wird.
Huffman Baum erstellen
Beim Huffman-Code gibt es eine eindeutige Vorgehensweise, die einem Fahrplan mit vier Schritten folgt. Nachdem wir die Ereignisse nun schon sortiert haben, können wir direkt mit dem ersten Schritt loslegen. Dabei musst du in der sortierten Liste jeweils die zwei Zeichen mit den niedrigsten Auftretenswahrscheinlichkeiten finden. In unserer Liste gibt es drei Zeichen mit der kleinsten Auftretenswahrscheinlichkeit 
. Wir können daher frei entscheiden welche zwei wir auswählen.
Wir nehmen einfach die beiden Zeichen ganz links in der sortierten Liste, also PG und DH. Im zweiten Schritt werden die zwei gefundenen Zeichen zu einem neuen Element verschmolzen, dessen Wahrscheinlichkeit die Summe der beiden Einzelwahrscheinlichkeiten ist.
Wir zeichnen dabei einen Knoten, der die Zeichen PG und DH zu einem neuen Element verbindet, dessen Auftretenswahrscheinlichkeit dann 
ist. Damit können wir schon mit Schritt drei beginnen, der Einsortierung des neuen Elements. Hier gilt es die Liste neu zu sortieren, wenn das neue Element nicht die geringste Auftretenswahrscheinlichkeit in der Liste hat. Das ist auch meistens der Fall.
Neue Anordnung der Elemente
Unsere Liste ist jetzt nicht mehr nach aufsteigender Wahrscheinlichkeit sortiert, denn das neue Element – bestehend aus PG und DH – hat die Auftretenswahrscheinlichkeit . Die Wahrscheinlichkeit des Elements BD ist aber kleiner und muss daher ganz am Anfang stehen. Wir sortieren die Liste daher neu, nach aufsteigender Wahrscheinlichkeit.
Nun fahren wir mit den ersten Schritten rekursiv fort. Wir suchen in unserer neuen Liste erneut die Elemente mit der niedrigsten Auftretenswahrscheinlichkeit. Dann kommen wir wieder zu Schritt zwei, indem wir diese dann zusammenfassen und zu einem neuen Element verschmelzen.
Das neue Element hat die Auftretenswahrscheinlichkeit 
. Wir müssen die Liste jetzt wieder neu sortieren, sodass alle Elemente nach aufsteigender Wahrscheinlichkeit sortiert sind.
Nachdem wir die Liste neu sortiert haben, fassen wir wieder die zwei kleinsten Wahrscheinlichkeiten zusammen. Das Ereignis BT mit der Wahrscheinlichkeit fassen wir mit dem Knoten mit der Wahrscheinlichkeit zusammen. Dies ergibt einen neuen Knoten mit der Wahrscheinlichkeit 
. Jetzt müssen wir die Liste neu ordnen. Die beiden Elemente mit den kleinsten Auftretenswahrscheinlichkeiten sind nun B3 und KAM, die wir zu einem neuen Element verschmelzen. Wir zeichnen also einen Knoten mit der Wahrscheinlichkeit 
und sortieren neu.
DW fassen wir nun mit dem Knoten nebenan zusammen, da diese die kleinsten Wahrscheinlichkeiten haben. 
plus ergibt 
. Jetzt müssen wir wieder neu sortieren, da die Liste nichtmehr geordnet ist. L fassen wir mit dem Knoten von B3 und KAM zusammen. Dies ergibt einen neuen Knoten mit der Wahrscheinlichkeit 
. Wir sortieren wieder nach aufsteigender Wahrscheinlichkeit.
Jetzt fassen wir die Elemente BS und SB zusammen, die zu einem Knoten mit der Wahrscheinlichkeit 
führen. In der sortierten Liste können wir nun die Knoten und zusammenfassen, was zu einem neuen Knoten mit führt.
Jetzt haben wir nur noch zwei Knoten, die wir zu einem neuen Knoten mit der Wahrscheinlichkeit 
ist gleich 1 zusammenfassen. Dieser Wurzelknoten umfasst alle Möglichkeiten, denn er hat die Wahrscheinlichkeit 1. Falls dies nicht der Fall ist, dann hast du entweder ein Ereignis vergessen oder dich verrechnet. Wir sind nun bei Schritt 4, dem Abbruch des Algorithmus, sobald nur noch ein Objekt in der Liste übrig ist.
Codewörter
Allerdings ist diese Darstellungsvariante etwas unüblich. Deshalb spiegeln wir den Baum noch horizontal, sodass die Wurzel oben steht und die Blätter unten. Wir haben nun einen Baum, aber die Codewörter fehlen noch. Diese bekommen wir, indem wir allen Zweigen links eines Knotens eine 0 und denen rechts eine 1 zuweisen. Bei der Codewort-Konstruktion beginnen wir immer in der Wurzel, die dann das höchstwertige Bit, also das Bit ganz links im Codewort darstellt.
Die fertigen Codewörter der einzelnen Bars können wir aus dem Baum ablesen. Sie lauten:
Die einzelnen Codewörter unterscheiden sich von den Codewörtern der Shannon-Fano-Codierung. Logisch, denn die Huffman-Codierung ist ja ein ganz anderes Verfahren mit anderen Schritten. Trotzdem liefern beide Codierungsverfahren einen optimalen Code.
Mittlere Codewortlänge
Jetzt können wir auch die mittlere Codewortlänge unserer Codierung berechnen. Allgemein sollte diese besser, also kleiner sein, als bei der Shannon-Fano-Codierung. Für die mittlere Codewortlänge erhalten wir den Wert
Bei der Shannon-Fano-Codierung hatte die mittlere Codewortlänge genau den gleichen Wert. Haben wir uns verrechnet? Nein, denn die mittlere Codewortlänge ist zwar oft etwas besser, sie kann aber auch gleich gut sein, wie das bei uns jetzt der Fall ist.
Weitere Eigenschaften der Huffman-Kodierung
Zuletzt noch zwei wichtige Eigenschaften des Huffman-Codes: Ein mit Huffman erzeugter Code ist genauso wie ein Shannon-Fano-Code immer präfixfrei, das heißt, dass kein Codewort den Beginn eines anderen Codewortes darstellen darf.
Zudem entsteht der Codebaum von den Blättern ausgehend und endet in der Wurzel. Diese Konstruktion wird auch „Buttom-Up“ genannt, denn im klassischen Bild eines Baumgraphen sind die Blätter unten und die Wurzel oben. Dies ist der große Unterschied zum Shannon-Fano-Code, der „Top-Down“, also von der Wurzel zu den Blättern konstruiert wird. Folglich ist der Huffman-Code zwar Überlegen in der mittleren Codewortlänge, aber bei vielen Blättern sehr umständlich bis fast unmöglich zu konstruieren, denn du musst sehr oft umsortieren und brauchst daher viel Speicher.