Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Huffmancode: Informatik (deutsch)
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 71 Zeilen
- so hallo und herzlich willkommen auf meinem Blog blibtck ich mache heute endlich mal wieder ein Informatik Video heute soll es um folgendes gehen die
- hfman Codierung wenn man etwas codieren möchte dann brauche ich natürlich erstmal einen
- Text oder einen Datensatz den ich überhaupt codieren will ich habe mir jetzt hier z.B mal einen netten kleinen Satz ausgesucht den wahrscheinlich fast
- alle kennen milch macht munter was bedeutet in diesem Fall jetzt hier überhaupt codieren ich möchte den
- Satz den ihr hier jetzt vor euch seht in eine Abfolge von Einsen und Nullen umwandeln das bedeutet dass zum Schluss jeder Buchstabe eine eindeutige Abfolge
- von ein und Nullen zugeordnet wird die Haman Codierung hat einen bestimmten Vorteil es handelt sich dabei nämlich um eine präfixfi Codierung das
- heißt es entsteht ein Code der kein Präfix benötigt um z.B die einzelnen Buchstaben voneinander abzugrenzen aber das zeige ich euch zum Schluss dann auch
- noch mal genau gut wir möchten jetzt also diesen Satz kodieren fangen wir mal an was wir zuerst machen müssen ist die Buchstaben zu zählen und zwar wie oft
- jeder einzelne Buchstabe vorkommt ich habe das schon mal vorbereitet weil es eher langweilige Aufgabe ist ganz wichtig dabei ist dass man z.B
- Lehrzeichen mitzählt die möchte ich ja mit kodieren sonst könnte ich nie danach einen Satz bauen der Lehrzeichen enthält also ich habe jetzt hier links
- die Häufigkeit aufgelistet dann können wir jetzt an mit der mit dem codierprozess anfangen dazu
- bauen wir uns eine ganz bestimmte Datenstruktur auf nämlich eine Baumstruktur das Besondere ein Baumstruktur ist dass wir immer einen
- Wurzelknoten haben der existiert immer von jedem Knoten gibt es dann Kinderknoten in unserem Fall hier haben wir einen Binärbaum das heißt wir haben
- immer höchstens zwei Kindknoten und dann gibt es noch eine ganz besondere Art von Knoten nämlich die Blattknoten das sind die die überhaupt keine Kinder mehr
- haben die heißen Blattknoten gut dann fangen wir mal mit der hafcodierung an wir gehen wie folgt vor wir nehmen jetzt zuerst mal die
- Buchstaben mit der geringsten Häufigkeit wir können also z.B mal hier mit dem i und mit mit dem L anfangen wir schreiben uns die jetzt einfach mal hier unten auf
- die landen zum Schluss in einem Blattknoten das heißt die bekommen keine Kinder mehr deswegen kann ich die auch gleich schön unten an den Rand schreiben
- i und L landen hier der Vater Knoten dieser beiden Knoten bekommt jetzt die Häufigkeit von beiden zusammen also ein und ein ist
- 2 so machen wir jetzt weiter wir suchen jetzt die nächsten beiden Knoten aus unserer Liste hier links aus die die geringste Häufigkeit haben da werden wir
- z.B noch beim A und beim U machen wir dasselbe jetzt noch mal sieht fast genauso aus praktisch a und U landen wieder in den beiden Endknoten und oben
- zähle ich die Häufigkeit zusammen dann haben wir noch mal ein Pärchen bei denen das SE gut funktioniert z.B n und
- E so jetzt bleibt nur noch ein Knoten mit der Wahrscheinlichkeit 1 übrig nämlich
- das R das müssen wir jetzt mit der nächst kleineren Wahrscheinlichkeit zusammenpacken nämlich mit einer Z wo
- haben wir überhall eine zwei stehen wir haben z.B hier links beim C und H hätten wir noch eine zwe oder das Leerzeichen oder auch hier die Wahrscheinlichkeit
- oder die Häufigkeiten die wir schon zusammengefügt haben im Prinzip ist es jetzt euch überlassen mit was ihr jetzt das er zuammenhängt ich möchte aber
- möglichst schnell alle Buchstaben hier mal drin haben deswegen mache ich das mal mit dem
- C ich hänge das R und das C zusammen diesmal kommt aber oben keine zwei hin sondern eine 3 weil wir die Häufigkeiten 1 und 2 zusammen
- fügen das C und das haben wir jetzt verbraten so jetzt machen wir weiter h und T sind noch recht klein haben auch nur die Häufigkeit 2 machen wir die mal
- noch zusammen bisschen Platz
- sparen hier entsteht oben natürlich eine 4 weil 2 + 2 4 so jetzt ist ja schon gar nicht mehr so viel übrig wir haben jetzt hier unten noch die Häufigkeit 2 und
- oben die Häufigkeit 3 aber wir wollen ja immer die kleinsten Häufigkeiten zusammen machen das bedeutet dass wir die das zwei vom Leerzeichen mit einer
- zwei von diesen drei zweien zusammenbringen müssen das ist uns jetzt eigentlich im Prinzip uns selbst überlassen was wir da nehmen was ist am
- geschicktesten machen wir vielleicht die hier mal das soll ein Symbol für leerrzeichen sein so z und Z gibt wieder vier
- gut zwei ist weg so jetzt haben wir noch eine drei übrig hier oben aber noch zwei zweien hier übrig und wir möchten wie vorhin schon gesagt immer die
- niedrigsten Häufigkeiten zusammenbringen das heißt in dem Fall müssen erstmal die beiden zweien hier zusammengebracht werden dann steht auch wieder eine
- vi so jetzt haben wir nichts mehr was kleiner ist als dre deswegen können wir jetzt die beiden Dreier noch zusammenbringen das heißt wir haben hier
- noch ein m und 3 und 3 6 so jetzt sind die Vierer die kleinsten das heißt wir verbasteln mal wieder die
- viere zusammen ich nehme die beiden linken hier es entsteht also eine die kleinste Kombination Kombinationsmöglichkeit jetzt wäre die 4
- und die 6 daraus entsteht eine Zeh und dann bleibt ja gar nicht mehr viel übrig dre vielleicht no kurz abhaken es
- entsteht jetzt hier noch eine 18 zum Schluss und diese 18 ist für die Kodierung auch immer unser Einstiegspunkt die 18 ist nämlich der
- Wurzel des Baums der jetzt entstanden ist wir haben jetzt unseren hffmanbaum eigentlich vollständig aufgebaut es
- fehlt noch eine Kleinigkeit die uns doch recht weiterhilft beim Codieren wir machen jetzt folgendes immer wenn von einem Knoten eine verestelung nach links
- weggeht schreiben wir da eine ein hin und immer wenn Sie nach rechts weggeht eine Null das bedeutet hier links eine ein rechts eine Null und das machen wir
- jetzt kurz für alle verestelungen im Prinzip ist es egal also ihr könntet es auch andersrum
- machen das Wichtige ist dass ihr es konsistent macht also solltet ihr es andersrum machen müsst ihr es auch wirklich immer anders herum
- machen gut und das war's schon ich fragt euch jetzt vielleicht wie will ich jetzt mit diesem komischen Baum hier überhaupt irgendwas anfangen eigentlich ist es
- ganz einfach wenn ich jetzt z.B das M codieren möchte mache ich folgendes ich schreib hier mal m hin weil wir das M machen so die 18 ist wie vorhin gesagt
- schon unser Startpunkt und wo möchte ich hin ich möchte zum m das befindet sich hier das also mache ich folgendes ich laufe
- jetzt diesen Baum entlang und laufe zum m das heißt ich laufe nach rechts nach rechts und wieder nach links daraus ergibt sich dann eine Nummer nämlich
- 0 1 das bedeutet das M kann ich mit 01 codieren wir können ja gleich mal einfach das Wort Milch vielleicht
- komplett machen damit ihr ein bisschen mehr Übung bekommt wir machen mal das i das i befindet sich muss ein bisschen suchen hier unten das heißt wir laufen
- wir den ganzen Baum entlang zum i also 0 1 1 1 und ihr seht jetzt hier schon die Codewörter die so entstehen die müssen
- nicht die gleiche Länge haben das liegt eben daran dass es sich um einen präfixfien Code handelt machen wir vielleicht noch mal das
- L wo ist das L l hier unten gleich neben i sieht also fast genauso aus upsa 0 10 10 genau jetzt haben wir schon drei Buchstaben wir können ja mal versuchen
- etwas rückwärts zu codieren beispielsweise diese Zeichenfolge hier die haben wir auch was wir also jetzt
- machen ist wir haben jetzt nicht das Ziel vorgegeben sondern den Weg den wir laufen müssen das bedeutet wir starten wieder bei der 18 laufen Richtung der 1
- also laufen wir nach links danach kommt eine ull das heißt wir folgen der ull danach kommt wieder eine 1 danach kommt wieder eine ull das bedeutet wir landen
- beim E machen wir das ganze vielleicht noch mal wir fangen wieder bei der 18 an gehen Richtung 0 landen bei der Z danach
- kommt eine ein also landen wir bei der VI hier unten danach kommen zwei Nullen das heißt ich laufe ull und noch mal Null und lande beim
- U ich denke damit solltet ihr halbwegs verstanden haben wie der Haman Code funktioniert wenn es noch Fragen gibt könnt ihr die natürlich gerne in den
- Kommentaren äußern oder mir auch eine PM schreiben und ich habe jetzt noch für euch eine kleine Übung
- vorbereitet nämlich das hier oben einmal eine Zahlenfolge und einmal ein Wort und eure Aufgabe wäre es jetzt das Wort tauche zu codieren und diese
- einzeln und Nullen Folge die ihr da oben rechts noch oder in der Mitte noch seht zu dekodieren die Ergebnisse findet ihr unter dem Video damit ihr das mit euch
- abgleichen könnt noch mal kurz eine Zusammenfassung halfman Code wird verwendet um etwas zu codieren oder zu decodieren natürlich auch wenn ich etwas
- mit dem Hafen Code codieren möchte muss ich einen Baum aufstellen seht ihr unten der hfman Code ist ein Präfix ist ein
- präfixfies codierverfahren es gehen keine Daten dabei verloren und soweit ich weiß wird der z.B auch bei der sipkprimierung
- angewendet ich hoffe durch das Video ist euch das Vorgehen etwas klarer geworden ich finde sowas macht auch relativ viel Spaß vielleicht auch mal zu
- programmieren wenn ihr dazu Lust habt oder ihr könnt auch auch Geheimbotschaften mit euren Freunden jetzt in eins und Nullen hier schicken
- wenn ihr dazu Lust habt wichtig ist wenn ihr das mit euren Freund macht die müssen natürlich auch den Baum kennen das heißt wenn ich etwas mit diesem Code
- codiere muss der Baum auch immer mit weitergegeben werden sonst kann ich es nicht mehr entschlüsseln gut ich hoffe es hat euch Spaß gemacht das war's von
- mir bis zum nächsten Mal tschüss
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 …
DatenkompressionDatenkomprimierung [1] genannt – ist ein Vorgang, bei dem die Menge digitaler Daten reduziert wird. Dadurch sinkt der Speicherbedarf,
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 …