Rechnernetze
Home Nach oben

Run Length Encoding

Run-length encoding (RLE) ist ein sehr einfaches Datenkompressionsverfahren, welches bei Folgen gleicher Zeichen deren Häufigkeit angibt. Es erzeugt nur gute Ergebnisse, wenn lange Folgen gleicher Daten vorliegen, was häufig bei Graphiken der Fall sein dürfte. Deshalb verwendet es z.B. Microsoft im .bmp-Format. Andere Einsatzmöglichkeiten sind Textdateien, bei denen Leerzeichen zum Formatieren verwendet wurden.

RLE ist ein verlustfreies Verfahren mit geringer Kompressionsrate. Es ist aber einfach zu verstehen, zu implementieren und auszuführen.

Prinzipielles Vorgehen

Es gibt verschiedene Implementierungen von RLE. Im Prinzip sollte es ein Kontrollzeichen (z.B. @) als Häufigkeitszeichen und ein Symbol geben. Als Beispiel wählen wir die Folge

A B C C C C C C D A B E E E E

welche kodiert würde als

A B @ 6 C D A B @ 4 E

Der Gewinn ist offenbar nicht sehr groß. Tatsächlich ist die Notwendigkeit eines Steuerzeichens häufig sehr aufwendig. Offenbar findet eine Kompression nur statt, wenn die Zeichenfolge mehr als drei Zeichen umfasst. Würde man die Folgen haben:

A B C C C X C C C D A B E E E X E

so erhielte man mit

A B @ 3 C X @ 3 C D A B @ 3 E X E

die gleiche Länge. Man könnte statt dessen auch die Kodierung unterlassen, was natürlich das gleiche wie die unkodierte Folge ergibt.

Abhängig von den Daten lassen sich auch andere Verfahren kreieren, die evtl. effizienter sind. So könnte etwa das Steuerzeichen nur auftreten, wenn eine Folge von verschiedenen Zeichen vorkommt, deren Anzahl nach dem Steuerzeichen angegeben wird. Kommen gleiche Zeichen vor, so wird deren Anzahl sowie das Zeichen ohne Steuerzeichen geschrieben. Die obige Zeichenfolge

A B C C C C C C D A B E E E E

würde dann kodiert werden als

@ 2 A B 6 C @ 3 D A B 4 E

was etwas schlechter wäre, aber immer noch einen Gewinn ergibt. Dieses Verfahren ist besonders effizient, wenn lange Folgen gleicher Zeichen vorhanden sind, die gegebenenfalls mit langen Folgen verschiedener Zeichen abwechseln. Aus

A B C C C C C C D A B C D F G E E E E E E

wird somit

@ 2 A B 6 C @ 7

Ein anderes Verfahren wechselt grundsätzlich Anzahl und Zeichen(folge) ab, wobei durch ein zusätzliches Bit darauf hingewiesen wird, ob es sich um eine Wiederholungszahl des nächsten Zeichens oder um ein Anzahl verschiedener Zeichen handelt. Werden die Zeichen etwa byteweise kodiert, so könnte man immer noch Zeichenlängen von 127 mit zwei Bytes kodieren, während bei verschiedenen Zeichen maximal eine Vergrößerung um ein Byte je 127 Zeichen hinzukommt, also wohl ein vertretbarer Aufwand. Im folgenden bedeutet 4 X, dass das Zeichen X vier mal verwendet wird, während 4 A B C D bedeutet, dass vier unterschiedliche Zeichen folgen. Dieses Verfahren soll in PackBits für Macintosh verwendet werden. Für unsere Beispiele 

A B C C C C C C D A B E E E E       und           A B C C C X C C C D A B E E E X E

erhalten wir:

2 A B 6 C 3 D A B 4 E               und           2 A B 3 C 1 X 3 C 3 D A B 3 E 2 X E

also nicht immer eine Verbesserung. Die Frage, welches Verfahren benutzt werden sollte, hängt also tatsächlich von den Daten ab, insbesondere bei räumlichen Daten lassen sich geometrische Sachverhalte - etwa kartesische Koordianten - nutzbringend einsetzen.

Kompressionsverfahren, welche das Prinzip RLE verwenden sind z.B. CompuServe™ Standard für ein RLE-Dateiformat und MS Windows-Standard .bmp.