Der Huffman Code | Algorithmen und Datenstrukturen

[@absence9443]

wenn's jmd in Python haben will, zeigt auch benötigten Speicherplatz mit und ohne Huffman-Kodierung an: def huffman(message): #initilialise stack stack = sorted([Node(val=a,k=b) for a,b in Counter(message).items()],key=lambda x:x.k,reverse=True) #create huffman tree while len(stack)>1: x=stack.pop() y=stack.pop() stack.append(Node(val=None,k=x.k+y.k,left=x,right=y)) stack.sort(key=lambda x:x.k,reverse=True) #turn tree into translation dict translator = dict() def convert(node,s=''): if node.left: convert(node.left,s+'0') if node.right: convert(node.right,s+'1') elif node.val: translator[node.val]=s convert(stack[0]) result=''.join(translator[char] for char in message) print(f'') print(f'') print(f'') return result

[@Ufuk646]

Wie leicht es ist durch gute Erläuterung, bin echt begeistert

[@Florian.Dalwigk]

Danke dir :)

[@dominichauff5470]

Genau was ich gebraucht habe. Nicht mehr und nicht weniger. Daumen hoch

[@Florian.Dalwigk]

Top, das freut mich :)

[@JustAnAliasBro]

Hast mir gerade so den Arsch gerettet. Hab Prüfung morgen und hatte keine Ahnung. Erklärungen sind Präzise , Animationen sehr gut, Sehr gute Sprechstimme und alles in allem 1+ für das vid. Danke

[@Florian.Dalwigk]

Vielen Dank :) Viel Erfolg für die Prüfung morgen!

[@janniswildermuth1499]

Super erklärt. Das die intuitive Variante mit verglichen wurde finde ich auch toll, sonst wäre die erste Frage bei vielen natürlich direkt, ob das denn überhaupt was bringt.

[@anna-lenaklaas77]

Sehr gut erklãrt. Versteht sogar ein Boomer

[@Florian.Dalwigk]

Vielen Dank Anna :)

[@rayvvenn]

hahaha

[@louispeter6138]

das Video ist voll gut!! Simple und einfach erklärt, sodass man es auch wirklich verstehen kann :) danke dir

[@Florian.Dalwigk]

Gerne :)

[@anonym9713]

Hätte man auch SS und PP als Block nehmen können? Die kommen ja immer nur zusammen vor. So wäre meine Codewort nur 14 Zeichen lang. Oder lässt sich das nur mit gleichlangen Blöcke machen?

[@BA-pq1vr]

Eine Frage: Hätte man auch die Buchstaben I und S verbinden können? Also das dann der Baum symmetrisch ist…

[@denizonat4651]

was kurzes dazu gelernt. Kannst du das programmieren in c und den code erklären?

[@Garkolym]

Danke für die Erklärung

[@Florian.Dalwigk]

Sehr gerne und ein frohes neues Jahr 2024 :)

[@Garkolym]

@@Florian.Dalwigk dir auch frohes neues

[@IA7mD]

VOICE CRACK sein vater, aber vielen dank fürs video

[@Florian.Dalwigk]

Lol, gerne ;)

[@giama4312]

Super video. Eine Frage hätte ich allerdings noch. Wieso entscheiden wir uns, dass die 1 auf der rechten Seite im Baum steht und nicht auf der linken?

[@yrrebwarts93]

Das interessiert mich auch sehr

[@1aboPLZ]

das ist egal jedoch muss das während des Kodierens einheitlich sein

[@matthiasmeyer1]

Danke!! Das ist echt gut erklärt

[@Florian.Dalwigk]

Das freut mich 🙂

[@TheCelebreties]

Vielen Dank! Mehr kann man dazu nicht sagen :D

[@Florian.Dalwigk]

Danke :)

[@sorenheege2389]

Super Erklärvideo!

[@Florian.Dalwigk]

Danke :)

[@oida10000]

