Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Lauflängen-Kodierung
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 31 Zeilen
- Als erstes Verlustfreies Kompressionsverfahren wollen wir uns ähm das Lau die Lauflängenkodierung angucken. Und das ist so ein bisschen
- die das Standardverfahren, mit dem man eigentlich immer einsteigen kann. Auf englisch runth and coding. Und die Idee hier ist, dass wir Sequenzen gleicher
- Symbole ersetzen durch die Kombination aus dem Symbol und deren Anzahl. Das heißt, wir haben eine hohe Ersparnis bei langen Folgen gleicher Symbole. Wenn wir
- mal das Beispiel hier rechts betrachten und ähm wir stellen uns vor, dass es sich dabei um ein Bild handelt, das eine Auflösung hat, ich sage jetzt mal
- beispielhaft 200 x 400 Bildpunkte, dann ernt man schon, dass wenn man eine Zeile von diesem Bild betrachtet, man immer lange Folgen von weißen Pixeln und dann
- lange Folgen von schwarzen Pixeln hat. Und das wäre ein Beispiel für eine gute Eignung für die Lauflängencodierung, weil wir überhaupt nur zwei verschiedene
- Symbole haben, schwarz und weiß und die jeweils häufig hintereinander vorkommen, zumindest im Schnitt. Die ähm diese Bitfolgen ähm die lassen
- sich jetzt so codieren, dass wir einfach nur mit 0 und 1 ähm arbeiten und wir könnten in unserer Festlegung einfach festlegen, dass wir zunächst mit der
- Anzahl der Nullen beginnen und dann immer abwechselnd Nullen und Einsen codieren. Da wir in diesem abwechselnden Schema sind, müssen wir auch gar nicht
- mehr sagen, um welches Zeichen es sich handelt, sondern nur noch das entsprechende Auftreten. Und wenn wir uns das mal als Beispiel angucken für
- die Folge 111101111, dann gäbe sich daraus die Codierung 0 mal die 0, weil wir eben
- nicht mit einer Null beginnen, dann einmal die 1, da haben wir jetzt noch nicht viel gespart, aber dann dreimal die 0, viermal die 1, ähm einmal die 0
- und noch dreimal die 1. Man sieht also, dass die Codierung, zumindest von der Anzahl der Einträge in der Codierung schon mal ähm weniger aufwendig ist als
- die Originaldaten. Etwas kompliziertes komplizierter ist es bei einem beliebigen Alphabet, also z.B. den Großbuchstaben von A bis Z. Da müssten
- wir jetzt immer Paare angeben. Paare aus dem aktuell zu codierenden Zeichen und dessen Anzahl von vorkommen. Hier zu Beginn unseres Wortes haben wir 3, also
- codieren wir E3, dann kommt ein K, k1, dann haben wir viermal den Buchstaben H, das wäre H4 und zum Schluss noch zweimal das I, I2. So könnte also eine solche
- Lauflängencodierung aussehen. Aber dieses Verfahren ist nachteilig bei Zeichen, die nur sehr selten vorkommen und deswegen codiert man tatsächlich nur
- Zeichenfolgen, die aus mindestens n gleichen Zeichen bestehen. Z.B. kann man sagen, erst wenn wir eine Folge von vier gleichen Zeichen haben, dann wollen wir
- Lauflängencodierung anwenden. In allen anderen Fällen wollen wir die Zeichen durch sich selber codieren. Das heißt, aber wir müssten irgendwie markieren, an
- welcher Stelle so eine lauflängencodierte Variante startet und wo ein Zeichen für sich selber steht. Und das kann man durch ein Escape
- Zeichen erreichen, das tatsächlich auch Teil des Alphabets sein kann. Wir gucken uns auch das in dem Beispiel an. Wir haben hier das Alphabet von klein A bis
- klein Z und verwenden jetzt einfach mal zufällig Y als unser Escapezeichen. Und jetzt betrachten wir hier so eine Eingabefolge, wo wir sehen, wir haben
- teilweise Folgen von Zeichen, die vier oder öfter mal hintereinander gleich vorkommen, 4 FS oder 5O. Und dann haben wir aber auch Zeichen, du nur einmal
- oder dreimal vorkommen und die werden jetzt unterschiedlich behandelt. Also das J wird durch sich selber codiert. Die 4F wollen wir durch F4 codieren,
- aber wir müssen das Ganze einführen mit unserem Escapeichen Y. Das heißt also durch 4F konkludieren wir durch yf4. Dann kommt das A, das für sich
- selber steht. Die 3Gs sind weniger als vier, insofern müssen auch die durch sich selber konstruiert werden. Und dann haben wir das Y, von dem es eigentlich
- auch nur eins gibt's, aber es ist unser Escape Zeichen. Das heißt, hier brauchen wir eine Sonderbehandlung, wo wir sagen Escape Zeichen und dann einmal das Y.
- Und danach haben wir noch die fünf Vorkommen vom O, also Y und dann die Anzahl 5. Das ist ein sehr einfaches Verfahren,
- einfach umzusetzen, aber sie haben es eben schon in unserem Beispiel gesehen, wir haben nicht viel Ersparnis bei Folgen ohne Wiederholungen oder selbst
- bei kurzen Wiederholungen. Insofern wird dieses Verfahren häufig nur in Kombination mit anderen Verfahren verwendet, wo man das vielleicht noch
- zusätzlich einsetzt. Es ist ja verlustfrei und auch der Rechenaufwand ist sehr überschaubar.
Zum Nachlesen
LauflängenkodierungDie Lauflängenkodierung (englisch run-length encoding, kurz RLE), auch die Lauflängencodierung, ist ein einfacher verlustfreier Kompressionsalgorithmus.
DatenkompressionDatenkomprimierung [1] genannt – ist ein Vorgang, bei dem die Menge digitaler Daten reduziert wird. Dadurch sinkt der Speicherbedarf,
Arithmetisches KodierenDie arithmetische Kodierung ist eine Form der Entropiekodierung, die bei der verlustfreien Datenkompression verwendet wird. Sie erzielt Kompressionsraten …
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 …