Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Grundlagen der Informatik, Codierung, Kompression - mit Übungsteil
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 125 Zeilen
- ja hallo liebe Zielgruppe ich begrüße Sie zu einem weiteren Video aus der Reihe grundlagende Informatik heute zum Thema Codierung und
- Datenkompression zunächst zum begriffcodierung das hat bei uns gar nichts mit Geheimnissen zu tun es ist einfach eine Abbildung von einem
- quellenalphabet in ein codealphabet die Abbildung ist injektiv das sorgt dafür dass wir die codierte nach eindeutig dekodieren können das Original lässt
- sich also vollständig rekonstruieren wir nennen das daher auch eine verlustfreie Komprimierung falls das codealphabet nur aus 0 und 1 besteht sprechen wir auch
- von einer binären Codierung nun zur Kompression unter Datenkompression werden Verfahren verstanden die aus großen Dateien
- kleinere Dateien machen so können wir speicherplatt sparen oder Daten schneller übertragen Beispiels also sind Daten die Audio und vide speeichern oft
- sehr voluminös sie lassen sich aber meistens gut komprimieren bei Audio und Video gibt es auch nicht nur die verlustfreie Komprimierung sondern auch
- die verlustbehaftete Komprimierung dann lässt sich zwar nicht mehr dieselbe Information rekonstruieren aber eine sehr ähnliche beispielsweise eine
- Audiodatei bei der wir keinen Unterschied mehr hören im Vergleich zum Original Software für verlustfreie Komprimierung wird auch oft als
- Packprogramm oder kurz als Packer bezeichnet bekannt sind dabei das siipformat oder rformat oder auch TGZ ja und wie funktioniert nun Komprimierung
- eine Idee ist oft dass ich wiederholende Muster oder sehr gleichmäßige Strukturen dadurch gut komprimieren lassen dass dieses Muster oder die Wiederholung
- beschrieben wird das einfachste Beispiel dafür ist die lauflängencodierung wiederholt sich ein Wert sehr oft dann geben wir einfach die
- Anzahl der Wiederholungen und den Wert selbst an so etwas verwenden wir auch außerhalb der Informatik in der natürlichen Sprache so würde ich
- beispielsweise sagen die binär dargestellte Zahl 2 hoch 100 ist eine 1 gefolgt von 10ull ich könnte auch sagen es ist die Folge 1
- 00 und so weiter und die 100 Nullen direkt aufzählen das ist aber nicht nur ermüdend es dauert auch viel länger besser ist es einfach zu sagen wie viele
- Nullen folgen und aus dieser Idee können wir auch einen Algorithmus konstruieren der das selbe für sich wiederholende Folgen von bites erledigt hier nun ein
- Beispiel für die lauflängencodierung von bites sie sehen das Original schwarz dargestellt mit der Folge F0 F0 F0 F1 08 08 08 08 08
- 05080800 offenbar gab es dabei einige Wiederholungen die wir nun über ihre Lauflänge beschreiben können es ergibt sich 03 F0 01 F1 06 08 und so weiter das
- bedeutet eben eine dreimalige Wiederholung von F0 eine nur einmalige Wiederholung von F1 eine sechsmalige Wiederholung von 08 und so weiter das
- Ergebnis bei diesem Beispiel ist dann etwas kürzer als das Original das Verfahren führt für einzelne bites die sich also nicht wiederholen zu
- Verdoppelung des Speicherbedarfs wenn uns dieser Effekt stört können wir auch ein markerzeichen vereinbaren das heißt einzelne bites bleiben einzelne bites
- und sequenzlängen werden durch das markerzeichen eingeleitet mit dem markerzeichen FF können wir für das Beispiel schreiben ff03 F0 F1
- ff0608 und so weiter das heißt die Wiederholung wie dreimal F0 oder 6 x 08 wird jeweils durch FF eingeleitet während einzelne bites einzelne bites
- bleiben in dem Beispiel hat sich das marbite allerdings nicht gelohnt wir brauchen etwas mehr Speicherplatz als bei der Codierung über Lauflängen ohne
- markerbeit zudem benötigen wir jetzt noch eine codierungsmöglichkeit für das bite FF was ja auch natürlich vorkommen kann das können wir als
- ffff vereinbaren hier noch mal ein Beispiel gezeigt die Folge 03030303 FF
- 0105 können wir dann so codieren ff0503 für die fünfmalige Wiederholung der 03 F F für das einzelne bite FF und dann
- ff0605 für die sechsfache Wiederholung des bites 05 ob sich ein solches Verfahren lohnt hängt natürlich von den Originaldaten ab je mehr und je längere
- Sequenzen es gibt desto effizienter wird das Verfahren in der Praxis ist das oft bei einfachen selbsterzeugten Computergrafiken der Fall dort
- wiederholen sich Pixel oft in großer Anzahl wir zeigen eine lauflängencodierung für eine einfache gfik das ist so eine Art Piktogramm die
- Grafik hat 128 Pixel Höhe als auch breite sie ist also quadratisch jedes Pixel wird mit einem Byte für seine Farbe gespeichert insgesamt benötigen
- wir also 16 kbibyte wie diese Farbpalette genau aussieht ignorieren wir mal für das Beispiel wir brauchen nur wissen dass Schwarz durch das 0 BTE
- codiert wird und dass die Farbe Gelb durch das bite A0 codiert wird Computergrafiken werden in der Regel von oben links nach unten rechts codiert und
- zwar Zeile für Zeile um nun die Lauflängen zu bestimmen gehen wir vereinfachten davon aus dass diese Grafik aus einem senkrechten Strich auf
- gelben Hintergrund besteht und der Strich hat eine Länge von 100 Pixeln und eine Breite von 2 Pixeln da die Anzahl 0 keinen Sinn ergibt für eine Lauflänge
- interpretieren wir die 0 als die Zahl 256 das ist in der Welt der zweierptenzen auch eine schöne runde Zahl nämlich z 2 h 8 wenn wir nur diese
- Grafik zeilenweise also von oben nach unten kodieren haben wir zunächst 14 reih gelbe Zeilen jede Zeile besteht aus 128 Pixeln das heißt wir können
- 256 Pixel codieren um jeweils zwei Zeilen anzugeben mit der siebenfachen Wiederholung von 00 A0 werden also 14 reihenelbe Zeilen codiert dann folgen in
- der nächsten Zeile noch mal 63 gelbe Pixel das können wir über 3F A0 codieren dann folgt 0200 für zwei schwarze Pixel und es folgen 63 gelbe Pixel in der
- Zeile die noch zu Ende codiert werden muss und weitere 63 gelbe Pixel in der nächsten Zeile das können wir verschmelzen zu 126 gelben Pixeln das
- ergibt die beiden bites 7e A0 und es folgen wieder zwei weitere schwarze Pixel und die ganze Sequenz müssen wir insgesamt noch 99 mal wiederholen damit
- die gesamte Länge von 100 Pixeln für den schwarzen Strich codiert wird dann können wir mit 3F A0 die verbliebenen gelben Pixel bis zum Zeilenende codieren
- und schließlich wie am Anfang die 14 gelben Zeilen codieren insgesamt erhalten wir 430 bites also deutlich weniger als das Original und wir haben
- hier eine verlustfreie Komprimierung die lauflängenkodierung ist in besonderer Weise effizient wenn es nur zwei Zustände im Original gibt z.B schwarze
- oder wei wee Pixel oder auch anderen Datenquellen mit Werten bestehend aus 0 und 1 die sich häufig wiederholen bitte schauen Sie einmal auf die Grafik oben
- rechts ohne zu erschrecken und sie sehen 12 weiße Pixel in der nächsten Zeile noch mal drei weiße Pixel die können wir verschmelzen zu einer Folge von 15
- weißen Pixeln dann folgen sechs schwarze Pixel noch mal 3 + 2 also 5 weiße Pixel und so weiter es ergibt sich dann eine Folge von Lauflängen die unten rechts
- dargestellt ist dabei müssen wir wirklich nur die Lauflängen angeben nicht die Ziff 0 und 1 jeweils codieren weil die sich ohnehin abwechseln wir
- müssen also nur die Zahlen 15 6 5 8 und so weiter speichern woraus sich die besondere Effizienz dieses Verfahrens ergibt eine weitere Option die wir bei
- der Codierung von Daten haben sind längenvariable Codes wenn wir für jedes Zeichen aus sigσma das entsprechende codzeichen C von Sigma betrachten und
- alles in einer Menge zusammenfassen erhalten wir die Menge aller Codewörter beim ask Code wären das alles Codewörter mit der Länge 7 bit deswegen nennen wir
- aski auch ein blockcode es gibt aber auch Codes bei denen sich die Längen unterscheiden dann sprechen wir von einem
- längenvariablencode ein bekanntes Beispiel für einen längenvariablencode ist z.B der Moris Code das sehen Sie unten rechts dort wird das a über die
- Folge kurz lang codiert und das E über die Folge kurz und das i über kurz kurz und das U über kurz kurz lang das Signal kurz kann also für das E stehen als auch
- für den Beginn eines as stehen damit der Empfänger das unterscheiden kann muss der Absender kleine Pausen nach jedem Buchstaben machen sodass die
- Eindeutigkeit gewahrt bleibt genau genommen hat der Code also drei Zeichen kurz lang und Pause wie das dann schief gehen kann sehen Sie an dem Beispiel
- oben rechts mit einer mehrdeutigen Codierung wenn wir sagen a wird durch 0 J durch 1 und Z durch 100 codiert dann würde die Folge ZZZ zu
- 10110 codiert werden aber auch die Folge Jazz würde zu 10101 codiert werden ohne weitere Informationen kann der Empfänger also
- diese Nachrichten nicht mehr eindeutig decodieren um die Eindeutigkeit zu erreichen können wir trendnzeichen verwenden wie bei mor coache oder auch
- eindeutige Präfixe das heißt ein Zeichen darf nicht der Beginn eines anderen Zeichens sein sodass der Empfänger immer genau weiß wie er dekodieren muss es
- nennen wir präfixfreie Codes die Möglichkeit der längenvariablen Codes können wir kombinieren mit der Idee dass wir häufige Zeichen möglichst mit kurzen
- Codewörtern codieren und seltene Zeichen dafür mit längeren Codewörtern das nennen wir eine Entropie Codierung und das funktioniert auch mit Folgen von
- Bits wir können eine Folge von präfixfreien Bitfolgen erzeugen das wäre dann 1 01 001 1 und so weiter und jetzt ist für den
- Empfänger klar der schon einzelne Bits empfangen hat ob diese bereits für ein vollständiges codiertes Zeichen stehen wie z.B 001 oder der Präfix eines noch
- nicht vollständig übertragenen Zeichens sind wenn sie beispielsweise nur die 00 empfangen müssen sie noch warten ob dies beispielsweise zur 001 oder zur
- 001 und so weiter wird nachdem die eins übertragen wurde ist die Dekodierung jedoch eindeutig die Codewörter werden dann mit absteigender Häufigkeit
- vergeben das zuletzt erzeugte Codewort kann übrigens kürzer dargestellt werden wir brauchen die letzte eins nicht mehr da bereits mit der Anzahl der Nullen die
- Eindeutigkeit gegeben ist wir zeigen das hier für den besonders kurzen Text eliminierte der UTF 16 vorliegt das häufige e wird mit dem Codewort 1 das i
- mit 01 das L mit 001 das M mit 001 codiert und so weiter bis zum t welches dann mit 6 Nullen codiert wird hier ergibt sich eine sehr kurze codierte
- Nachricht weil wir hier die Länge in Bits bestimmen es sind nur 33 Bits statt 176 Bits im Original aber Vorsicht der Empfänger benötigt ja nicht nur diese
- Bitfolge er muss auch die Zuordnung von Zeichen zu Codewörtern kennen und auch das benötigt Speicherplatz bzw Übertragungskapazität je länger aber der
- Text ist desto effizienter wird in der Regel das Verfahren wir lernen nun abschließend ein sehr wichtiges und in der Praxis oft genutztes
- Komprimierungsverfahren kennen das LZW Verfahren die drei Buchstaben stehen für die Erfinder Lempel ZIV und welch in einer weit verbreiteten Variante
- verarbeitet das Verfahren bites also achtbitwerte und gibt 12 Bit Kürzel aus dabei können diese Kürzel für original bites stehen oder auch für Folgen aus
- mehreren bit es wird also zur Codierung bzw zur Decodierung ein Wörterbuch benötigt aber das Verfahren erzeugt dieses Wörterbuch während der
- Dekodierung bzw während der Codierung es ergibt sich ein Maximum von ca 4000 Wörter im Wörterbuch wenn wir 12 Bit Kürzel zur Ausgabe verwenden der große
- Vorteil des Algorithmus besteht darin dass es ein One Pass Algorithmus ist das heißt der Input wird nur einmal eingelesen und die Ausgabe beginnt
- sofort das ist ein Unterschied zum zuletzt kennengelernten Verfahren bei dem wir zunächst einmal die Häufigkeiten bestimmen und dann erst mit der
- Komprimierung beginnen können hier nun der Algorithmus in einer einfachen Beschreibung zunächst werden die 2650 verschiedenen bitwerte im Wörterbuch
- aufgenommen das heißt jedes Bit wird durch einen 12 bitwert codiert das können wir einfach dadurch tun dass wir die ersten vier Bits auf Null setzen und
- das Bit reinkopieren dann beginnt eine Schleife wir holen uns jeweils ein Zeichen und schauen bereits die folgenden Zeichen an und zwar nehmen wir
- eine Folge von bites die nicht im Lexikon steht wenn also beispielsweise eine Folge von drei bites auftritt und diese Folge bereits im Lexikon steht
- dann wählen wir vier bals und schreiben diese neue Folge ins Lexikon danach würden wir die drei bals über das bereits existierende Kürzel ausgeben und
- von vorne beginnen das heißt wir merken uns das letzte Zeichen und schauen wieder was danach folgt das wiederholen wir sol lange bis das gesamte original
- verarbeitet wurde hier sehen Sie nun sowohl als auch Dekodierung als Pseudocode etwas ausführlicher als in der zuletzt
- dargestellten Beschreibung diesen Pseudocode können Sie gleich verwenden wenn Sie eine Übungsaufgabe bearbeiten es genügt zunächst ein schneller Blick
- um die Grundstruktur zu verstehen hierbei erkennen wir insbesondere dass bei der Dekodierung das Wörterbuch während der Bearbeitung erzeugt wird das
- wird hier als Mustertabelle bezeichnet und ist für beide Algorithmen zu Beginn leer und wird dann gefüllt mit den 256 verschiedenen Werten eines bites nach
- Bearbeitung der gesamten Eingabe endet jeweils der Algorithmus und die codierte Datei bzw das Original ist vollständig ausgegeben
- worden hier nun ein ganz konkretes Beispiel was ihr Verständnis sicherlich erleichtern wird und zwar möchten wir hier Musik komprimieren diese liegt vor
- in einer Folge von maschinenlesbaren Noten das ist ein sehr vereinfachtes Beispiel für ein bekanntes kinderled wobei die Länge der gespielten Töne hier
- der Einfachheit halalber weggelassen wurde wir müssen also eine Zeichenkette komprimieren CDE CC D CE und so weiter der Algorithmus beginnt nun mit dem
- Einlesen der Daten er liest zuerst ein C ein schaut dass darauf ein D folgt und die Folge CD wird als erster Eintrag 256 in das Wörterbuch geschrieben wir
- beginnen deswegen mit 256 weil die Einträge 0 bis 255 für dieod der original bites verwendet werden ausgegeben wird sofort ein C
- allerdings in seiner 12 Bit Codierung das heißt zu Beginn haben wir 4er bit mehr benötigt als das Original dann finden wir ein D das D wird auch gleich
- ausgegeben in seiner 12 Bit Codierung und wir schreiben die Folge de ins Wörterbuch mit dem Index 257 und das Prinzip wiederholt sich
- gleich mit dem E es wird ein E ausgegeben und die Folge EC wird ins Wörterbuch übernommen dann folgt ein C mit der Ausgabe C und dem Wort CC im
- Wörterbuch und nun wird erstmals wirklich komprimiert wir finden CD eine Folge die bereits im Wörterbuch steht wir können CD direkt ausgeben als 12
- bitwert 256 und schreiben dann CDE ins Wörterbuch das wiederholt sich ähnlich mit EC wir können 258 als Index ausgeben
- also 12 Bit statt 16 Bit wir komprimieren also hier bereits etwas und ECE wird ins Wörterbuch geschrieben mit dem Index
- 261 dann folgen drei einzelne Zeichen die auch einzeln ausgegeben werden müssen da die Folgen noch nicht im Wörterbuch stehen schließlich kann EF
- über den Index 262 ausgegeben werden und die Folge EFG wird ins Wörterbuch übernommen das geht dann immer so weiter wir sehen das später sogar Folgen von
- drei Wörtern codiert werden können dann werden also aus 24 Bits 12 Bits und wenn sich dieses Lied sehr häufig wiederholen würde immer wieder maschinenlesbar
- gespielt werden dann würden auch die Folgen im Wörterbuch immer länger werden und damit der komprimierungseffekt immer stärker hier endet es mit dem letzten C
- die Eingabe ist abgearbeitet das C wird direkt ausgegeben und ins Wörterbuch wird nichts mehr aufgenommen es folgen nun Übungen sie
- können das Video wieder anhalten wenn die Zahlenfolge 12 2 3 aufsteigt um Zeit zu haben selber die Übungsaufgabe zu bearbeiten bevor die Lösung eingeblendet
- wird in dieser Übung sollen sie eine lauflängenkomprimierung vornehmen dazu betrachten Sie die Grafik rechts die Kantenlänge des Quadrates ist wieder 128
- Pixel und dargestellt wird ein zweifarbiges Bild ein schwarzer wagerechter Strich mit Länge 50 Pixel und Höhe 2 Pixel der Rest des Bildes ist
- Zyan und wird mit dem Wert 30 codiert schwarz wird wieder mit 0 codiert sie werden zu Bearbeitung sicherlich 10 Minuten benötigen sie können nun das
- Video anhalten wir zeigen gleich die Lösung in der Lösung ergibt sich nun eine beitfolge zunächst die 31fache Wiederholung der bit 0030 für insgesamt
- 22 Zeilen Zyan von oben nach unten dann folgt noch eine Zeile Zyan und weitere 39 Pixel Zyan bis das erste schwarze Pixel eingelesen wird das ergibt 167
- Pixel Zan oder A7 in seiner hexadezimalen Darstellung dann folgen 50 schwarze Pixel und noch mal 39 Zyan piixel bis zum Zeilenende und noch mal
- 39 zy piixel zu Beginn der nächsten Zeile sodass wir insgesamt 78 zyanpixel erhalten das wird Hexer dezimal mit 4e30 codiert dann wieder 50 schwarze Pixel
- dann wieder die restlichen zyanpixel in der Zeile und so weiter bis wir die 31fache Wiederholung haben wie am Anfang insgesamt erhalten Sie 134 Bytes die
- Folge a730 würde normalerweise am Schluss stehen weil nur ein Mensch achtet hier auf die Symmetrie ein Algorithmus würde es einfach durch
- verarbeiten aber beide Lösungen sind korrekt denn sie haben hier die Wahl wo a730 steht in der nächsten Aufgabe sollen sie nun eine LZW Komprimierung
- vornehmen und zwar geht es um die UTF8 Zeichenkette ABC ABC ABC ABC ABC also eine fünffache Wiederholung von ABC wie viele bites können Sie einsparen sie
- können das Video nun anhalten es erscheint gleich die Lösung ausgegeben werden acht Zeichen insgesamt also 12 byes womit sich eine Einsparung von 3
- Bytes ergibt konkret geben wir zunächst A B und C aus wobei die Folgen ab BC und ca jeweils ins Wörterbuch aufgenommen werden mit Indizes 256 257 und 258 dann
- können wir die Folgen ab BC und ca direkt ausgeben mit jeweils einem 12 bitkürzel und es werden Zeichenketten der Länge 3 ins wörderbuch aufgenommen
- dann wird direkt zweimal ABC ausgegeben und der Algorithmus hat die Eingabe verarbeitet das zuletzt ins Wörterbuch aufgenommene Wort mit vier Zeichen wird
- also nicht verwendet das waren auch schon alle Übungen und das Ende des Lehrvideos ist erreicht hoffentlich konnte ich Ihnen einen Einblick geben in
- Datenkompression bzw Codierung und vielleicht sehen wir uns bald schon wieder bei einem anderen Lehrvideo aus der Reihe Grundlagen der Informatik bis
- dahin verabschiede ich mich auf wiederschauen ه
- [Musik]
Zum Nachlesen
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.
Lempel-Ziv-Welch-AlgorithmusDer Lempel-Ziv-Welch-Algorithmus (kurz LZW-Algorithmus oder LZW genannt) ist ein häufig bei Grafikformaten zur Datenkompression, also zur Reduzierung der …
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 …