Lauflängencodierung


Im Zeitalter des Internets werden ständig Daten zwischen den Internet-Teilnehmern ausgetauscht. Wenn gleichzeitig sehr viele Teilnehmer Daten übertragen, ist eine hohe Bandbreite notwendig, um die Daten durch die verfügbaren Leitungen zu transportieren. Man unterscheidet hier zwischen den Nutzdaten, also den Texten, Bildern, Videos, Spielständen, Steuerdaten, Bankdaten,... und den tatsächlich übertragenen Datenströmen. Damit die verfügbaren Bandbreiten nicht an ihre Grenzen kommen, werden viele Nutzdaten vor der Übertragung komprimiert und nach der Übertragung entpackt. ZIP-Dateien sind ein Beispiel für komprimierte Daten.

Zu den Anfangszeiten des Internets wurden vor allem Texte ausgetauscht, heute sieht die halbe Welt über das Internet Filme an. Die verfügbare Bandbreite wird regelmäßig durch die veränderte Nutzung des Internets knapp, weswegen effiziente Verfahren, welche die Menge der übertragenen Daten deutlich verkleinern können, immer wichtiger werden. Haben wir vor wenigen Jahren noch SD-Filme gestreamt, sind wir heute bei HD-, UHD-, 4K-, 8K-,... Auflösungen angekommen. Sollten alle Internetteilnehmer auf die Idee kommen, gleichzeitig 8K-Filme anzusehen, würden die Backbones des Internets volllaufen.

In diesem Thema werden Sie Komprimierungsverfahren kennenlernen, mit welchen die übertragene Datenmenge klein gehalten wird. Man unterscheidet:

  • verlustfreie Komprimierung, bei der keine Nutzdaten verloren gehen
  • verlustbehaftete Komprimierung, bei der Nutzdaten verloren gehen

Lauflängencodierung

Eine einfache Methode der verlustfreien Komprimierung von Nutzdaten ist die Lauflängencodierung. Die Lauflängencodierung kann sinnvoll angewendet werden, wenn die Nutzdaten aus einer Folge von Zeichen besteht, bei denen sich Zeichen wiederholen. Die Idee der Lauflängencodierung ist, dass man nur ein Zeichen angibt und dann die Anzahl der Wiederholungen des Zeichens durch eine Zahl mitteilt.

Beispiel:

Zeichenfolge:

jjjjjrrrrbbbbbbbbbeeeoooooooopppppqqqqqqll

Lauflängencodierte Zeichenfolge:

5j4r9b3e8o5p6q2l

Länge der Zeichenfolge: 42 Zeichen
Länge der komprimierten Zeichenfolge: 16 Zeichen
Komprimierungsrate: \(16/42 = 0,38 = 38 \%\)

Die Lauflängencodierung konnte die gegebene Zeichenfolge auf 38% der Nutzdaten komprimieren.


Aufgabe zur Lauflängencodierung

Aufgabe 1: Starten Sie eine Entwicklungsumgebung Ihrer Wahl und schreiben Sie ein kleines Programm, mit welchem eine gegebene Zeichenfolge lauflängenkomprimiert wird.

Aus

jjjjjrrrrbbbbbbbbbeeeoooooooopppppqqqqqqll

soll

5j4r9b3e8o5p6q2l

werden.

Aufgabe 2: Ergänzen Sie Ihr Programm so, dass die Komprimierungsrate der Lauflängencodierung berechnet und ausgegeben wird.

Hinweis: Unter den Tabs "Lösung 1" und "Lösung 2" finden Sie Schülerlösungen mit Javascript und p5.js als Anregung für Ihr eigenes Programm.


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.

In einem neuen Fenster starten: Lauflängencodierung 1

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.

In einem neuen Fenster starten: Lauflängencodierung 2