Lauflängencodierung - Run-length encoding

Lauflängencodierung ( RLE ) ist eine Form von verlustfreien Datenkompression , in denen läuft von Daten (Sequenzen , in denen der gleiche Datenwert in vielen aufeinanderfolgenden Datenelementen auftritt) als ein einziger Datenwert gespeichert und zählen, anstatt wie die ursprüngliche Lauf . Dies ist am effizientesten bei Daten, die viele solcher Durchläufe enthalten, zum Beispiel einfache grafische Bilder wie Symbole, Strichzeichnungen, Conways Game of Life und Animationen. Bei Dateien, die nicht viele Läufe haben, kann RLE die Dateigröße erhöhen.

RLE kann auch verwendet werden, um sich auf ein frühes Grafikdateiformat zu beziehen, das von CompuServe zum Komprimieren von Schwarzweißbildern unterstützt wird , aber weithin durch das spätere Graphics Interchange Format (GIF) ersetzt wurde. RLE bezieht sich auch auf ein wenig verwendetes Bildformat in Windows 3.x mit der Erweiterung rle, einer lauflängencodierten Bitmap, die zum Komprimieren des Windows 3.x-Startbildschirms verwendet wird.

Beispiel

Betrachten Sie einen Bildschirm mit reinem schwarzen Text auf einem einfarbigen weißen Hintergrund über einer hypothetischen Scanlinie. Er kann wie folgt gerendert werden:

12W1B12W3B24W1B14W2W

Dies kann als eine Folge von zwölf Ws interpretiert werden, ein B, zwölf Ws, drei Bs usw. und stellt die ursprünglichen 67 Zeichen in nur 18. Während das tatsächliche Format für die Speicherung von Bildern verwendet , ist in der Regel binär anstatt ASCII - Zeichen so bleibt das Prinzip das gleiche. Sogar binäre Datendateien können mit dieser Methode komprimiert werden; Dateiformatspezifikationen schreiben häufig wiederholte Bytes in Dateien als Füllraum vor. Neuere Komprimierungsmethoden wie DEFLATE verwenden jedoch häufig LZ77- basierte Algorithmen, eine Verallgemeinerung der Lauflängencodierung, die Abfolgen von Zeichenfolgen (wie BWWBWWBWWBWW) nutzen kann.

Die Lauflängencodierung kann auf verschiedene Weise ausgedrückt werden, um Dateneigenschaften sowie zusätzliche Komprimierungsalgorithmen zu berücksichtigen. Zum Beispiel kodiert eine beliebte Methode Lauflängen nur für Läufe von zwei oder mehr Zeichen, verwendet ein "Escape"-Symbol, um Läufe zu identifizieren, oder verwendet das Zeichen selbst als Escape, so dass jedes Mal, wenn ein Zeichen zweimal erscheint, es einen Lauf anzeigt. Im vorherigen Beispiel würde dies Folgendes ergeben:

WW12BWW12BB3WW24BWW14

Dies würde als ein Lauf von zwölf Ws, a B, ein Lauf von zwölf Ws, ein Lauf von drei B usw. interpretiert werden. Bei Daten, bei denen Läufe weniger häufig sind, kann dies die Komprimierungsrate erheblich verbessern.

Eine andere Sache ist die Anwendung zusätzlicher Kompressionsalgorithmen. Selbst bei extrahierten Läufen können die Häufigkeiten verschiedener Zeichen groß sein, was eine weitere Komprimierung ermöglicht; Wenn jedoch die Lauflängen in die Datei an den Orten geschrieben werden, an denen die Läufe aufgetreten sind, unterbricht das Vorhandensein dieser Zahlen den normalen Fluss und erschwert die Komprimierung. Um dies zu überwinden, trennen einige Lauflängencodierer die Daten- und Escape-Symbole von den Lauflängen, so dass die beiden unabhängig gehandhabt werden können. Für die Beispieldaten würde dies zwei Ausgaben ergeben, die Zeichenfolge " WWBWWBBWWBWW" und die Zahlen ( 12,12,3,24,14).

Geschichte und Anwendungen

Bereits 1967 wurden Run-Length-Codierung (RLE) bei der Übertragung analoger Fernsehsignale eingesetzt. 1983 wurde die Run-Length-Codierung von Hitachi patentiert . RLE eignet sich besonders gut für palettenbasierte Bitmap-Bilder wie Computersymbole und war eine beliebte Bildkomprimierungsmethode bei frühen Online-Diensten wie CompuServe, bevor anspruchsvollere Formate wie GIF aufkamen . Es funktioniert nicht gut bei Halbtonbildern wie Fotos, obwohl JPEG es bei den Koeffizienten verwendet, die nach der Transformation und Quantisierung von Bildblöcken verbleiben .

Gängige Formate für lauflängencodierte Daten umfassen Truevision TGA , PackBits , PCX und ILBM . Die International Telecommunication Union beschreibt auch einen Standard zur Codierung von Lauflängenfarbe für Faxgeräte , bekannt als T.45. Der Standard, der mit anderen Techniken zur modifizierten Huffman-Codierung kombiniert wird , ist relativ effizient, da die meisten Faxdokumente im Allgemeinen weiße Flächen mit gelegentlichen schwarzen Unterbrechungen sind.

Siehe auch

Verweise

Externe Links