Lauflängenkodierung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Die Lauflängenkodierung (englisch run-length encoding, kurz RLE) ist ein einfacher verlustfreier Kompressionsalgorithmus und gehört zur Gruppe der Entropiekodierer. Er ist geeignet, um längere Wiederholungen von Symbolen zu komprimieren.

Idee[Bearbeiten]

Die Grundidee des Algorithmus ist, jede Sequenz von identischen Symbolen durch deren Anzahl und ggf. das Symbol zu ersetzen. D. h. es werden nur die Stellen markiert, an denen sich das Symbol in der Nachricht ändert. Da die Längenangabe im Vergleich zur Länge der Sequenz nur logarithmisch wächst, spart man insbesondere bei langen Wiederholungssequenzen erheblich Speicherplatz. Umgekehrt ist die Einsparung umso geringer, je kürzer die Wiederholungen sind.

Die Lauflängenkodierung wird heutzutage als Vorkodierungsschritt (z. B. bei der Bildkompression, wie JPEG) verwendet, um sich im folgenden Kodierungsschritt Aufwand zu sparen. (Z. B. spart man sich bei der Huffman-Kodierung die Betrachtung längerer Symbole, da diese bereits zuvor reduziert wurden.)

Beispiel:

Statt einer Folge mit fünf Wiederholungen des Zeichens 0 und dreimal 1

0000 0111

speichert man lediglich

5 3

Je länger eine einzelne Folge wird, umso größer ist die Einsparung, denn

  • für 10 Wiederholungen benötigt man zwei Dezimalstellen,
  • für 100 wiederholungen benötigt man drei Dezimalstellen,
  • für 1000 Wiederholungen benötigt man vier Dezimalstellen, usw.

Gleiches gilt für beliebige andere Zahlensysteme.

Verfahren[Bearbeiten]

Bitfolgen[Bearbeiten]

Bei der Kodierung von Bitfolgen existieren nur zwei Möglichkeiten: Eine Folge von Nullen oder eine Folge von Einsen. Auf jede Sequenz von Nullen folgt garantiert mindestens eine Eins – und umgekehrt ebenfalls. Die einzige Ausnahme ist, wenn das Ende der Nachricht erreicht ist.

Der Kodierer einigt sich nun mit dem Dekodierer darauf, mit welchem Bit begonnen wird. Das kann entweder durch Konvention sein oder bspw. durch ein zusätzliches Bit zu Beginn. Anschließend werden abwechselnd die Längen der Null- und Eins-Folgen übertragen. Der Dekodierer muss anschließend nichts anderes tun, als zu jedem empfangenen Wert entsprechend viele Null- oder Eins-Bits ausgeben.

Beispiel:

Die Ausgangssequenz laute:

1110 0010 0000 11

Kodiert wird daraus:

3, 3, 1, 5, 2

Mehrwertige Symbolfolgen[Bearbeiten]

Bei der Kompression von Symbolfolgen, die aus einem Alphabet mit mehr als zwei Symbolen bestehen, ist nicht mehr eindeutig, welches Symbol als nächstes folgt (z. B. Bytes haben ein Alphabet von 256 möglichen Zeichen). Hier muss neben der Anzahl der Wiederholungen auch das Symbol mitgesendet werden, aus dem die Sequenz besteht.

Eine Besonderheit hierbei ist, dass die komprimierte Nachricht u. U. sogar größer wird, wenn der Speicherplatz für die Anzahl der Wiederholungen größer ist, als die Folge selbst.

Beispiel:

Die Ausgangssequenz laute:

AAAA ABBB BBBB CDDD EE

Kodiert wird daraus:

{A, 5}, {B, 7}, {C, 1}, {D, 3}, {E, 2}

Grundsätzlich könnte ein Symbol statt nur aus einem, auch aus zwei Buchstaben bestehen:

{AA, 2}, {AB, 1}, {BB, 3}, {CD, 1}, {DD, 1}, {EE, 1}

Im ungünstigsten Fall (keine Wiederholungen) wäre die „komprimierte“ Nachricht größer, als das Original. Aus der Folge

ABCD

würde

A1B1C1D1.

Implementierung[Bearbeiten]

Der Basisalgorithmus (ohne Optimierungen) ist leicht implementierbar:

#include <stdio.h>
 
