Lauflängenkodierung
Die Lauflängenkodierung (englisch run-length encoding, kurz RLE), auch die Lauflängencodierung, ist ein einfacher verlustfreier Kompressionsalgorithmus. Er ist geeignet, um längere Wiederholungen von Symbolen zu komprimieren. Er gehört nicht zur Gruppe der Entropiekodierer, da er auf der absoluten Häufigkeit und nicht auf der relativen Häufigkeit von Symbolen basiert.
Idee
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
Das Startsymbol muss demnach bekannt sein oder zusätzlich kodiert werden.
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
Bitfolgen
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.
Mehrwertige Symbolfolgen
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.
Implementierung
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
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.
Anwendungen
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
Bekannte Dateiformate, die die Lauflängenkodierung verwenden, sind einige ältere Grafikformate wie bspw. Windows Bitmap, GEM Image, Targa oder PCX. Unter Windows wird die Dateiendung *.rle üblicherweise für RLE-komprimierte Bilder verwendet.
Literatur
- David Salomon: Data Compression: The Complete Reference. 4. Auflage. Springer, 2007, ISBN 978-1-84628-602-5.
- David Salomon: Data Compression: The Complete Reference. 4. Auflage. Springer, 2007, ISBN 978-1-84628-602-5, S. 23–31.
- Jens-Rainer Ohm: Multimedia Communication Technology. Springer, 2004, ISBN 3-540-01249-4, S. 479–481.
Einzelnachweise
- T.30 : Procedures for document facsimile transmission in the general switched telephone network. ITU-T, abgerufen am 15. August 2013.