RLE-Komprimierung - Lauflängencodierung
Die Lauflängencodierung oder RLE-Komprimierung ist ein Kompressionsalgorithmus, der zum Beispiel bei Bildern im JPEG-Format angewendet wird. Dabei werden längere Wiederholungen von Symbolen durch neue Symbole ersetzt, die Zeichenkette wird damit verkürzt und die Datei so reduziert.
Verkettung von Punkten
Die Verkettung von Punkten ist eine Methode, mit der Punkte auf optimale Weise gespeichert werden können: Bei einem Schwarz-Weiß-Bild gibt es nur zwei Farben. Ein Bildpunkt kann also auf einem Bit codiert werden, um so Speicherplatz zu sparen.
RLE-Komprimierung
RLE (Run Length Encoding, manchmal auch RLC genannt (Run Length Coding), wird bei vielen Bildformaten benutzt (zum Beispiel BMP, PCX und TIFF). Diese Komprimierungsmethode beruht auf der Verkürzung von Wiederholungen aufeinanderfolgender Elemente.
Das Grundprinzip besteht darin, ein erstes Element zu codieren, dann die Anzahl an Wiederholungen eines Wertes anzugeben und sie dann durch den zu wiederholenden Wert zu vervollständigen. So ergibt die Reihe AAAAAHHHHHHHHHHHHHH nach diesem Prinzip in komprimierter Form 5A14H. Der Gewinn durch die Komprimierung entspricht (19-5)/19, also etwa 73,7 Prozent. Für die Kette "TRITTBRETT", in der die Redundanz der Zeichen gering ist, ergibt das Ergebnis der Komprimierung "1T1R1I2T1B1R1E2T". Die Komprimierung erweist sich hier als nicht sinnvoll, da mit einem Verlust von (10-16)/10, also minus 60 Prozent.
Die RLE-Komprimierung hat deshalb besondere Regeln, die eine Komprimierung ermöglichen, wenn es erforderlich ist, und eine Kette so lassen, wie sie ist, wenn die Komprimierung zu einem Verlust führt. Diese Regeln sind folgende:
Wenn drei Elemente oder mehr sich aufeinanderfolgend wiederholen, wird die RLE-Komprimierung angewandt.
Ansonsten wird ein Kontrollzeichen (00) eingefügt, gefolgt von einer Anzahl von Elementen der nicht komprimierten Kette und dann von der kompromierten Kette selbst.
Ist die Zahl der Elemente der Kette ungerade, wird das Kontrollzeichen (00) am Ende hinzugefügt.
Außerdem gelten die diese spezifischen Kontrollzeichen:
00 01 für ein Zeilenende,
00 00 für ein Bildende und
00 02 XX YY für eine Verschiebung des Zeigers im Bild um XX Spalten und YY Linien.
So ergibt die RLE-Komprimierung nur einen Sinn für solche Daten, die zahlreiche aufeinanderfolgende, also redundante Elemente besitzen, insbesondere für Bilder, die große gleichförmige Teile enthalten. Die Methode hat den Vorteil, leicht einsetzbar zu sein. Es gibt Varianten, in denen das Bild durch Punktblöcke nach Zeilen oder sogar im Zickzack codiert ist:
Foto: © tkacchuk - 123RF.com