RLE

aus RHWiki, der freien Romhacking-Enzyklopädie

RLE steht kurz für Run Length Encoding. Das ist eine Komprimierungsmethode, die ausnutzt, dass mehrfach die selben Bytes, manchmal auch Bytekombinationen oder nur Bits, hintereinander auftreten. Für solche Fälle wird dann einfach in die komprimierte Datei geschrieben "Nehme x mal Bytes...".

Inhaltsverzeichnis

1 Die Komprimierung

2 Beispiel

3 Codierung

4 Relevanz / Effizienz

5 Siehe auch

[bearbeiten]

Die Komprimierung

Eine RLE-Komprimierung implementiert normalerweise zwei Basiscodes: Einer indiziert, dass eine bestimmte Anzahl unkomprimierter Bytes folgen, der andere gibt an, dass ein Byte (oder eine Bytekombination) x-fach wiederholt werden soll.

[bearbeiten]

Beispiel

Der Text:
abccccccccddddefffffgg

wäre pseudo-komprimiert:
[U2]ab[C8]c[C4]d[U1]e[C5]f[C2]g

Wobei [C*] der Kontrollcode für Komprimierte Daten ist und [U*] der für unkomprimierte.

Bei der Dekomprimierung wird das ganze dann so abgearbeitet:

[U2] -> nimm die folgenden 2 Bytes "ab" direkt
[C8] -> nimm das nächste Byte "c" und kopiere es 8 mal in den Output-Stream.
[C4] -> Kopiere "d" 4 mal in den Output-Stream
[U1] -> Kopiere ein Zeichen "e"
[C5] -> Schreibe 5 mal "f" in den Output-Stream
[C2] -> Schreibe 2 mal "g" in den Output

[bearbeiten]

Codierung

Manchmal sind an einer Stelle mehrere Codierungsmöglichkeiten gleicheffizient, oder die unkomprimierte Methode ist sogar besser als die Komprimierung oder umgekehrt.

Beispiel: 
abcdeefgh

Man könnte nun (analog zum Eingangs-Beispiel) so komprimieren:
[U4]abcd[C2]e[U3]fgh

Man kann aber auch so schreiben:
[U9]abcdeefgh

Der letzte Fall ist in vielen Fällen kürzer, da die Kontrollcodes
eine nicht unerhebliche Menge an Platz einnehmen.

In einem anderen Fall ist fraglich, ob ein einzelnes Zeichen (Literal) besser komprimiert oder unkomprimiert codiert werden soll:

Beispiel:
aaaaabccccc

Wird zu
[C5]a[U1]b[C5]c

oder:
[C5]a[C1]b[C5]c
?

Um solche Konstellationen zu vermeiden, führt man eine Mindestlänge für Wiederholungen ein, ab der sich eine Komprimierung wirklich lohnt. Meistens sind das 3 Bytes. Alles was kürzer als 3 Byte ist muss in solchen Fällen also unkomprimiert codiert werden.

Auf diese Weise stehen der komprimierten Codierung gleich 2 zusätzliche Plätze für die Angabe der Länge zur Verfügung. Wird die Länge z.B. durch 7 Bits angegeben, so lässt sich damit nun eine Länge im Bereich von 3-130 angeben. Es ist allerdings fraglich, ob das wirklich so stark ins Gewicht fällt...

[bearbeiten]

Relevanz / Effizienz

RLE-Komprimierungen fanden früher vorallem im Grafikbereich Anwendung, da bei Bildern mit wenig Farben oft mehrere Pixel der selben Farbe aufeinander folgen. Heute haben Bilder viele Farben, sodass sich die RLE-Komprimierung in ihrer originalen Form kaum noch eignet. Stattdessen wird RLE fast nur noch in Kombination mit anderen Komprimierungsmethoden, wie z.B. Huffman oder lz77 verwendet.

Beispiel für eine solche kombinierte Komprimierung: Grafikkomprimierung PKMN GSK

Ein Beispiel für eine typische RLE: Komprimierung der Maps in Super Mario Land 2

[bearbeiten]