Magic Bookof Algorithms
/
EN

KompressionCMP-01

Lauflängenkodierung (RLE)

Statt zwölfmal W zu speichern, merkt man sich einfach: zwölfmal W.

Laufzeit
O(n)
Zusatzspeicher
O(n)
Verlustfrei
ja
Schlechtester Fall
doppelte Größe

01Worum es geht

Die Lauflängenkodierung ist die einfachste Form von Kompression, die es gibt. Sie ersetzt jede Folge gleicher Zeichen durch die Anzahl und das Zeichen: Aus WWWWWWWWWWWWB wird 12W1B.

Verlustfrei ist sie dabei immer, das Original lässt sich exakt zurückgewinnen. Sie lohnt sich aber nur, wenn es lange Wiederholungen gibt: bei Schwarzweißbildern, Faxen, einfachen Pixelgrafiken oder Sensordaten, die sich selten ändern.

WWWWWWWWWWWWB
12W1B
Eine lange Folge gleicher Zeichen schrumpft auf Anzahl und Zeichen zusammen.

02So funktioniert es

Kodieren läuft einmal durch die Eingabe:

  1. Merke dir das aktuelle Zeichen.
  2. Zähle, wie oft es sich unmittelbar wiederholt.
  3. Schreibe Anzahl und Zeichen in die Ausgabe und springe hinter die gezählte Folge.

Dekodieren ist der Weg zurück. Da eine Anzahl mehrere Ziffern haben kann, werden erst alle Ziffern gelesen, bis ein Zeichen auftaucht. Das Zeichen wird dann so oft ausgegeben, wie die Zahl es angibt.

Beide Richtungen sehen jedes Zeichen genau einmal an, deshalb ist der Aufwand linear.

03Implementierung

MagicBook.Algorithms/Compression/RunLengthEncoding.csC#
using System.Text;

public static class RunLengthEncoding
{
    // Ersetzt jede Folge gleicher Zeichen durch "Anzahl + Zeichen": aus "aaab" wird "3a1b".
    public static string Encode(string input)
    {
        var result = new StringBuilder();
        var index = 0;

        while (index < input.Length)
        {
            var current = input[index];
            var runLength = 1;

            // Zählen, wie oft sich das aktuelle Zeichen hier wiederholt.
            while (index + runLength < input.Length && input[index + runLength] == current)
                runLength++;

            result.Append(runLength).Append(current);
            index += runLength;
        }

        return result.ToString();
    }

    // Macht aus "3a1b" wieder "aaab".
    public static string Decode(string encoded)
    {
        var result = new StringBuilder();
        var index = 0;

        while (index < encoded.Length)
        {
            // Eine Anzahl kann mehrere Ziffern haben, also Ziffern lesen, bis ein Zeichen auftaucht.
            var digits = 0;
            while (char.IsDigit(encoded[index + digits]))
                digits++;

            var count = int.Parse(encoded.AsSpan(index, digits));

            result.Append(encoded[index + digits], count);
            index += digits + 1;
        }

        return result.ToString();
    }
}

04Beispiel

MagicBook.Console/Examples/RunLengthEncodingExample.csC#
var input = "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWB";

var encoded = RunLengthEncoding.Encode(input);
Console.WriteLine(encoded);

// Kürzer als die Eingabe - aber nur, weil sie lange Wiederholungen enthält.
Console.WriteLine($"{input.Length} -> {encoded.Length} characters");

Console.WriteLine(RunLengthEncoding.Decode(encoded) == input);
Ausgabe der Konsole
12W1B12W3B24W1B
53 -> 15 characters
True

05Gut zu wissen

  • Im schlechtesten Fall wird das Ergebnis doppelt so groß wie die Eingabe, nämlich wenn sich kein einziges Zeichen wiederholt. Aus abc wird 1a1b1c.
  • Deshalb schreiben echte Formate die Anzahl nur bei Wiederholungen und markieren sonst unkomprimierte Blöcke. Genau das macht zum Beispiel PackBits in TIFF-Dateien.
  • Enthält die Eingabe selbst Ziffern, ist dieses einfache Format mehrdeutig. In der Praxis kodiert man deshalb Bytes mit einer festen Längenangabe statt Text.