LZW-Kodierung: Informatik
bleeptrack
https://www.youtube.com/watch?v=dLvvGXwKUGw

Transkript (automatisch erstellt)

0:01 so hallo bei meiner kleinen informatikecke ich möchte euch heute mal wieder einen Codierungsverfahren zeigen diesmal nicht den Huffman Code sondern
0:08 die LZW Codierung die ist benannt nach drei Herren nämlich Lempel ZiF und welch und stammt aus dem Jahr 1984 die LCW Codierung wird übrigens z.B bei der
0:21 gifkprimierung verwendet ja leg wir gleich mal los wenn wir was codieren wollen kennt ihr ja schon brauchen wir erst mal ein Wort dass wir codieren
0:29 wollen ich habe mir hier mal ab ABC ab AC ausgesucht was sehr kreativ ist wie ich finde ja okay die LZW Codierung ist Wörterbuch
0:41 basiert das heißt wir bauen uns während dem Codieren eine Art Wörterbuch auf und man startet normalerweise auch mit einem Wörterbuch das schon grundeinträge hat
0:51 meistens sind das die einzelnen Buchstaben und normalerweise nimmt man hier die aski Zeichen also hier würde dann irgendwie 60 stehen und ich weiß
1:00 gerade gar nicht was das kleine a ist aber ich habe es hier mal einfach halt halber mit ganz normalen kleinen Zahlen gemacht also ich habe angefangen bei
1:08 eins zu zählen und wenn ich eine LZW Codierung ma dann baue ich mir am besten noch eine Tabelle auf die sieht folgendermaßen aus
1:16 also die werden oft unterschiedlich gezeigt diese Tabellen aber ich finde die hier jetzt mal am einfachsten wir haben vier ein vier
1:25 Spalten vier Einträge die erste Spalte ist das letzte Wort die nächste Spalte ist das aktuelle Wort
1:33 mit dem wir gerade ja wir arbeiten im Endeffekt immer in mit einer Kombination aus dem beiden Spalten Eintrag hier steht für Eintrag im Wörterbuch also
1:42 immer wenn wir einen neuen Eintrag im Wörterbuch machen und die codeausgabe aus der Spalte können wir dann zum Schluss ablesen wie wir denn das Wort
1:51 codiert haben J fangen wir auch mal an das aktuelle Wort bzw der aktuelle Buchstabe ist natürlich gleich mal der erste
2:00 Buchstabe nämlich das a das kommt hier rein was dann passiert ist ich schaue mir immer beide Spalten an das letzte
2:11 Wort und das aktuelle Wort in dem Fall haben wir ja kein letztes Wort weil wir gerade eben was angefangen haben das heißt wir haben hier praktisch blank und
2:18 a ist also ein a dann überprüfe ich steht das schon in meinem Wörterbuch und sehe ja klar a ist gleich der erste Eintrag steht schon drin das heißt ich
2:28 kann mir hier weitere Schritte sparen D mache ich gleich weiter dass der nächste Buchstabe ist das B mein letztes Wort oder mein letzter
2:40 Buchstabe war ja das a das heißt das a wandert jetzt hier rüber jetzt schaue ich mir wieder beide Spalten in Kombination an und sehe
2:49 ab gibt es noch nicht im Wörterbuch das heißt ich muss einen neuen Eintrag machen und am sinnvollsten ist natürlich ich zähle hier gleich weiter das heißt
2:58 der höchste Eintrag war die vier und dann mache ich eben hier die fünf draus also haben wir einen neuen Eintrag im
3:08 Wörterbuch was dann noch passiert ich gebe den Code für das letzte Wort aus also den Code für a und der ist ja 1
3:17 lautwörterbuch so und dann geht schon weiter wir holen uns wieder ein a aus der Zeichenkette und das B war mein letztes
3:27 Wort wandert hier rüber und wir schauen wieder BA okay gibt es noch nicht machen wir also einen neuen Eintrag wäre dann der sechste
3:41 Eintrag und wir geben den Code für B aus wir holen uns jetzt wieder ein B aus der Zeichenkette jetzt wird's richtig
3:52 spannend erst denn wir sehen jetzt okay ab gibt es schon haben wir schon einen eigenen Eintrag gemacht das heißt wir können uns hier wieder sämtliche
4:02 Schritte sparen und jetzt muss man aufpassen wenn es nämlich für die Kombination hier schon einen Eintrag gibt dann wandert nicht nur das B in die
4:11 nächste Zeile sondern die Kombination also ab wenn ihr euch jetzt wundert das hätten wir hier oben ja eigentlich auch
4:19 machen müssen denn da haben wir hier ja auch nichts gemacht haben wir ja im Endeffekt auch denn hier ist ja eigentlich blank oder nichts und das
4:26 haben wir ja im Endeffekt hier mit runtergezogen gut dann holen wir jetzt uns noch das C aus der Zeichenkette landen bei ABC gibt
4:36 es noch nicht also ein neuer Eintrag und wir geben den Code für ab aus der ist
4:47 5 so dann wandert das C weiter wir holen uns ein a ca gibt es auch als Eintrag noch nicht also wieder ein neuer das ist dann die
5:03 8 und wir geben den Code für C aus der ist 3 dann kommt ein B das a wandert wieder weiter und wir
5:15 sehen ja ab haben wir schon also können wir uns hier den Rest sparen und jetzt eben wieder aufpassen wenn es den Eintrag schon gibt
5:26 wandern beide beide Spalten mit weiter und wir holen uns ein a aus der Zeichenkette so jetzt haben wir a a das
5:38 gibt's auch noch nicht das wäre der neunte Eintrag und wir geben ab aus das ist wieder die
5:48 F a wandert weiter und jetzt sind wir sch schon fertig wir holen uns noch ein C AC kennen wir auch nicht also noch mal ein neuer Eintrag der zehnte
6:04 Eintrag und wir geben noch zuletztes a aus genau ein so wir sind hier jetzt am Schluss unsere Zeichenkette das heißt das C wandert noch weiter und hier kommt
6:18 nichts mehr ich schreibe hier mal end of file da müssen wir jetzt dann noch eine Sache machen damit das C nicht vergessen wird müssen wir das C noch ausgeben das
6:28 heißt hier kommt noch die drei so und jetzt haben wir das Wort auch schon fertig codiert das heißt unsere Zeichenkette
6:38 entspricht der Codierung 1 2 5 3 5 1 3 so dann wür ich sagen schauen wir mal ob das stimmt mal die Tabelle schnell wegmachen 1 2 5 3 5 1 3 schauen wir mal
6:58 die 1 ist das A 2 das B 5 war ab die 3 das C 5 wieder ab 1 das a und die 3 das C ab ABC ab AC
7:24 ja hat also funktioniert so und wie immer zum Schluss würde ich euch jetzt noch vorschlagen das ganze mal selber zu
7:32 machen und zwar mit dem Wort [Musik] Abra kadabra und mein Vorschlag dazu wäre
7:43 natürlich auch ein ein anfangswörterbuch das heißt ihr hätte dann auch das a als ein das B als 2 das R als 3 und das K als
7:58 VI könnt ihr damit mal ausprobieren ich werde das Ergebnis auf jeden Fall unter das Video schreiben dann könnt ihr auch vergleichen ob ihr es richtig gemachen
8:06 gemacht habt so ich hoffe es hat euch Spaß gemacht und ich wünsche euch noch alles Gute und hoffentlich bis bald tschüss