int main()
{
   int n = 1; /* Anzahl der Wiederholungen */
   int ch = -1; /* Aktuelles Zeichen */
   int prev_ch = getchar(); /* Vorheriges Zeichen */
 
   do {
      ch = getchar();
 
      if ((ch != prev_ch) || (n == 255)) /* Symbol/Wiederholungen-Tupel ausgeben, falls ein anderes Symbol kommt oder die maximal darstellbare Anzahl erreicht. */
      {
         /* printf("%c%c", prev_ch, n); */ /* Binäre Ausgabe */
         printf("%c, %d\n", prev_ch, n); /* Lesbare Ausgabe als 2er-Tupel */
 
         n = 0; /* Beginn einer neuen Folge */
      }
 
      prev_ch = ch;
      ++n;
   } while (ch != EOF);
 
   return 0;
}

Modifikationen[Bearbeiten]

Mitunter finden sich in einer Nachricht nur sehr wenige Wiederholungssequenzen. Um nun zu verhindern, dass bei einem mehrwertigen Alphabet jedes einzelne Vorkommen durch ein Tupel mit Längenangabe 1 ersetzt wird (z.  ABCA1B1C1), kodiert man nur Folgen ab einer bestimmten Länge (z. B. ab drei).

Dann benötigt man jedoch ein spezielles Zeichen (escape character), das anzeigt, dass ein komprimiertes Tupel folgt. Dieses spezielle Zeichen bzw. Symbol kommt im Idealfall sonst nicht in der Nachricht vor, andernfalls wählt man ein Symbol, von dem man annimmt, dass es nur selten auftritt. Die Besonderheit an diesem Symbol ist, dass es jedes mal als Tupel kodiert werden muss (auch wenn es nur einmal auftritt), da sonst wieder nicht zwischen dem Symbol und dem Tupel unterschieden werden kann.

Beispiel:

Die ursprüngliche Nachricht laute:

Auus die Maaaaauuuuus (Länge: 21 Zeichen)

Als Escape Character wählen wir (zur Verdeutlichung) das Zeichen „s“. Außerdem kodieren wir nur Folgen, die mindestens drei Wiederholungen enthalten:

Auuss1 die Msa5su5ss1 (Länge: 21 Zeichen)

Wiederholt sich ein Buchstabe öfter als drei Mal oder ist er das Escape-Zeichen, so wird durch die Ausgabe des Escape-Zeichens angezeigt, dass ein Tupel mit Längenangabe folgt. Darauf folgt die Anzahl der Wiederholungen und abschließend das entsprechende Zeichen.

Durch das Escape-Zeichen besteht zwar zusätzlicher Speicherbedarf, dieser wird im vorliegenden Fall jedoch durch die Einsparung an Länge-1-Folgen wieder wettgemacht. Naiv kodiert würde die Nachricht lauten:

A1u2s1_1d1i1e1_1M1a5u5s1 (Länge: 24 Zeichen)

Anwendungen[Bearbeiten]

Lauflängenkodierung kommt in Kombination mit einer modifizierten Huffman-Kodierung bei der Fax-Übertragung nach der ITU-T Empfehlung T.30 („G3-Fax“) zum Einsatz.[1] Gerade beim Übertragen von Schwarz-Weiß-Seiten erzielt die Lauflängenkodierung gute Ergebnisse, da sich hier lange weiße Bereiche mit kürzeren schwarzen Bereichen abwechseln.

Bei der verlustbehafteten Kompression von Bildern wird die Lauflängenkodierung nach der Transformation in den Frequenzbereich auf die einzelnen Koeffizienten angewandt. Insbesondere nach der Quantisierung entstehen in der Regel viele gleiche Werte oder Nullen, die sich effektiv mit einer Lauflängenkodierung komprimieren lassen. Anschließend werden diese „vor“-komprimierten Daten noch mit der Huffman-Kodierung weiter komprimiert.

Dateiformate[Bearbeiten]

Bekannte Dateiformate, die die Lauflängenkodierung verwenden, sind einige ältere Grafikformate wie bspw. Windows Bitmap, GEM Image, Targa oder PCX. Unter Microsoft Windows wird die Dateiendung *.rle üblicherweise für RLE-komprimierte Bilder verwendet.

Literatur[Bearbeiten]

  •  David Salomon: Data Compression: The Complete Reference. 4. Auflage. Springer, 2007, ISBN 978-1-84628602-5.

Einzelnachweise[Bearbeiten]

  1. T.30 : Procedures for document facsimile transmission in the general switched telephone network. ITU-T, abgerufen am 15. August 2013.
  •  David Salomon: Data Compression: The Complete Reference. 4. Auflage. Springer, 2007, ISBN 978-1-84628602-5, S. 23–31.
  •  Jens-Rainer Ohm: Multimedia Communication Technology. Springer, 2004, ISBN 3-540-01249-4, S. 479–481.