Sollte man den Hufman-Code über den gesamten Text oder über einzelne Wörter machen? Wieviel Platz nimmt der Baum selbst weg? Was ist die Verarbeitungslatency beim Dekodieren?

[@1aboPLZ]

1. es macht mehr Sinn den ganzen Text zu kodieren weil der je länger der Text desto geringer der Informationsgehalt pro Zeichen ist 2. kommt auch wieder auf den informationsgehalt an. Ist dieser sehr gering nimmt die Tabelle/der Baum sehr wenig Platz weg im Verhältnis zum Code 3. keine Ahnung was du meinst bin Schüler. der Algorithmus hat glaub ich eine lineare Laufzeit

[@cntrix2047]

mit welchem programm hast du das video erstellt?

[@jensharbers5620]

Super video, muss anmerken, das ich im Studium leider zu spät den Sinn von manchen Datenstrukturen und anderen gesehen habe

[@Florian.Dalwigk]

Besser spät als nie ;)

[@MiauRizius]

Cooles und vorallem interessantes Video.

[@Florian.Dalwigk]

Vielen Dank 🙂🙃

[@MiauRizius]

@@Florian.Dalwigk Aber wie bekommt man wieder die Buchstaben raus? Wenn deine Binärzahlen für Buchstaben mal so und mal so lange sind?

[@Florian.Dalwigk]

Der Baum wird mit übertragen. Daraus kann man die Nachricht wieder herstellen.

[@MiauRizius]

@@Florian.Dalwigk Okay

[@paulr5111]

super erklärt tolles Video!

[@Florian.Dalwigk]

Danke dir 😊

[@tim265]

Wieso wird der Baum nicht so aufgebaut, dass er einem AVL Baum ähnelt? Also in deinem Beispiel I und S unter der Wurzel stehen und dann M und P jeweils z.B. beide unter I? Dann wären die Binärcodes auch entsprechend kürzer?

[@tristan7715]

Habe ich mich auch gefragt

[@1aboPLZ]

dann wäre das nicht prefixfrei

[@3333927]

Dafür muss aber das Wort bekannt sein. Denn wenn man nun ein Wort nur mit den Buchstaben MISP (z.B. Missisippi) so codiert, funktioniert der Code nicht mehr, wenn man das Wort "Illinois"auslesen will. Für jedes Wort mit anderen Buchstaben, braucht man also einen Schlüsselcode, der einem zuvor sagt, welche Buchstaben wie oft in dem Wort vorkommen.

[@1aboPLZ]

ich verstehe nicht ganz was du meinst aber falls es dir nicht klar ist: die Tabelle/der Baum muss mit übertragen werden

[@3333927]

@@1aboPLZ Also man muss dann für jedes Wort mitübertragen, wie der jeweilige vorkommende Buchstabe kodiert wurde? Bei Missisippi hätte man dann mit dem Huffmancode 21 Bits + 4x8 Bits für ASCII, also in der Summe 53 Bits anstatt 88 Bits? Beispiel: M: 01001101 -> 100 I: 01001001 -> 0 S: 01010011 -> 11 P: 01010000 -> 101 Also zuerst muss man die Zuweisung machen, dann das Wort im zugewiesenen Binärcode: 01001101100 | 010010010 | 0101001111 | 01010000101 || 100011110111101011010 Das wären dann 62 Bits, anstatt 88 Bits. Und das muss man dann für jedes einzelne Wort immer wieder neu machen, weil ja jedes Wort unterschiedlich ist. Bei Wörtern, die keine sich wiederholenden Buchstaben haben, hätte man dann sogar einen längeren Code als mit der ASCII Tabelle. Mir ergibt sich der Sinn davon nicht.

[@1aboPLZ]

wie das kodiert wird muss einmal für die Nachricht übertragen werden. Man kann aber auch sagen man einigt sich auf durchschnittliche Wahrscheinlichkeiten die die Buchstaben in der entsprechenden Sprache haben. Das heißt für Nachrichten mit hoher Informationsdichte macht keinen Sinn alle Kodierungen zu übertragen

