Mit Google fortfahren
Lauflängenkodierung (RLE) einfach erklärt
Die Lauflängenkodierung, kurz RLE für Run-Length Encoding, ersetzt aufeinanderfolgende gleiche Symbole durch ihre Anzahl und das Symbol. Dadurch bleiben alle Informationen erhalten. Speicher spart das Verfahren aber nur, wenn die Daten ausreichend lange Wiederholungen enthalten.
Hake ab, was du schon kannst — und komm am Ende hierher zurück!
Warum Wiederholungen Speicher sparen können
Betrachte diese Folge aus weißen und schwarzen Pixeln:
WWWWWSSS
Statt jedes Pixel einzeln zu notieren, kannst du die beiden Läufe angeben:
5W 3S
Lauf
Ein Lauf ist eine ununterbrochene Folge gleicher Symbole. In WWWWWSSS bilden die fünf weißen Pixel den ersten und die drei schwarzen Pixel den zweiten Lauf.
RLE ist verlustfrei: Wenn die Regeln der Codierung eindeutig festgelegt sind, lässt sich die ursprüngliche Folge vollständig wiederherstellen.
Lange Läufe benötigen nur wenige Angaben. Viele kurze Läufe erzeugen dagegen viele Angaben und können die Datenmenge vergrößern.
So codierst und decodierst du Läufe
Zum Codieren gehst du immer in derselben Reihenfolge vor:
- Beginne beim ersten Symbol und setze den Zähler auf 1.
- Vergleiche das nächste Symbol mit dem aktuellen Symbol.
- Ist es gleich, erhöhst du den Zähler.
- Ist es verschieden, notierst du Anzahl und bisheriges Symbol. Dann beginnt ein neuer Lauf.
- Am Ende notierst du auch den letzten Lauf.
Die Folge WWWWSSWWW enthält drei Läufe:
- vier weiße Pixel:
4W - zwei schwarze Pixel:
2S - drei weiße Pixel:
3W
Die RLE-Darstellung lautet daher 4W 2S 3W.
Beim Decodieren erzeugst du zuerst vier W, dann zwei S und zuletzt drei W. So erhältst du wieder WWWWSSWWW.
Bei einer Bitfolge genügt auch ein bekanntes Startbit mit anschließend wechselnden Lauflängen. Aus 00000111 werden bei Startbit 0 beispielsweise die Längen 5, 3. Bei mehr als zwei möglichen Symbolen muss dagegen zu jeder Länge das zugehörige Symbol angegeben werden.
Wähle in jeder Lücke die passende Form und prüfe anschließend deine Antworten.
Beim Codieren wird zuerst ein zusammenhängender erkannt. Seine wird zusammen mit dem Symbol gespeichert. Beim Decodieren wird das Symbol entsprechend oft .
So funktioniert der 4-Bit-Code für Bilder
Ein Bild wird vor der Codierung in einer festgelegten Reihenfolge gelesen, zum Beispiel zeilenweise von links nach rechts und von oben nach unten. Außerdem muss vereinbart sein, ob ein Lauf über ein Zeilenende hinaus fortgesetzt wird. Zum Wiederherstellen des Bildes benötigt der Decoder dieselbe Leseregel sowie Breite und Höhe des Bildes.
Für Schwarz-Weiß-Bilder kann jedes Codewort aus vier Bit bestehen:
- Das erste Bit gibt die Farbe an:
0bedeutet weiß,1bedeutet schwarz. - Die letzten drei Bit speichern die Lauflänge minus 1.
- Ein Codewort kann deshalb Lauflängen von 1 bis 8 darstellen.
| Lauflänge | weiß | schwarz |
|---|---|---|
| 1 | 0000 | 1000 |
| 2 | 0001 | 1001 |
| 3 | 0010 | 1010 |
| 4 | 0011 | 1011 |
| 5 | 0100 | 1100 |
| 6 | 0101 | 1101 |
| 7 | 0110 | 1110 |
| 8 | 0111 | 1111 |
Warum wird 1 abgezogen? Drei Bit können die Werte von 000 bis 111, also von 0 bis 7, darstellen. Durch die Zuordnung gespeicherter Wert = Lauflänge − 1 stehen diese acht Werte für die Lauflängen 1 bis 8.
Ein schwarzer Lauf der Länge 3 erhält zuerst das Farbbit 1. Für die Länge wird 3 − 1 = 2 gespeichert; 2 lautet binär 010. Das Codewort ist daher 1010.
Ein Lauf aus 14 schwarzen Pixeln ist zu lang für ein einzelnes Codewort. Du zerlegst ihn beispielsweise in 8 und 6 Pixel:
1111 1101
1111 steht für acht schwarze Pixel und 1101 für sechs schwarze Pixel. Zusammen ergeben sie wieder 14 schwarze Pixel.
So vergleichst du den Speicherbedarf
Eine Aussage wie „RLE komprimiert gut“ reicht nicht. Du musst das verwendete Codeformat und beide Datenmengen kennen.
Für ein Schwarz-Weiß-Bild mit 20 mal 11 Pixeln benötigt die ursprüngliche Bitmap bei einem Bit pro Pixel:
$$20 \cdot 11 = 220\text{ Bit}$$
Eine Codierung desselben Bildes besteht aus 38 Codewörtern zu je 4 Bit:
$$38 \cdot 4 = 152\text{ Bit}$$
Der Anteil der komprimierten Datenmenge beträgt:
$$\frac{152}{220} \cdot 100\% \approx 69{,}1\%$$
Die codierten Daten sind also rund 69 Prozent so groß wie das Original. Gespart werden 68 Bit beziehungsweise rund 30,9 Prozent.
Die Schreibweise beeinflusst das Ergebnis. Eine lesbare Textdarstellung mit 51 ASCII-Zeichen benötigt 51 Byte, also 408 Bit. Sie wäre damit größer als die 220 Bit Bildinformation. RLE allein garantiert noch keine Verkleinerung; entscheidend ist auch, wie Lauflängen und Symbole gespeichert werden.
Wann RLE nützt und wann nicht
RLE eignet sich besonders für Daten mit großen gleichartigen Bereichen, zum Beispiel einfache Schwarz-Weiß-Bilder mit langen weißen Flächen. Weniger geeignet sind Folgen mit häufigen Farb- oder Symbolwechseln.
Beim 4-Bit-Verfahren zeigt der Extremfall das Problem deutlich:
WSWSWSWS
Jedes Pixel bildet einen eigenen Lauf. Für acht ursprüngliche Bildbits entstehen acht Codewörter mit insgesamt 32 Bit. Die codierte Folge ist viermal so groß wie das Original.
Beurteile RLE in drei Schritten: Läufe untersuchen, Codeformat festlegen und anschließend beide Bitmengen berechnen.
Auch die Anzahl möglicher Symbole ist wichtig:
- Bei zwei Symbolen genügt ein bekanntes Startsymbol mit wechselnden Lauflängen.
- Bei mehreren Symbolen ist das nächste Symbol nicht vorhersagbar. Deshalb muss es zusammen mit seiner Lauflänge gespeichert werden.
- Hat das Längenfeld einen Höchstwert, müssen längere Läufe auf mehrere Codewörter verteilt werden.
Karteikasten
Überlege zuerst selbst und drehe die Karte anschließend zum Prüfen um.
Alles auf einen Blick
- Lauflängenkodierung
- Prinzip: gleiche Symbole zu Läufen bündeln
- Codieren: Länge und Symbol eindeutig speichern
- Decodieren: Symbole in angegebener Anzahl wiederholen
- 4-Bit-Code: Farbbit plus drei Bit für Länge minus 1
- Nutzen: lange Läufe können Speicher sparen
- Grenze: kurze Läufe und Farbwechsel können Daten vergrößern
- Prüfung: Codeformat und Bitmengen vergleichen
Abschluss-Check
Du beherrschst RLE, wenn du nicht nur Läufe bilden kannst, sondern vor jeder Speicherrechnung das Codeformat klärst und das Ergebnis anhand der tatsächlichen Bitmengen beurteilst.