Lauflängenkodierung (RLE) einfach erklärt

Stell dir vor, du sollst jemandem AAAAA diktieren. Statt fünfmal „A“ zu sagen, sagst du „fünf A“. Genau das macht die Lauflängenkodierung (englisch run-length encoding, kurz RLE). Sie ist ein einfacher verlustfreier Kompressionsalgorithmus. Kompression heißt: Daten werden kürzer aufgeschrieben. Verlustfrei heißt: Beim Decodieren kommt die Ausgangsfolge wieder heraus.

Die Grundidee: Jede Folge gleicher Symbole wird durch ihre Anzahl und gegebenenfalls das Symbol ersetzt. Das Alphabet ist die Menge der möglichen Symbole. Hat es mehr als zwei Symbole, muss neben der Anzahl auch das Symbol mitgesendet werden. Dafür schreibt man Paare der Form {Symbol, Anzahl}.

Beim Codieren zählst du, wie oft ein Symbol direkt hintereinander steht, und schreibst das Paar auf. Beim Decodieren gibst du zu jedem Paar das Symbol so oft aus, wie die Anzahl sagt.

Ein Schwarz-Weiß-Bild heißt auch Binärbild. Seine Pixel sind nur Schwarz oder Weiß, also reicht ein Bit je Pixel. Meist steht 0 für Schwarz und 1 für Weiß. Der umgekehrte Fall kommt auch vor. Nenne deshalb immer dazu, welche Zuordnung gilt.

Bei Bitfolgen gibt es nur Nullen und Einsen. Auf eine Folge von Nullen folgt also eine Folge von Einsen und umgekehrt, außer am Ende der Nachricht. Deshalb musst du das Symbol nicht mitsenden. Kodierer und Dekodierer einigen sich vorher, mit welchem Bit begonnen wird: durch Konvention oder durch ein zusätzliches Bit am Anfang. Danach werden abwechselnd die Längen der Null- und der Eins-Folgen übertragen.

Der Dekodierer gibt zu jedem empfangenen Wert entsprechend viele Null- oder Eins-Bits aus. Nach jedem Wert wechselt er das Bit. Binärbilder werden unter anderem bei Faxgeräten verwendet.

Den Speicherbedarf zählst du bei Bitfolgen in Bit, bei Symbolfolgen in Zeichen. Vergleiche die Länge vor und nach dem Codieren.

Bei Bitfolgen speicherst du jede Länge als Binärzahl mit fester Stellenzahl. Drei Binärstellen decken die Zahlen von 0 bis 7 ab. Darum passen nur Läufe bis 7 in 3 Bit. Im Beispiel unten werden aus 24 Bit nur 15 Bit. Ein zusätzliches Start-Bit ist dabei nicht mitgezählt. Speicherst du es doch, zähle es extra und sage dazu, wie du gezählt hast.

Lange Läufe sparen viel: Für 100 Wiederholungen braucht man nur drei Dezimalstellen. Die Einsparung ist umso geringer, je kürzer die Wiederholungen sind. Ausgedachtes Beispiel: Die Bitfolge 0101 hat vier Läufe der Länge 1 (Beginn mit 0). Mit je 3 Bit wären das 12 Bit statt 4 Bit.

Bei mehr als zwei Symbolen kann die komprimierte Nachricht sogar größer werden. Deshalb kodiert man mitunter nur Folgen ab einer bestimmten Länge, zum Beispiel ab vier. Dann braucht man ein Escape-Zeichen, das anzeigt, dass ein komprimiertes Paar folgt.

RLE ist geeignet, um längere Wiederholungen von Symbolen zu komprimieren. Bei langen Wiederholungsfolgen spart man insbesondere erheblich Speicherplatz. Bei kurzen Wiederholungen ist die Einsparung gering. Im ungünstigsten Fall, also ohne Wiederholungen, wäre die „komprimierte“ Nachricht größer als das Original.

Ein Beispiel sind Schwarz-Weiß-Seiten beim Fax. Dort wechseln sich lange weiße Bereiche mit kürzeren schwarzen Bereichen ab. Darum erzielt RLE dort gute Ergebnisse. Auch Grafikformate wie Windows Bitmap, Targa oder PCX verwenden die Lauflängenkodierung.

So begründest du: Prüfe, ob die Daten lange Läufe enthalten. Wenn ja, spart RLE viel Platz. Wechseln die Zeichen dagegen ständig, bringt RLE wenig oder sogar eine größere Nachricht.