Top 6 Fehler beim Huffman-Code
Robert Steffens
https://www.youtube.com/watch?v=jLrJ8lKNoNU

Transkript (automatisch erstellt)

0:00 In diesem Video geht es um die Erstellung einer Huffman-Codierungstabelle basierend auf der Buchstabenhäufigkeit von diesem Text, den ich jetzt mal lieber nicht vorlese. Dabei
0:08 werde ich auf die sechs häufigsten Fehler eingehen, die ich in Arbeiten immer wieder sehe. Los geht's. Im Gegensatz zur Codierung von Buchstaben in ASCII ist die Länge der Codierung
0:17 der einzelnen Symbole beim Huffman-Code variabel. So soll Speicherplatz gespart werden. Symbole, die häufig vorkommen, sollen einen kurzen Code bekommen, die seltenen hingegen einen langen.
0:26 Dazu ist es natürlich erst einmal notwendig, die Buchstabenhäufigkeit festzustellen. Los geht es mit der Frequenzanalyse. Diese macht das, was der Name vermuten lässt: Jeder Buchstabe im
0:34 Text wird gezählt und in einer Liste notiert. Ein Fehler, den ich dabei immer wieder sehe, ist, dass das Leerzeichen als Symbol nicht mit aufgenommen wird. In unserem Beispiel symbolisiere
0:44 ich das mit einem Unterstrich. Der zweite Fehler, den ich manchmal sehe, ist, dass die Groß- und Kleinschreibung ignoriert wird. Jedoch müssen diese zur Unterscheidung unterschiedlich codiert
0:51 werden. In diesem Fall müssen wir also das kleine 'o' von dem großen 'O' unterscheiden und beide in unserer Buchstabenhäufigkeitsliste aufführen. Mit dieser Liste der Häufigkeiten der einzelnen
1:00 Buchstaben erstellen wir nun den Huffman-Baum. Dieser ist eine spezielle Art von Binärbaum. Um diesen zu erzeugen, werden unsere Buchstaben als triviale Bäume dargestellt, also als Baum,
1:09 der aus nur einem einzigen Knoten als Wurzel besteht. Diese Knoten werden später unsere Blätter vom Huffman-Baum. Die Blätter, also die äußersten Knoten, repräsentieren
1:17 die zu codierenden Buchstaben. Das ist ein großer Unterschied zum Baum des Morse-Codes, wo auch innere Knoten Buchstaben sind. Nun wird aus den einzelnen Teilbäumen genau ein
1:26 Huffman-Baum zusammengesetzt. Neben dem Buchstaben besitzen die Knoten noch eine weitere Eigenschaft, nämlich die Buchstabenhäufigkeit, die wir im vorigen Schritt gezählt haben. Es werden nun also
1:35 die zwei Knoten mit den geringsten Häufigkeiten verbunden. In unserem Beispiel sind es das Ausrufezeichen und das große 'O'. Diese werden verbunden, indem ein Vorgänger erzeugt wird,
1:44 der jeweils mit seinen Nachfolgern, also unseren Knoten, verbunden wird. Dabei nimmt der neue Knoten die summierte Buchstabenhäufigkeit seiner Nachfolger an. Bei uns ist das die Drei. Jetzt
1:53 werden die nächsten Knoten, genau genommen die Wurzeln der verbleibenden Bäume, verbunden. In unserem Fall ist das die Drei vom Leerzeichen und die Wurzel des gerade zusammengefügten
2:02 Teilbaums mit der Häufigkeit Drei. Diese werden verbunden, indem ein neuer Vorgänger erzeugt wird, mit der Häufigkeit Sechs. Hier komme ich nun zu dem Fehler, den ich am häufigsten beobachte:
2:10 Es werden zwei Knoten verbunden, die nicht die geringste Häufigkeit aufweisen. Anstatt der Sechs müsste ich das 'U' mit der Häufigkeit Vier und das 'A' mit der Häufigkeit Fünf verbinden,
2:18 da diese Zahlen kleiner als die Sechs sind. An dieser Stelle passiert dieser Fehler häufig, weil geglaubt wird, dass immer mit dem Knoten weitergearbeitet werden muss,
2:27 der zuletzt erzeugt wurde. Das ist nicht richtig. Es müssen immer die Knoten gewählt werden, die die geringste Häufigkeit aufweisen. Dabei ist es egal, ob dies ein neu erzeugter Vorgängerknoten ist oder
2:37 triviale Bäume, die nur einen Knoten haben. Also merke: Immer die Häufigkeit von allen Wurzeln untersuchen! Weiter geht es erstmal mit einem Fehler, den ich häufig sehe: Bereits verbundene
2:47 Knoten sollen erneut verbunden werden. In meinem Tool führt das zu einer Fehlermeldung, auf Papier gezeichnet führt es dazu, dass es plötzlich kein binärer Baum mehr ist, weil es plötzlich mehr
2:56 als einen Vorgänger gibt oder weil ein Knoten plötzlich drei oder mehr Nachfolger hat. Weiter geht's. Als Nächstes muss ich den Knoten mit der Häufigkeit Sechs verbinden. Als Partner kommen
3:06 zwei Knoten in Betracht. Diese markiere ich hier einmal mit Hellblau: einmal den Teilbaum mit der Häufigkeit Neun oder der Knoten vom Buchstaben 'O', ebenfalls mit der Häufigkeit Neun. Egal,
3:15 welchen der beiden Knoten ich wähle, es ergibt sich jedes Mal ein gültiger Huffman-Baum. Wir spielen das mal mit beiden Varianten nebeneinander durch. Auf der rechten Seite des Monitors wähle
3:23 ich die Neun vom Buchstaben 'O' und auf der linken Seite den Teilbaum mit der Häufigkeit Neun. Jetzt müssen in beiden Beispielen noch die Buchstabenhäufigkeit Neun mit der Zehn verbunden
3:32 werden. Einmal ist es das kleine 'o' auf der linken Seite, einmal ist es der Teilbaum auf der rechten Seite. Nun müssen noch die letzten beiden Wurzeln miteinander verbunden werden, nämlich die
3:40 Häufigkeit Fünfzehn mit der Neunzehn. Die oberste Wurzel mit der Vierunddreißig ist nun auch die Wurzel von unserem Huffman-Baum. Nachdem alle Teilbäume zu einem zusammengefügt sind, müssen
3:50 die Kanten noch benannt werden. Dabei ist es nur wichtig, dass die linken und rechten Nachfolger einheitlich benannt werden, also zum Beispiel links immer die Null und rechts immer die Eins.
3:59 Hier sehe ich eigentlich nur Fehler, wenn der Baum ganz wild gezeichnet ist und man den Überblick verliert. Daher der Pro-Tipp: Eine Skizze auf dem Schmierblatt, auch Konzeptpapier genannt, hilft,
4:08 einen schönen Baum zu zeichnen. Der Huffman-Baum ist fertig, und hier kommen wir zum nächsten Fehler. Denn in der Einleitung habe ich gesagt, dass wir die Codierungstabelle haben wollen. Zwar
4:17 können wir die Codierung im Baum schon ablesen, aber es soll die Tabelle angegeben werden. Dabei verfolgt man von der Wurzel des Baumes die Kanten bis zu den Blättern, in denen die Buchstaben
4:26 stehen. Dabei werden die Bezeichnungen der Kanten, die abgelaufen werden, als Codewort in unserer Tabelle notiert. Ganz selten sehe ich den Fehler, dass nicht bei der Wurzel begonnen wird, sondern
4:35 bei den Blättern, um das Codewort abzulesen. Mit dem Wissen sollte es nun ganz einfach sein, selbst einen Huffman-Baum zu erstellen. Ich verweise mal auf meine Playlist hier oben rechts,
4:43 dort habe ich für ein paar Buchstabenhäufigkeiten einen Huffman-Baum erstellt.