[@anonymunterwegs3047]

Ganz klasse!

[@Florian.Dalwigk]

:)

[@anonymunterwegs3047]

@@Florian.Dalwigk 😘❤

[@jemaripano8078]

Sehr gutes video

[@Florian.Dalwigk]

Danke

[@luisa_laurent]

5:15 Hallo, ich bin Marcel Davis

[@Florian.Dalwigk]

;)

[@_inetuser]

🫱🏿‍🫲🏼

[@whogotpwned]

Sehr gut erklärt. Deine Darstellungen und Animationen sind echt gut. Top.

[@Florian.Dalwigk]

Vielen Dank für dein Feedback, das freut mich sehr :)

[@inf0rmix2011]

Find ich auch ! vielen dank dafür!!!!

[@dragonminja246]

Muss schon sagen, das war echt gut :D

[@Florian.Dalwigk]

Danke 😊

[@MrRicsto]

Servus, danke für das Video! Wäre es auch richtig wenn man in der Darstellung des Baumes praktisch das I auf der rechten Seite stehen hätte? Also sodass man für I auf 1 kommt und für zb S auf 01 statt 11? Danke im Voraus^^

[@Florian.Dalwigk]

Ja, würde auch gehen.

[@MrRicsto]

@@Florian.Dalwigk Alles klar, vielen dank :)

[@Florian.Dalwigk]

Gerne!

[@toniii1105]

Sehr gut erklärt mit einer echt angenehmen Stimme. Danke!

[@Florian.Dalwigk]

Gerne und vielen Dank für dein Feedback :)

[@nterior9245]

Super erklärt. Gerne mehr solcher Videos

[@claudiomondillo5802]

Danke für das Video. Ich habe dazu noch eine Frage: Beim ersten Wurzelknoten(MP) wird das S auf der rechten Seite geschrieben. Beim Wurzelknoten MPS wird das I an der linken Seite geschrieben. Warum? Wird immer der letzte Buchstabe auf die linke Seite geschrieben oder wie entscheide ich ob ich links oder rechts vom Wurzelknoten den nächsten Buchstaben hinschreibe?

[@whogotpwned]

Du zählst die Summe der Erscheinungen über das jeweilige Wort. Kleiner als der entsprechende Knoten impliziert Links und größer wiederum Rechts.

[@bered4894]

4:18 der geringste wenn man M und P nicht einzeln betrachtet richtig?

[@Florian.Dalwigk]

Genau

[@LegendRuffy]

an sich ist alles genau so wie in meiner vorlesung außer dass du die absolute häufigkeit eines buchstabens nimmst statt die realtive häufigkeit... was ist denn nun richtig? hmm

[@Florian.Dalwigk]

Geht wohl beides

[@Johannes-vb2tg]

2:13 dieser Voicecrack haha wollte doch nur für Informatik lernen haha. Starkes Video sonst

[@Florian.Dalwigk]

...

[@ed1849x]

top

[@Florian.Dalwigk]

:)

[@bilalbar8322]

🙏

[@Florian.Dalwigk]

👍

[@darioackermann2398]

Ich habe den Eindruck, dass der Algorithmus, der hier erklärt wird, z.B. mit 'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbccccccccccccddddddddddddddddeeeeeeeeefffff' nicht funktioniert... Man müsste doch zunächst immer Paare bilden?

[@kristofferlillje2548]

Übermorgen steht eine Klausur in Informatik an. Jetzt wird gehusslet.

[@michaelmendez1451]

Yo its you again. Lol me too.

[@kristofferlillje2548]

@@michaelmendez1451 Love you

[@Florian.Dalwigk]

Viel Erfolg für die Prüfung :)

[@RiesLP]

Frag mich grad nur wie man das dann wieder decodiert 🤔

[@Florian.Dalwigk]

