Magic Bookof Algorithms
/
DE

CompressionCMP-01

Run-Length Encoding (RLE)

Instead of storing W twelve times, simply remember: twelve times W.

Running time
O(n)
Extra memory
O(n)
Lossless
yes
Worst case
twice the size

01What it is about

Run-length encoding is the simplest form of compression there is. It replaces every run of equal characters with the count and the character: WWWWWWWWWWWWB becomes 12W1B.

It is always lossless, the original can be restored exactly. But it only pays off when there are long repetitions: black and white images, faxes, simple pixel graphics or sensor data that rarely changes.

WWWWWWWWWWWWB
12W1B
A long run of equal characters collapses into a count and the character.

02How it works

Encoding walks through the input once:

  1. Remember the current character.
  2. Count how often it repeats right here.
  3. Write the count and the character to the output and jump behind the counted run.

Decoding is the way back. Since a count can have several digits, all digits are read first until a character shows up. That character is then written out as often as the number says.

Both directions look at every character exactly once, which makes the effort linear.

03Implementation

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

public static class RunLengthEncoding
{
    // Replaces every run of equal characters by "count + character": "aaab" becomes "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;

            // Count how often the current character repeats right here.
            while (index + runLength < input.Length && input[index + runLength] == current)
                runLength++;

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

        return result.ToString();
    }

    // Turns "3a1b" back into "aaab".
    public static string Decode(string encoded)
    {
        var result = new StringBuilder();
        var index = 0;

        while (index < encoded.Length)
        {
            // A count can have more than one digit, so read digits until a character appears.
            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();
    }
}

04Example

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

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

// Shorter than the input - but only because it contains long runs.
Console.WriteLine($"{input.Length} -> {encoded.Length} characters");

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

05Good to know

  • In the worst case the result becomes twice as large as the input, namely when no character repeats at all. abc turns into 1a1b1c.
  • That is why real formats only write a count for repetitions and mark uncompressed blocks otherwise. PackBits in TIFF files does exactly that.
  • If the input contains digits itself, this simple format is ambiguous. In practice you therefore encode bytes with a fixed length field instead of text.