Lauflängenkodierung
aus Wikipedia, der freien Enzyklopädie
Die Lauflängenkodierung (engl. Run-length encoding, kurz RLE) ist ein sehr einfacher verlustfreier Kompressionsalgorithmus für digitale Daten. Sie ist besonders gut geeignet, Wiederholungen oder Sequenzen von gleichen Werten verkürzt darzustellen. Liegt eine Wiederholung vor, wird die Anzahl der Wiederholungen sowie der wiederholte Wert gespeichert.
[Bearbeiten] Beispiel
Als Beispiel sei ein S/W-Bildschirm angenommen, auf dem sich schwarzer Text auf weißem Hintergrund befindet. Hier sind lange Folgen von weißen Punkten bzw. Pixeln nur selten durch einzelne schwarze Punkte unterbrochen. Bezeichnet man weiße Punkte mit "W" und schwarze mit "S", so ergibt sich in einer einzelnen Bildzeile die folgende Information:
WWWWWWWWWWSWWWWWWWWWWSSS
Nach Anwendung der Lauflängenkodierung erhält man:
10WS10W3S
Dies muss interpretiert werden als eine Folge von zehn weißen, einem schwarzen, gefolgt von weiteren zehn weißen und drei schwarzen Punkten. Die ursprünglich verwendeten 24 Buchstaben wurden somit in neun Buchstaben komprimiert, was einer Kompression auf ca. 33% der ursprünglichen Größe entspricht.
Bei einer ungünstigen Verteilung der Werte kann allerdings auch eine Vergrößerung der Datenmenge vorkommen. Dies ist bspw. bei folgenden Zahlenwerten der Fall:
5656
Da man hier nicht mehr zwischen den ursprünglichen Daten und dem Multiplikator unterscheiden kann, muss man selbst einzeln vorkommende Werte kodieren. Ansonsten würde der Algorithmus 56 zu 66666 expandieren. Die Kodierung der obigen Folge wird also wie folgt vorgenommen:
15161516
Vor jede ursprüngliche Zahl wird die Anzahl *1* ergänzt. Der längenkodierte Wert ist somit doppelt so lang wie der ursprüngliche.
Dieses Problem lässt sich vermeiden, indem bei Multiplikatoren größer 3 ein Kontrollzeichen eingefügt wird:
WSWSWWWWWWWWWSSSSSSWSWWW WSWSX9WX6SWSWWW
Hier kommt es aber zum Konflikt wenn im Datensatz das Kontrollzeichen als Inhalt auftaucht. Lösen kann man das, wenn man ein einzelnes X als XX komprimiert. Das Kontrollzeichen-X ist hervorgehoben.
WSSSSSWWWWWWxWWSWSSSSSSSSSxxxxxWSSW WX5SX6WXXWWSWX9SX5XWSSW
Es gibt weitere Möglichkeiten, ein solches Aufblähen der Daten zu verringern, ganz vermeiden lässt sich dieser Effekt jedoch nicht.
[Bearbeiten] Praktische Anwendung
Die unterschiedlichen Kompressionsprogramme speichern die komprimierte Datenfolge im Gegensatz zum obigen Beispiel in binärer Form ab, die teilweise sehr unterschiedlich sein kann. Einige Anwendungen speichern auch zusätzlich Folgen von mehreren Datenwerten, machen also aus -ABC-ABC-ABC-ABC- die gekürzte Darstellung 4[-ABC]-.
Geeignet ist die Lauflängenkodierung also da, wo es lange Folgen des gleichen Wertes gibt. Dies ist sehr häufig bei älteren Icons oder Clip-Art-Bildern der Fall, die meist nur mit wenigen Farben gezeichnet sind.
Bekannte Dateiformate, die die Lauflängenkodierung anwenden, sind daher viele ältere Grafikformate wie beispielsweise Windows Bitmap, GEM Image, Targa oder PCX.
Unter Microsoft Windows wird die Dateiendung .RLE üblicherweise für RLE komprimierte BMP-Bilder verwendet, die Dateiendung .BMP meist für unkomprimierte Bilder.
