Lauflängenkodierung (RLE)

Jeder Lauf — egal wie lang — kostet gleich viel zum Speichern: 2 Einheiten, eine für das Symbol, eine für die Anzahl. Ein Lauf der Länge L lohnt sich nur, wenn das weniger kostet als L Rohzeichen auszuschreiben — also wenn L größer als 2 ist. Über die gesamte Eingabe gemittelt wird daraus L̄ = N/R größer als 2, wobei N die Gesamtlänge und R die Anzahl der Läufe ist — genau die Bedingung, die die Formel oben prüft. Das erklärt auch, warum RLE ein schlechter allgemeiner Kompressor ist: englischer Text, Quellcode und Zufallsdaten haben selten Läufe länger als 2, weshalb RLE Daten vorbehalten bleibt, die absichtlich lange Läufe erzeugen — 1-Bit-Faxscans, dünn besetzte Bitmaps und Palettenbilder mit einfarbigen Flächen. Reale Formate treiben das weiter: PNG wendet vor der Kompression einen Paeth-/Sub-/Up-Deltafilter auf jede Scanzeile an, der weiche Farbverläufe zuerst in lange Läufe von Differenzen nahe null verwandelt — RLE (über DEFLATE) erledigt den Rest. Probiere oben das Worst-Case-Beispiel: sechzehn verschiedene Zeichen ergeben sechzehn Läufe der Länge 1, sodass die Kodierung 32 Einheiten für 16 Zeichen braucht — die Eingabe verdoppelt sich.

Lauflängenkodierung ist die eine Kompressionsidee, auf die man von allein käme: Statt WWWWWWW Zeichen für Zeichen auszuschreiben, sagt man einfach "7 W" — genau die Abkürzung, die Menschen bei einer Telefonnummer als "dreimal die Sieben" nutzen. Sie durchläuft die Daten in einem einzigen Durchgang von links nach rechts und merkt sich nichts außer dem gerade gezählten Lauf, was sie schnell und gut streambar macht. Und sie ist verlustfrei: Aus den (Symbol, Anzahl)-Paaren lässt sich das Original exakt rekonstruieren — anders als bei JPEG oder MP3, die Details für immer verwerfen.

Naive RLE kann inkomprimierbare Daten verdoppeln, doch Apples Variante PackBits — entstanden im MacPaint der 1980er und bis heute ein Standard-Kompressionsmodus in TIFF — ist so konstruiert, dass sie fast nie wächst. Jeder Block beginnt mit einem vorzeichenbehafteten Steuerbyte: ein nicht-negativer Wert bedeutet "die nächsten Bytes sind wörtlich", ein negativer "wiederhole das folgende Byte". Einzigartige Daten werden in Blöcken von bis zu 128 Bytes unverändert kopiert, sodass der schlimmste Fall nur ein Steuerbyte pro 128 hinzufügt — unter 1 % Mehraufwand statt der 100 %, die naive RLE erreichen kann.