Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Huffman-Kodierung
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 36 Zeilen
- Nun schauen wir uns als nächstes die Hoffman Codierung an. Die Idee hier ist, dass Zeichen, die häufiger vorkommen, mit einer kurzen oder kürzeren Bitfolge
- codiert werden. Das hat natürlich zurfolge, dass wir zu unterschiedlichen Wortlängen in unserer Codierung kommen. Vorgeschlagen wurde das Verfahren
- bereits 1952 durch David Haffman. Allerdings arbeit äh arbeitete er bereits auf Inspirationen von Vorgängerarbeiten.
- Das Vorgehen ist hier so, wir erstellen zunächst mal eine Codeabelle, in der wir die relativen Häufigkeiten der ähm Symbole eintragen. Und ähm das heißt,
- wir müssen schon die Häufigkeiten kennen, beispielsweise, weil wir die kennen für ein Alphabet oder eben für die gesamte Nachricht. Und dann
- konstruieren wir einen Baum für die Zeichen dieses Alphabets, wobei wir bei der Konstruktion des Baumes darauf achten, dass diejenigen Zeichen, die
- häufig vorkommen, weiter oben im Alphabet stehen. Und die Kanten in diesem Baum stehen dann für die Codierungszeichen. Das wird in der
- Praxis später ein Binärbaum sein, wo wir die Kanten mit 0 und 1 beschriften. Das funktioniert dann so, wir haben also ein Alphabet und zugehörig die relativen
- Häufigkeiten und die Summe der Häufigkeiten für alle Zeichen in unserem Alphabet muss natürlich nachher ein sein. Jetzt generieren wir für jeden
- Knoten in unserem für uns für jedes Zeichen in unserem Alphabet einen Knoten und mal merken uns für den Knoten die relative Häufigkeit und sortieren diese
- Knoten aufsteigend. Also ganz vorne steht derjenige Knoten, der die geringste relative Häufigkeit hat. und ganz hinten der Knoten mit der höchsten
- relativen Häufigkeit. Und nun kommt ein Algor, der eigentliche Algorithmus zur Konstruktion des Haffmanbaums. Dabei fassen wir jeweils die ersten beiden
- Knoten in unserer sortierten Liste zusammen und bauen daraus einen Teilbaum und das ergibt dann einen neuen Elternknoten und dessen relative
- Häufigkeit ergibt sich aus der Summe der beiden Kinder. Und diesen Teilbaum legen wir wieder in unsere sortierte Liste rein und machen so lange weiter, bis in
- der Liste nur noch einziger Baum drin steckt. Wie sieht das in dem Beispiel aus? Wir haben jetzt hier ein Alphabet bestehend aus den Zeichen ABC mit den
- hier angegebenen relativen Häufigkeiten. Also das kleine D tritt mit einer Wahrscheinlichkeit von 10 % in unseren Nachrichten auf. Dann haben wir die hier
- in eine Liste einsortiert, die sortiert ist. Vorne die Elemente mit geringer relativer Häufigkeit und hinten die Elemente mit hoher relativer Häufigkeit.
- Dann wurden die ersten beiden Elemente zusammengefasst zu einem Teilbaum. Es gibt also einen neuen Wurzelknoten, wo D das linke Kind und C das rechte Kind
- ist. Das wäre dieser Teilbaum und dessen relative Häufigkeit berechnet sich aus der Summe der beiden Kinder der relativen Häufigkeiten. Das wäre 0,1 +
- 0,2= 0,3. Das Minus hier steht nur dafür, dass dieser Knoten selber kein Zeichen codiert, sondern ein innerer Knoten im Baum ist. Diesen neu
- konstruierten Baum fügen wir dann wieder in die Liste ein und zwar sortiert an der richtigen Stelle. Wir sehen jetzt, wir haben hier noch einen Knoten mit
- geringerer relativer Häufigkeit und dann einen mit höherer relativer Häufigkeit, deswegen steht er hier in der Mitte. Und auch hier fassen wir jetzt wieder die
- ersten beiden zusammen. Das ergibt diesen Baum hier oben mit der kombinierten relativen Häufigkeit von 0,55, was größer ist als 0,54 für das
- kleine A. Und im letzten Schritt bauen wir das noch mit ein und haben dann unseren vollständigen Baum aufgebaut. Und jetzt sehen wir, an die Kanten habe
- ich jetzt noch zusätzlich die ähm Codierungszeichen eingetragen. Also hier auf den linken Teilbaum kommt man mit einer 0, den rechten Teilbaum mit einer
- 1. Und was man hier schon sehen kann, das Zeichen mit der größten relativen Häufigkeit steht hier sehr weit oben im Baum und um es zu erreichen, muss man
- nur eine einzige Kante durchlaufen, während diejenigen Zeichen, die eine geringe relative Häufigkeit haben, weiter unten im Baum stehen und wir
- müssen über mehrere Kanten laufen, um zu ihnen zu kommen. Das nutzen wir jetzt sowohl bei der Codierung als auch bei der Dekodierung aus. Wir starten mit der
- Codierung. gegeben ist also ein Symbol und wir suchen jetzt den Pfad, der von der Wurzel bis zu dem Symbol, das codiert werden soll, führt und sammeln
- die entsprechenden Kantenlabel zusammen. Wenn wir also beispielsweise das kleine A codieren wollen, dann können wir hier vom Wurzelknoten einfach die Null
- entlang laufen und haben unser Symbol gefunden. Folglich wird das Zeichen A mit 0 codiert. Und wenn wir auf dem auf der anderen Seite das kleine D codieren
- wollen, dann starten wir auch in der Wurzel. müssen hier zweimal die ein entlang laufen und dann einmal die 0, um beim Knoten D herauszukommen. Das heißt
- 1 10 ist die Codierung für den Buchstaben klein D. Und wie sieht's jetzt beim Dekodieren aus? Im Prinzip ganz genauso. Als Eingabe erhalten wir
- eine Bitfolge und auch die arbeiten wir von der Wurzel beginnend ab, wobei wir anhand der Bits entscheiden, ob wir das linke oder rechte Kind auswählen. Also
- haben wir z.B. die Folge 10. Dann starten wir am Wurzelknoten, laufen die Kante 1 und dann die Kante 0 zu entlang, kommen beim Knoten B heraus und wissen
- also, dass der das codierte Zeichen dem kleinen B entspricht. M.
Zum Nachlesen
Huffman-KodierungDie Huffman-Kodierung ist eine Form der Entropiekodierung, die 1952 von David A. Huffman entwickelt und in der Abhandlung A Method for the Construction of …
Arithmetisches KodierenDie arithmetische Kodierung ist eine Form der Entropiekodierung, die bei der verlustfreien Datenkompression verwendet wird. Sie erzielt Kompressionsraten …
PräfixcodeAls Präfixcode wird ein Code bezeichnet, der die Fano-Bedingung erfüllt: Kein Codewort des Codes ist Präfix eines anderen Codewortes. Anders ausgedrückt darf …
DatenkompressionDatenkomprimierung [1] genannt – ist ein Vorgang, bei dem die Menge digitaler Daten reduziert wird. Dadurch sinkt der Speicherbedarf,