Lauflängen

Lauflängen bezeichnet die Längen von Läufen identischer Symbole in einer Sequenz. Ein Lauf ist eine maximale Folge gleicher Werte, und die Lauflänge gibt an, wie viele aufeinanderfolgende Token denselben Wert tragen. In einer Sequenz aus Symbolen übt jeder Wechsel des Symbols einen neuen Lauf aus, der durch seine Länge beschrieben wird.

Formal lässt sich eine Sequenz s1, s2, ..., sn über einem Alphabet A betrachten. Ein Lauf beginnt bei Position i, wenn s_i ungleich s_{i-1} oder i = 1, und endet bei j, wenn s_j ungleich s_{j+1} oder j = n. Die Lauflänge ist l = j − i + 1. Die Gesamtheit der Lauflängen eines Datensatzes liefert eine Verteilung, die Aufschluss über Wiederholungspotenziale geben kann.

Run-Length-Encoding (RLE) ist ein bekanntes Verfahren, das Lauflängen nutzt, um Daten zu komprimieren. Dabei werden Symbol und Lauflänge als Paare gespeichert, z. B. (Symbol, Lauflänge). Diese Kodierung ist besonders effizient, wenn lange Läufe identischer Werte vorkommen, etwa in monochromen Bildern, Protokolldaten oder Texten mit vielen Leerräumen. Im Worst-Case, bei alphabetisch wechselnden Symbolen, kann RLE mehr Platz benötigen als die Originaldaten.

Anwendungsbereiche umfassen lossless Bild- und Video-Kompression, Druckdaten, Textverarbeitung mit vielen Wiederholungen sowie bestimmte Formen der Bioinformatik, etwa bei der Kompression redundanter Sequenzabschnitte. Variationen der Kodierung verwenden unterschiedliche Methoden zur Repräsentation der Lauflängen (z. B. variable Bitlängen oder Codes wie Golomb-Codes) und beeinflussen Effizienz und Entkodierungsgeschwindigkeit. Beispiele verdeutlichen typische Lauflängenverteilungen wie 3, 1, 2, 4 in einer kurzen Sequenz.