Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Einführung in die Informatik (EI)3.9.2 Huffman Code
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 61 Zeilen
- [Musik] hallo und herzlich willkommen tsum einer online vorlesung einführung in die
- informatik kurz dieses mal mit dem kapitel 392 half men codierungen dieses kapitel ist eine ergänzung zum kapitel 3.9 indem es allgemeinen
- komprimierungsverfahren ging bei komprimierungsverfahren unterscheidet man zwischen verfahren zur ad und ganz reduktion die verlustfrei arbeiten und
- verfahren zur irrelevant reduktion die verlust behaftet sind wir wollten uns einen algorithmus zur redundanz reduktion anschauen und das ist der
- rahmen code oder die hafen codierung prinzip der hafen codierung ist den am häufigsten vorkommenden symbolen die kürzesten code zuzuordnen und den
- seltensten vorkommenden symbolen die längsten codes vergleichbar mit dem maße alphabet dazu geht man folgendermaßen vor zuerst
- werden die an zahlen oder die häufigkeiten der symbole bestimmt also eine statistische analyse durchgeführt dann erzeugt man einen ausbalancierten
- kothbauer wir werden gleich sehen was das ist und wie das funktioniert und zum schluss ermittelt man die codes anhand dieses code baums und erstellt die neuen
- symbole und wenn alles gut läuft und das tut meistens erhält man damit wesentlich kompaktere und dateien die akkordierung kann man universell einsetzen die
- funktioniert eigentlich bei allen dateien gut man kann sie auch als zusätzliches verfahren nach einer verlust behafteten komprimierung zb bei
- mp3 ansetzen aber wir wollen uns mal genauer anschauen wie dieses verfahren denn prinzipiell funktioniert
- dazu nehmen wir als nächsten mal ein einfaches text beispiel hier in form des wortes superman erster schritt wir machen eine statistische analyse
- das heißt wir schauen wie oft welches zeichen vorkommt haben wir links an da haben wir zunächst mal dass es das kommt vier mal vor
- dann haben wir das das kommt zweimal vor das bekommt einmal vor dass er kommt sieben mal vor dass er das m
- das a und das einkommen jeweils einmal vor sie sehen ich habe das hier schon absteigend sortiert das war unser erster schritt eine statistische analyse im
- zweiten schritt erstellen wir einen so genannten ausbalancierten code baum und wir gehen nach folgendem prinzip vor wir nehmen immer die beiden symbole mit
- der geringsten häufigkeit und fügen die zu einem knoten zusammen wir beginnen also hier unten mit dem enden und immer
- und fügen die zusammen zu einem knoten in denen ich jetzt einfach mal n a und ich mag ihr hier jetzt die gesamtsumme hatte zweimal 1 ist 2
- damit haben wir schon mal abgearbeitet jetzt schaue ich wieder welche symbole wir betrachten es als ein symbol kommen jetzt am seltensten vor und die fasse
- ich wieder zusammen da hätte ich jetzt das m und dass er mit jeweils einmal die ich zusammen fassen kann wo ich die jetzt genau hin schreibe
- ist eigentlich ziemlich egal mach mal hier auf dieser seite m und r die zusammen zu mr und damit wir das nicht aus den augen
- verlieren damit zusammen dann auch wieder die anzahl 2 wir wiederholen den schritt es gibt jetzt das p mit einmal und es gibt das ohne zweimal und
- außerdem gibt es aber auch in are und mr mit jeweils zwei mal welche fasse ich jetzt zusammen ist egal ich entscheide mich hier dafür dass tee
- und das zusammenzufassen also p&o was ich hier zusammen mit der gesamtanzahl tragen so jetzt schaue ich was habe ich jetzt
- für an zahlen 3 2 und 2 und 4 das heißt die kleinsten zahl sind jetzt hier 2 und 2 damit fand sich jetzt diese beiden zusammen zu n a m und r und
- bekomme jetzt hier als gesamtsumme 4 jetzt habe ich hier drei und vier und ich habe hier in meiner buchstaben ist
- auch noch mal eine vier ich möchte jetzt dass es erst mal verstehen das heißt ich fasse das es mit insgesamt vier zusammen mit
- er halte es die uhr nun kann ich es jemals der beste raus streichen und 3 und 4 macht zusammen 7 so jetzt lasse ich s p und nmr
- zusammen mit der gesamtzahl von 11 und im letzten schritt fasse ich noch dass er zusammen
- mit dem gesamten baum den ich hier schon aufgebaut habe und erhalte da 18 und habe jetzt alle symbole zusammen also esp a m
- und er damit habe ich den balancierten code baum aufgebaut ein letzter schritt fehlt noch ich versehe jeweils den linke zweig mit
- einer null und den rechten zweig mit einer 1 so und jetzt kann ich die neue codierung für jedes zeichen damit angeben
- und wir sehen jetzt bekomme ich als es muss immer oben anfangen und diesen gesamten baum so weit nach unten laufen bis sich am ende beim entsprechenden
- buchstaben oder symbol angekommen bin das heißt ich fange oben anlaufe einmal nach links habe eine null und bin schon bei mir angekommen
- damit hat das neue codierung einen 0 dass es finden wir hier wir gehen erst einmal nach rechts als eine 1 dann nach links 1 0 und dann noch
- mal nach links noch mal eine null also 100 und der rest im schnelldurchlauf wenn wir vom ursprünglichen ascii codes ausgehend bei dem wir ein bald pro
- zeichen haben sich schon mal dass alle zeichen in ihrer neuen codierung kürzer sind und das effektive an der sache ist dass außerdem die zeichen die am
- häufigsten vorkommen nämlich dass er den aller kürzesten code haben das besteht nämlich nur noch aus einem bit nämlich denn 0 und zeichen die weniger häufig
- sind wie das a und das n und das m haben dann längere codes in diesem fall mit vier bit wenn jetzt also dieses wort superman in der neuen codierung
- darstellen sieht das so aus wir haben viermal es dass es ist 100 dann haben wir zwei ist 1 0 1 1 1 p
- und so weiter und schließlich das n jetzt was wir diese pc quenz wieder in beit zusammen
- und dann schauen wir mal wie viel zeit hier in summe haben zur man sieht als ende dezember
- deswegen fühlt man dann hinten noch ein vorbild dazu und damit sind wir mit der codierung fertig und wir haben jetzt ein zwei drei
- vier fünf sechs ursprünglich hatten wir 18 das ist doch schon eine deutliche komprimierung als wir reduzieren das
- ganze auf ein drittel jetzt ist die frage wie kann ich denn das wieder zurück kodieren dazu muss der code baum den wir erstellt haben
- mit übertragen werden das ist ein kleiner nachteil an diesem verfahren aber bei der üblichen größe von dateien macht das eigentlich wenig
- aus warum muss damit übertragen werden weil ich nämlich jetzt die zeichen zurückkehren will aus meiner biz sequenz diesen code baum
- entlang laufen muss versuchen wir die decodierung nachzuvollziehen es geht los mit einer 1 dh ich gehe hier einmal nach rechts dann kommt eine null
- jetzt gehe ich hier über und dann kommt noch eine null danke ich hier über und ich sehe jetzt bin ich unten an einem blatt angekommen
- und habe mein es sobald ich ein symbol wiederhergestellt habe fange ich wieder oben an als diese 1g wieder aus von hier oben
- ich folge wieder den pfad nach unten wieder eine null und wieder eine null und komme gleichermaßen wieder beim es raus und so
- weiter deswegen spielt es auch keine rolle wie ich am anfang meine symbole zusammengefasst habe weil ich diesen code baum mit übertrage und anhand
- dieses speziellen code baums immer wieder bei meinem ursprünglichen symbol herauskomme dass ein beispiel mit einer größeren code baum und einem kleinen
- text jetzt machen wir noch ein beispiel mit einem bild das funktioniert nämlich auch bei bildern und ich habe ja schon ein bisschen vorarbeit geleistet und
- habe schon mal nachgezählt wie viele pixel wie viel grüne pixel blaue pixel und wieviel orangene pixel es gibt und anhand dieser verteilung können wir
- jetzt wieder einen code baum erstellen wir versehen den wieder mit nullen und einsen und können jetzt neu kodieren das
- b ist jetzt in der neuen codierung eine 1 das g ist 0 1 das baby ist 000 und das wo ist 001 jetzt nach die neue regierung in die pixel eingetragen
- das sind insgesamt 97 bit und das entspricht 13 wobei wir das letzte bald wieder mit viel witz aufführen müssen die
- ursprüngliche dateigröße ist 64 byte von 64 auf 13 haben wir auch wieder eine ordentliche reduktion nämlich in etwa 20 ganze soll heißen unsere komprimierte
- datei hat nur noch die größe von 20 prozent der ursprünglichen datei damit sind wir am ende angekommen ich hoffe sie hatten spaß an dem kleinen einblick
- in die hafen kodierung und wir sehen uns beim nächsten mal wieder
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 …
DatenkompressionDatenkomprimierung [1] genannt – ist ein Vorgang, bei dem die Menge digitaler Daten reduziert wird. Dadurch sinkt der Speicherbedarf,
LauflängenkodierungDie Lauflängenkodierung (englisch run-length encoding, kurz RLE), auch die Lauflängencodierung, ist ein einfacher verlustfreier Kompressionsalgorithmus.
BildkompressionBildkompression ist die Reduzierung des Speicherbedarfs eines digitalen Bilds. Wie bei jeder Anwendung der Datenkompression geht es darum, …