Lauflängencodierung


Einige Lösungen zur Lauflängencodierung (Run-Length-Encoding)

Aaron:

Bei der Lauflängencodierung wird eine Zeichenfolge in Buchstabenblöcke unterteilt. Es wird geschaut, wie oft ein einzelner Buchstabe direkt aufeinander folgt. Man schreibt also die Anzahl und den Buchstaben in die komprimierte Form und erhält so aus „wwwwwww“ schließlich „7w“. Dies ist deutlich kürzer und spart Speicherplatz.


Chris:

Die Idee der Lauflängenkodierung ist es, jede Abfolge von identischen Symbolen durch deren Anzahl und nach Bedarf durch das Symbol zu ersetzen. Bei einer Binärcodefolge würde es folgendermaßen aussehen. Man hat zum Beispiel :

1111 1110 0000 1000 0001 1111

Hier kann man auf die entsprechende Zahl in der Komprimierung verzichten, da man ja nur zwei verschiedene Möglichkeiten hat. Jedoch müssen Kodierer und Decodierer sich darauf einigen, ob sie mit 1 oder mit 0 beginnen. In diesem Beispiel beginnen wir mit 1.

Der Zwischenschritt für die Kodierung lautet:

(1111 111 -> 7) (0 0000 -> 5) (1 -> 1) (000 000 -> 6) (1 1111 -> 5)

Theoretisch wäre man mit dem Ergebnis 7 5 1 6 5 fertig, aber man ja einen Binärcode und der muss wieder in seine Ursprungsform. Also aus 7 5 1 6 5 wird dann 111 101 001 110 101.

Diese Kodierung kann auch mit mehrwertigen Symbolfolgen absolviert werden. Man hat zum Beispiel:

AAAA ABBB BBBB CDDD EE

Hier muss man nun das Symbol mit in der Komprimierung angeben, da es mehr als zwei verschiedene Symbole gibt. Im Prinzip gibt es zwei verschiedene Möglichkeiten für die Kodierung der Nachricht.

1. Möglichkeit:

(AAAA A ->5) (BBB BBBB -> 7) (C -> 1) (DDD -> 3) (EE ->2).

Daraus wird dann {A,5}{B,7}{C,1}{D,3}{E,2}.

2. Möglichkeit

(AAAA -> 2) (AB -> 1) (BB BBBB -> 3) (CD -> 1) (DD -> 1) (EE -> 1)

Daraus wird dann {AA,2}{AB,1}{BB,3}{CD,1}{DD,1}{EE,1}.

In ungünstigen Fällen, wenn es zum Beispiel keine Wiederholung von Symbolen gibt, ist die komprimierte Datei größer. Aus der Folge ABCD würde A1B1C1D1.


Anwendung der Lauflängenkodierung: Bilder

Im folgenden kleinen Programm können Sie auf einer Fläche von 200x200 Pixeln malen, indem Sie die Maus bewegen. Das Bild wird in einem Objekt namens img gespeichert.

Innerhalb des Objekt wird das Array img.pixels gespeichert. In diesem Array werden die Farbinformationen aller Pixel des Bildes gespeichert.

Ein Bild mit 200x200 Pixeln speichert 4 Informationen pro Pixel: 3 Farbwerte zwischen 0 und 255 und den Alphawert zwischen 0 und 255 um die Transparenz (Durchsichtigkeit) anzugeben.

Das Array img.pixels hat also eine Länge von 200x200x4 = 160000.

Wenn Sie im Bild malen, sind die meisten Pixel leer und nur wenige Pixel werden geändert.

Aufgabe 1:

  • Öffnen Sie das Vorschaufenster in einem eigenen Browser-Tab.
  • Färben Sie ein paar Pixel im Zeichenbereich oben links, indem Sie die Maus bewegen.
  • Öffnen Sie das Debug-Fenster, indem Sie die Taste F12 drücken.
  • Klicken Sie auf "Sources" und öffnen dann die Datei "pixellauflaenge.js" mit einem Doppelklick.
  • Klicken Sie im rechten Bereich im Block "Watch" auf den kleinen Pfeil links neben "Watch" und dann auf das "+"-Symbol rechts neben Watch. Geben Sie dann "img.pixels" ein und drücken die Enter-Taste.
  • Sehen Sie sich das Array mit 160000 Einträgen an, indem Sie auf die kleinen Pfeile links klicken.

Beobachtung: Sie sehen in dem Array eigentlich nur Nullen und nur dort, wo Sie die Maus bewegt haben, gibt es andere Eintragungen.

Diese Situation ist perfekt geeignet für die Lauflängenkodierung, denn in diesem Array gibt es sehr viele sich wiederholende gleiche Zahlen (nämlich 0).

Aufgabe 2: (für die Profis)

  • Kopieren Sie das Array img.pixels in ein eigenes Array, nach einer geeigneten Anleitung, die Sie im Internet finden.

  • Erweitern Sie das Programm, so dass das kopierte Array lauflängenkomprimiert in einen String geschrieben wird. Wenn Sie nur wenige Pixel mit der Maus gemalt haben, müsste der erzeugte String ziemlich kurz werden.

  • Legen Sie im Kursforum ein neues Thema an und stellen Sie dort Ihren Lösungscode und den Lösungsstring vor. Im Forum gibt es eine Funktion "Code" mit dem Sie den Code auch hübsch formatieren können.

Aufgabe 2: (für alle anderen)

  • Warten Sie, bis im Forum ein Profi ein Lösungsthema begonnen hat. Versuchen Sie den Lösungscode in einer Umgebung Ihrer Wahl zum Laufen zu bringen, um selbst den lauflängencodierten String zu erzeugen oder versuchen Sie den lauflängencodierten String zu verstehen.

  • Diskutieren Sie im Forum oder wie auch immer Sie wollen, bis Sie den Code verstanden haben.

Lösung zur Aufgabe

Nico hat eine Lösung programmiert (Super Leistung!), die funktioniert und welche die Stärke der Lauflängencodierung zeigt.

Aufgabe 3:

  • Öffnen Sie die Sandbox in einem neuen Fenster.
  • Zeichnen Sie noch NICHTS mit der Maus im Zeichenbereich, sondern öffnen Sie im rechten Fenster nur die Konsole, indem Sie unten links auf "Console" klicken. Wenn Sie noch nichts gezeichnet haben, zeigt die Konsole den Entrag: 1,255,1,100,1,0,1,255,159996,0,. Die meisten Einträge sind identisch und werden mit der Zahl 159996 zusammengefasst.

  • Zeichnen sie nur wenige Pixel in den Zeichenbereich und beobachten Sie, wie sich die Ausgabe auf der Konsole verändert. Es sind immer noch weit weniger Einträge als 160000, aber je komplexer das Bild wird, desto länger wird der lauflängencodierte String.