Grundlagen der Informatik, Codierung, Kompression - mit Übungsteil
Ulrich Greveler
https://www.youtube.com/watch?v=3I9aWY4A5x4

Transkript (automatisch erstellt)

0:06 ja hallo liebe Zielgruppe ich begrüße Sie zu einem weiteren Video aus der Reihe grundlagende Informatik heute zum Thema Codierung und
0:14 Datenkompression zunächst zum begriffcodierung das hat bei uns gar nichts mit Geheimnissen zu tun es ist einfach eine Abbildung von einem
0:22 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
0:33 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
0:44 von einer binären Codierung nun zur Kompression unter Datenkompression werden Verfahren verstanden die aus großen Dateien
0:53 kleinere Dateien machen so können wir speicherplatt sparen oder Daten schneller übertragen Beispiels also sind Daten die Audio und vide speeichern oft
1:02 sehr voluminös sie lassen sich aber meistens gut komprimieren bei Audio und Video gibt es auch nicht nur die verlustfreie Komprimierung sondern auch
1:11 die verlustbehaftete Komprimierung dann lässt sich zwar nicht mehr dieselbe Information rekonstruieren aber eine sehr ähnliche beispielsweise eine
1:20 Audiodatei bei der wir keinen Unterschied mehr hören im Vergleich zum Original Software für verlustfreie Komprimierung wird auch oft als
1:28 Packprogramm oder kurz als Packer bezeichnet bekannt sind dabei das siipformat oder rformat oder auch TGZ ja und wie funktioniert nun Komprimierung
1:37 eine Idee ist oft dass ich wiederholende Muster oder sehr gleichmäßige Strukturen dadurch gut komprimieren lassen dass dieses Muster oder die Wiederholung
1:46 beschrieben wird das einfachste Beispiel dafür ist die lauflängencodierung wiederholt sich ein Wert sehr oft dann geben wir einfach die
1:54 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
2:03 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
2:14 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
2:24 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
2:34 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
2:48 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
3:00 bedeutet eben eine dreimalige Wiederholung von F0 eine nur einmalige Wiederholung von F1 eine sechsmalige Wiederholung von 08 und so weiter das
3:10 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
3:19 Verdoppelung des Speicherbedarfs wenn uns dieser Effekt stört können wir auch ein markerzeichen vereinbaren das heißt einzelne bites bleiben einzelne bites
3:28 und sequenzlängen werden durch das markerzeichen eingeleitet mit dem markerzeichen FF können wir für das Beispiel schreiben ff03 F0 F1
3:40 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
3:52 bleiben in dem Beispiel hat sich das marbite allerdings nicht gelohnt wir brauchen etwas mehr Speicherplatz als bei der Codierung über Lauflängen ohne
4:01 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
4:09 ffff vereinbaren hier noch mal ein Beispiel gezeigt die Folge 03030303 FF
4:21 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
4:34 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
4:44 Sequenzen es gibt desto effizienter wird das Verfahren in der Praxis ist das oft bei einfachen selbsterzeugten Computergrafiken der Fall dort
4:53 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
5:02 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
5:13 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
5:22 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
5:32 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
5:41 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
5:51 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
6:01 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
6:13 256 Pixel codieren um jeweils zwei Zeilen anzugeben mit der siebenfachen Wiederholung von 00 A0 werden also 14 reihenelbe Zeilen codiert dann folgen in
6:25 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
6:38 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
6:48 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
6:59 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
7:09 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
7:19 hier eine verlustfreie Komprimierung die lauflängenkodierung ist in besonderer Weise effizient wenn es nur zwei Zustände im Original gibt z.B schwarze
7:28 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
7:37 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
7:47 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
7:58 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
8:06 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
8:17 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
8:26 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
8:36 aski auch ein blockcode es gibt aber auch Codes bei denen sich die Längen unterscheiden dann sprechen wir von einem
8:43 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
8:52 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
9:03 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
9:12 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
9:20 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
9:31 10110 codiert werden aber auch die Folge Jazz würde zu 10101 codiert werden ohne weitere Informationen kann der Empfänger also
9:41 diese Nachrichten nicht mehr eindeutig decodieren um die Eindeutigkeit zu erreichen können wir trendnzeichen verwenden wie bei mor coache oder auch
9:49 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
9:59 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
10:09 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
10:17 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
10:29 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
10:39 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
10:49 001 und so weiter wird nachdem die eins übertragen wurde ist die Dekodierung jedoch eindeutig die Codewörter werden dann mit absteigender Häufigkeit
10:58 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
11:07 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
11:18 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
11:31 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
11:42 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
11:52 Text ist desto effizienter wird in der Regel das Verfahren wir lernen nun abschließend ein sehr wichtiges und in der Praxis oft genutztes
12:01 Komprimierungsverfahren kennen das LZW Verfahren die drei Buchstaben stehen für die Erfinder Lempel ZIV und welch in einer weit verbreiteten Variante
12:11 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
12:22 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
12:31 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
12:43 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
12:52 sofort das ist ein Unterschied zum zuletzt kennengelernten Verfahren bei dem wir zunächst einmal die Häufigkeiten bestimmen und dann erst mit der
13:00 Komprimierung beginnen können hier nun der Algorithmus in einer einfachen Beschreibung zunächst werden die 2650 verschiedenen bitwerte im Wörterbuch
13:10 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
13:18 das Bit reinkopieren dann beginnt eine Schleife wir holen uns jeweils ein Zeichen und schauen bereits die folgenden Zeichen an und zwar nehmen wir
13:27 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
13:36 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
13:45 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
13:54 verarbeitet wurde hier sehen Sie nun sowohl als auch Dekodierung als Pseudocode etwas ausführlicher als in der zuletzt
14:04 dargestellten Beschreibung diesen Pseudocode können Sie gleich verwenden wenn Sie eine Übungsaufgabe bearbeiten es genügt zunächst ein schneller Blick
14:13 um die Grundstruktur zu verstehen hierbei erkennen wir insbesondere dass bei der Dekodierung das Wörterbuch während der Bearbeitung erzeugt wird das
14:22 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
14:33 Bearbeitung der gesamten Eingabe endet jeweils der Algorithmus und die codierte Datei bzw das Original ist vollständig ausgegeben
14:43 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
14:52 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
15:00 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
15:10 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
15:23 beginnen deswegen mit 256 weil die Einträge 0 bis 255 für dieod der original bites verwendet werden ausgegeben wird sofort ein C
15:33 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
15:43 ausgegeben in seiner 12 Bit Codierung und wir schreiben die Folge de ins Wörterbuch mit dem Index 257 und das Prinzip wiederholt sich
15:52 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
16:01 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
16:12 bitwert 256 und schreiben dann CDE ins Wörterbuch das wiederholt sich ähnlich mit EC wir können 258 als Index ausgeben
16:23 also 12 Bit statt 16 Bit wir komprimieren also hier bereits etwas und ECE wird ins Wörterbuch geschrieben mit dem Index
16:31 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
16:41 ü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
16:50 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
17:00 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
17:09 die Eingabe ist abgearbeitet das C wird direkt ausgegeben und ins Wörterbuch wird nichts mehr aufgenommen es folgen nun Übungen sie
17:17 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
17:27 wird in dieser Übung sollen sie eine lauflängenkomprimierung vornehmen dazu betrachten Sie die Grafik rechts die Kantenlänge des Quadrates ist wieder 128
17:37 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
17:47 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
17:56 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
18:06 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
18:19 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
18:28 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
18:40 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
18:51 Folge a730 würde normalerweise am Schluss stehen weil nur ein Mensch achtet hier auf die Symmetrie ein Algorithmus würde es einfach durch
18:58 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
19:08 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
19:21 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
19:30 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
19:45 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
19:55 dann wird direkt zweimal ABC ausgegeben und der Algorithmus hat die Eingabe verarbeitet das zuletzt ins Wörterbuch aufgenommene Wort mit vier Zeichen wird
20:04 also nicht verwendet das waren auch schon alle Übungen und das Ende des Lehrvideos ist erreicht hoffentlich konnte ich Ihnen einen Einblick geben in
20:12 Datenkompression bzw Codierung und vielleicht sehen wir uns bald schon wieder bei einem anderen Lehrvideo aus der Reihe Grundlagen der Informatik bis
20:20 dahin verabschiede ich mich auf wiederschauen ه
20:35 [Musik]