Lauflängenkodierung

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

Beispiel:

Die Ausgangssequenz sei:

1111 1110 0000 1000 0001 1111

Kodiert wird daraus:

7 5 1 6 5

Die notwendige Mindestanzahl an notwendigen Binärstellen ist drei, denn dies deckt den Zahlenbereich von 0 bis 7 ab. Binär kodiert lautet die komprimierte Folge dann

111 101 001 110 101

Die ursprünglich 24 Bits konnten auf 15 Bits reduziert werden.

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

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.

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;
}

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.  ABC → A1B1C1), kodiert man nur Folgen ab einer bestimmten Länge (z. B. ab vier).

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

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:

1A2u1s_1d1i1e_1M5a5u1s (Länge: 22 Zeichen)

Beim Dateiformat PCX wird je nach Anzahl der Wiederholungen ein anderes Escape-Zeichen verwendet (diese machen bei PCX ein Viertel des Zeichenvorrats aus), sodass Escape- und Längenzeichen zu einem Zeichen zusammenfallen.

Dateiformate, die die Lauflängenkodierung verwenden, sind Grafikformate wie das Interchange File Format (IFF-ILBM mit CmpByteRun1-Algorithmus), Windows Bitmap, Targa oder PCX. Unter Windows wird die Dateiendung .rle üblicherweise für RLE-komprimierte Bilder verwendet.