www.inf.hs-flensburg.de/lang/algorithmen/code/huffman/huffman.htm

[@1aboPLZ]

Jetzt fehlt noch die Arithmetische Kodierung ;)

[@1aboPLZ]

wäre jedenfalls denke ich interessant

[@Florian.Dalwigk]

Dazu werde ich in absehbarer Zeit kein Video erstellen.

[@1aboPLZ]

@@Florian.Dalwigk schade

[@testaccount8328]

Wie wird der Text decodiert?

[@1aboPLZ]

Mithilfe der Tabelle/des Baumes

[@minoukruger7956]

Hi du erklärst das immer super ❤, kannst du ein Video bitte machen mit der LZ77 Compression , dies kommt häufig in Klausuren vor und es gibt nicht so gute erklär Videos dazu auf KZbin 🫣

[@Florian.Dalwigk]

Danke dir. Das Thema ist aktuell nicht geplant. Ich wünsche dir trotzdem viel Erfolg bei der Prüfungsvorbereitung!

[@nadjas4282]

wow, da klickt man auf einen der YT Links in den Übungsfolien und landet hier 😀👍

[@Florian.Dalwigk]

Richtig cool! Darf ich fragen, welche Uni?

[@nadjas4282]

@@Florian.Dalwigk THM Gießen

[@Florian.Dalwigk]

Ach, wie cool 😎 Ich habe da mal ganz in der Nähe gewohnt ;)

[@Florian.Dalwigk]

Darf ich fragen, wie der Dozent heißt?

[@nadjas4282]

@@Florian.Dalwigk cool cool auch ein Hesse 😀 Bienhaus ist der Gute 🐝 Grundlagenmodul muss ich machen weil an voriger Uni net so gab

[@murxibald]

Rechnet sich das? Die Kodierungstabelle muss ja schließlich auch übertragen werden, was die Redundanz wieder erhöht. 😅

[@Florian.Dalwigk]

Kommt natürlich auf das Problem an.

[@flocco2542]

Zur Dekodierung muss aber der Baum mit übertragen werden, oder? Dieser beansprucht ja ebenfalls wieder Speicher.

[@Florian.Dalwigk]

Das wurde in den Kommentaren schon beantwortet

[@baraka629]

Wir könnten noch eine größere Ersparniss erzielen wenn wir ganze Bigramme codieren würden ( z.b. das Bigramm "MI")

[@Florian.Dalwigk]

Kann man auch machen, ja.

[@hakim2665]

Danke für das Video schreibe morgen meine Arbeit und habe durch das Video viel gelernt.

[@Florian.Dalwigk]

Super und viel Erfolg!

[@noelluthi6040]

Wie ist ein Leerschlag zu handhaben?

[@1aboPLZ]

der Computer hat ja nur die Zahl vom Buchstaben im Speicher. Beim Aufschreiben als Grafik kann man dieses simbol auf der Leertaste benutzen sieht ja ungefahr so aus l___l

[@Murmel_Bahn]

Schöne Erklärung

[@Florian.Dalwigk]

Danke dir 🙃

[@xXxLegolas007xXx]

Warum hast du bei IMPS das I links von MPS stehen und nicht rechts ?

[@Florian.Dalwigk]

Weil ich von links nach rechts sortiere und l kommt im Alphabet vor m.

[@paulkohler8919]

super erklärt wie immer

[@Florian.Dalwigk]

Danke dir!

[@oskarkoelbel]

Hey, eine Frage hab ich dazu noch. Wozu schreibt man die Summen der Buchstaben dazu, die zusammengefasst werden? Haben die irgendeine Bedeutung?

[@Florian.Dalwigk]

Wo genau meinst du?

[@oskarkoelbel]

@@Florian.Dalwigk Ich meine die, die direkt unter den eingekreisten Buchstaben stehen, wenn man den Baum zeichnet. Das sind die Summen der zusammengefügten Buchstaben. Bei 4:14 wäre das die 3 unter MP

