4.1 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:

Eine einfache Methode der verlustfreien Komprimierung von Nutzdaten ist die Lauflängencodierung:

  • Voraussetzung: in der zu komprimierenden Zeichenfolge gibt es Zeichen, die sich wiederholen.

  • Idee: man gibt die Anzahl der Wiederholungen an und dann das Zeichen, das sich wiederholt.


Beispiel:

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.

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.

  • Ö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).

  • 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.