Lauflängenkodierung

Grundprinzip und Bedeutung

Die Lauflängenkodierung (englisch run-length encoding, RLE) ist ein einfacher verlustfreier Kompressionsalgorithmus: Die ursprünglichen Daten lassen sich vollständig wiederherstellen. Sie eignet sich besonders für Nachrichten mit langen Folgen gleicher Symbole. RLE ist kein Entropiekodierer, weil das Verfahren auf der absoluten Häufigkeit aufeinanderfolgender Symbole und nicht auf ihrer relativen Häufigkeit in der gesamten Nachricht beruht.

Eine zusammenhängende Folge identischer Symbole heißt Lauf. RLE ersetzt jeden Lauf durch seine Länge und, wenn nötig, das zugehörige Symbol. Damit werden im Wesentlichen nur die Stellen erfasst, an denen sich das Symbol ändert. Die Längenangabe wächst im Vergleich zur Länge eines Laufs nur logarithmisch: Für 10 Wiederholungen braucht man zwei Dezimalstellen, für 100 drei und für 1000 vier. Entsprechendes gilt in anderen Zahlensystemen. Lange Läufe ermöglichen daher große Einsparungen; bei kurzen Läufen ist der Nutzen geringer.

Beispielsweise kann die Folge 0000 0111 als 5 3 gespeichert werden: fünf Nullen und drei Einsen. Das Startsymbol muss dabei vereinbart oder zusätzlich kodiert werden. RLE wird außerdem als Vorkodierung eingesetzt, etwa bei der Bildkompression. Dadurch müssen nachfolgende Verfahren wie die Huffman-Kodierung bereits verkürzte Symbolfolgen verarbeiten.

Kodierung von Bitfolgen

Eine Bitfolge besitzt nur die Symbole 0 und 1. Nach einem Nulllauf folgt deshalb ein Einslauf und umgekehrt, sofern die Nachricht noch nicht beendet ist. Kodierer und Dekodierer müssen lediglich vereinbaren, mit welchem Bit die Nachricht beginnt. Dies kann durch eine feste Konvention oder durch ein zusätzliches Anfangsbit geschehen. Danach werden abwechselnd die Längen der Null- und Einsläufe übertragen. Beim Dekodieren wird zu jedem Längenwert die entsprechende Anzahl des jeweils erwarteten Bits ausgegeben.

Aus der 24 Bit langen Ausgangssequenz 1111 1110 0000 1000 0001 1111 entstehen die Lauflängen 7 5 1 6 5. Um Werte von 0 bis 7 darzustellen, sind mindestens drei Binärstellen je Längenwert erforderlich. Die binär kodierte Folge lautet daher 111 101 001 110 101 und umfasst 15 Bits. In diesem Beispiel sinkt der Speicherbedarf somit von 24 auf 15 Bits.

Mehrwertige Symbolfolgen

Bei einem Alphabet mit mehr als zwei Symbolen lässt sich das nächste Symbol nicht aus dem vorherigen ableiten. Ein Byte kann beispielsweise 256 verschiedene Zeichen darstellen. Deshalb muss RLE für jeden Lauf sowohl das Symbol als auch seine Wiederholungszahl speichern, meist als Tupel aus Symbol und Länge.

Die Folge AAAA ABBB BBBB CDDD EE wird zu {A, 5}, {B, 7}, {C, 1}, {D, 3}, {E, 2}. Grundsätzlich können auch Gruppen aus mehreren Zeichen als Symbol behandelt werden. Mit Symbolen aus jeweils zwei Buchstaben ergibt dasselbe Beispiel etwa {AA, 2}, {AB, 1}, {BB, 3}, {CD, 1}, {DD, 1}, {EE, 1}.

RLE garantiert keine Verkleinerung. Wenn die Längenangabe mehr Platz beansprucht als die ursprüngliche Folge, kann die kodierte Nachricht sogar größer werden. Im ungünstigsten Fall gibt es überhaupt keine Wiederholungen: Aus ABCD würde dann A1B1C1D1.

Implementierung und Verbesserungen

Der Basisalgorithmus zählt nacheinander gleiche Zeichen. Sobald ein anderes Zeichen erscheint oder die maximal darstellbare Anzahl erreicht ist, gibt er das bisherige Symbol zusammen mit seinem Zähler aus und beginnt einen neuen Lauf. In der dargestellten C-Implementierung beträgt die maximale Lauflänge 255. Die Ausgabe erfolgt als Zweiertupel aus Zeichen und Wiederholungszahl.

Bei Nachrichten mit wenigen Wiederholungen kann man die Vergrößerung durch zahlreiche Läufe der Länge 1 vermeiden, indem erst ab einer Mindestlänge komprimiert wird, beispielsweise ab vier Wiederholungen. Ein besonderes Escape-Zeichen kennzeichnet dann den Beginn eines komprimierten Tupels. Idealerweise kommt dieses Zeichen sonst nicht in der Nachricht vor; andernfalls sollte es selten sein. Das Escape-Zeichen selbst muss immer als Tupel kodiert werden, auch bei nur einem Vorkommen, damit es eindeutig von der Markierung eines Tupels unterschieden werden kann.

Im Beispiel „Auus die Maaaaauuuuus“ mit 21 Zeichen dient „s“ als Escape-Zeichen, und Läufe werden ab drei Wiederholungen kodiert. Das Ergebnis „Auuss1 die Msa5su5ss1“ hat ebenfalls 21 Zeichen. Das zusätzliche Escape-Zeichen benötigt zwar Speicher, verhindert hier aber viele Längenangaben für einzelne Zeichen. Eine naive Kodierung als „1A2u1s_1d1i1e_1M5a5u1s“ wäre 22 Zeichen lang.

Beim PCX-Format hängt das Escape-Zeichen von der Wiederholungszahl ab. Diese Escape-Zeichen bilden ein Viertel des Zeichenvorrats; dadurch lassen sich Escape- und Längenangabe in einem einzigen Zeichen zusammenfassen.

Einsatzgebiete und Dateiformate

RLE wird bei der Faxübertragung nach der ITU-T-Empfehlung T.30 („G3-Fax“) mit einer modifizierten Huffman-Kodierung kombiniert. Bei Schwarz-Weiß-Seiten funktioniert das besonders gut, weil sich häufig lange weiße Bereiche und kürzere schwarze Bereiche abwechseln.

Bei der verlustbehafteten Bildkompression wird RLE nach der Transformation in den Frequenzbereich auf die einzelnen Koeffizienten angewandt. Nach der Quantisierung entstehen gewöhnlich viele gleiche Werte oder Nullen, die sich wirksam als Läufe speichern lassen. Anschließend werden die auf diese Weise vorkomprimierten Daten zusätzlich mit Huffman-Kodierung komprimiert.

Grafikformate mit Lauflängenkodierung sind unter anderem das Interchange File Format, genauer IFF-ILBM mit dem CmpByteRun1-Algorithmus, Windows Bitmap, Targa und PCX. Unter Windows wird die Dateiendung .rle üblicherweise für RLE-komprimierte Bilder verwendet.