Einführung in die Informatik (EI)3.9.2 Huffman Code
Prof. Dr. Miriam Föller-Nord
https://www.youtube.com/watch?v=ZTUe6CLWfrc

Transkript (automatisch erstellt)

0:00 [Musik] hallo und herzlich willkommen tsum einer online vorlesung einführung in die
0:14 informatik kurz dieses mal mit dem kapitel 392 half men codierungen dieses kapitel ist eine ergänzung zum kapitel 3.9 indem es allgemeinen
0:24 komprimierungsverfahren ging bei komprimierungsverfahren unterscheidet man zwischen verfahren zur ad und ganz reduktion die verlustfrei arbeiten und
0:34 verfahren zur irrelevant reduktion die verlust behaftet sind wir wollten uns einen algorithmus zur redundanz reduktion anschauen und das ist der
0:44 rahmen code oder die hafen codierung prinzip der hafen codierung ist den am häufigsten vorkommenden symbolen die kürzesten code zuzuordnen und den
0:55 seltensten vorkommenden symbolen die längsten codes vergleichbar mit dem maße alphabet dazu geht man folgendermaßen vor zuerst
1:05 werden die an zahlen oder die häufigkeiten der symbole bestimmt also eine statistische analyse durchgeführt dann erzeugt man einen ausbalancierten
1:17 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
1:28 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
1:42 funktioniert eigentlich bei allen dateien gut man kann sie auch als zusätzliches verfahren nach einer verlust behafteten komprimierung zb bei
1:51 mp3 ansetzen aber wir wollen uns mal genauer anschauen wie dieses verfahren denn prinzipiell funktioniert
2:03 dazu nehmen wir als nächsten mal ein einfaches text beispiel hier in form des wortes superman erster schritt wir machen eine statistische analyse
2:16 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
2:27 dann haben wir das das kommt zweimal vor das bekommt einmal vor dass er kommt sieben mal vor dass er das m
2:45 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
2:59 zweiten schritt erstellen wir einen so genannten ausbalancierten code baum und wir gehen nach folgendem prinzip vor wir nehmen immer die beiden symbole mit
3:09 der geringsten häufigkeit und fügen die zu einem knoten zusammen wir beginnen also hier unten mit dem enden und immer
3:24 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
3:40 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
3:50 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
4:00 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
4:12 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
4:23 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
4:32 und das zusammenzufassen also p&o was ich hier zusammen mit der gesamtanzahl tragen so jetzt schaue ich was habe ich jetzt
4:49 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
5:03 bekomme jetzt hier als gesamtsumme 4 jetzt habe ich hier drei und vier und ich habe hier in meiner buchstaben ist
5:14 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
5:33 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
5:52 zusammen mit der gesamtzahl von 11 und im letzten schritt fasse ich noch dass er zusammen
6:11 mit dem gesamten baum den ich hier schon aufgebaut habe und erhalte da 18 und habe jetzt alle symbole zusammen also esp a m
6:35 und er damit habe ich den balancierten code baum aufgebaut ein letzter schritt fehlt noch ich versehe jeweils den linke zweig mit
6:49 einer null und den rechten zweig mit einer 1 so und jetzt kann ich die neue codierung für jedes zeichen damit angeben
7:07 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
7:15 buchstaben oder symbol angekommen bin das heißt ich fange oben anlaufe einmal nach links habe eine null und bin schon bei mir angekommen
7:26 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
7:43 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
8:01 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
8:12 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
8:22 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
8:36 darstellen sieht das so aus wir haben viermal es dass es ist 100 dann haben wir zwei ist 1 0 1 1 1 p
9:14 und so weiter und schließlich das n jetzt was wir diese pc quenz wieder in beit zusammen
9:25 und dann schauen wir mal wie viel zeit hier in summe haben zur man sieht als ende dezember
9:34 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
9:45 vier fünf sechs ursprünglich hatten wir 18 das ist doch schon eine deutliche komprimierung als wir reduzieren das
10:14 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
10:31 mit übertragen werden das ist ein kleiner nachteil an diesem verfahren aber bei der üblichen größe von dateien macht das eigentlich wenig
10:43 aus warum muss damit übertragen werden weil ich nämlich jetzt die zeichen zurückkehren will aus meiner biz sequenz diesen code baum
10:53 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
11:05 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
11:16 und habe mein es sobald ich ein symbol wiederhergestellt habe fange ich wieder oben an als diese 1g wieder aus von hier oben
11:30 ich folge wieder den pfad nach unten wieder eine null und wieder eine null und komme gleichermaßen wieder beim es raus und so
11:41 weiter deswegen spielt es auch keine rolle wie ich am anfang meine symbole zusammengefasst habe weil ich diesen code baum mit übertrage und anhand
11:53 dieses speziellen code baums immer wieder bei meinem ursprünglichen symbol herauskomme dass ein beispiel mit einer größeren code baum und einem kleinen
12:04 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
12:16 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
12:28 jetzt wieder einen code baum erstellen wir versehen den wieder mit nullen und einsen und können jetzt neu kodieren das
12:54 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
13:30 das sind insgesamt 97 bit und das entspricht 13 wobei wir das letzte bald wieder mit viel witz aufführen müssen die
13:52 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
14:23 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
14:32 in die hafen kodierung und wir sehen uns beim nächsten mal wieder