[@Florian.Dalwigk]

Danach richtet sich die Auswahl der Buchstaben.

[@oskarkoelbel]

@@Florian.Dalwigk Ok, vielen lieben Dank für deine Hilfe, finde deine Videos toll.

[@Florian.Dalwigk]

Gerne :)

[@lopix374]

Klasse Video, danke danke!

[@Florian.Dalwigk]

Gerne :)

[@matteiooo]

Sehr starkes Video 👍

[@Florian.Dalwigk]

Merci :) Ich freue mich, dass es dir weitergeholfen hat!

[@matteiooo]

@@Florian.Dalwigk Ich habe letztens von der JPEG-Kompression erfahren. VIlleicht ist es ja genau so interessant für dich wie für mich und du behandelst es in einem Video? Selbstverständlich habe ich dich abonniert. Liebe Grüße PS: Ein sehr hilfreiches Video darüber: kzbin.info/www/bejne/bZfLeYSdqpeCmbs

[@Florian.Dalwigk]

Du wirst lachen ... zu dem Thema wollte ich ursprünglich meine Bachelorarbeit schreiben ;) Allerdings habe ich mich dann doch für etwas aus dem IT-Security-Bereich entschieden. Ich werde mal schauen, dass ich dazu ein Video mache. Momentan sind aber noch andere in der Pipe. Weiterhin viel Spaß auf meinem Kanal und ein großes Dankeschön für dein Feedback :)

[@MaxMorsch]

Sehr gut erklärt. Eine Sache ist mir aber noch unklar: Wie wird der Baum übergeben oder wo und wie wird er gespeichert? Sind das in Summe dann bei kleinen Datenmengen nicht u.U. sogar mehr Daten?

[@friendlyinformatics6026]

Zur Datenmenge: Da dein Kommunikationspartner nur ein mal den Baum zum decodieren braucht, musst du nicht jedes mal die Informationen über den Baum mit senden (erst wenn sich die Struktur des Baumes ändert).

[@Florian.Dalwigk]

Mein Vorredner hat bereits alles gesagt :)

[@1aboPLZ]

@@friendlyinformatics6026 und bei dem text "TheQuickBrownFoxJumpsOverTheLazyDog"?

[@1aboPLZ]

weil, dass der Baum nur einmal übertragen werden muss ist klar aber bei Texten mit hohem Informationsgehalt pro Zeichen würde das doch mehr Platz verbrauchen oder irre ich mich? Eine Lösung wäre ja vielleicht eine Tabelle für Englische/Deutsche durchschnittliche Häufigkeiten zu nutzen

[@friendlyinformatics6026]

@@1aboPLZ Wenn du Platz als Länge des Wortes definierst ja; Aber ein Buchstabe muss ja trotzdem ins Binäre irgendwie für die Übertragung konvertiert werden. Um die Konvertierung zu optimieren kann man dann einen Huffman Baum verwenden. (Falls ich deine Frage richtig verstanden habe)

[@martinschwarz3626]

Wie kommt man auf die 21 Bit.

[@Florian.Dalwigk]

Wo genau?

[@martinschwarz3626]

@@Florian.Dalwigk Bei 5:47

[@Florian.Dalwigk]

Siehe Unwandlung mithilfe der Tabelle, ca. 20 Sekunden vor deinem Timestamp.

[@martinschwarz3626]

@@Florian.Dalwigk Sorry, ich verstehe es eeinfach nicht. Kannst du mir bitte in ein paar Sätzen erklären, wie man von den 88 Bits auf 21 Bits kommt? Vielen Dank, für die Antwort im Voraus!

[@martinschwarz3626]

Weil ich finde es nicht im Video

[@publicvoid1471]

ASCII verwendet nur 7 bits pro zeichen! UTF-8 braucht 8 bits

[@Florian.Dalwigk]

stackoverflow.com/questions/14690159/is-ascii-code-in-matter-of-fact-7-bit-or-8-bit