Lab 5 — Principles of Data Compression (RLE)

Purpose

Practical introduction to lossless data compression using the RLE (Run Length Encoding) algorithm — the simplest and fastest compression method, used in PCX image files.

Theory

RLE replaces sequences of repeating characters with a character + count pair:

Input:  AAAAAAAAAAAAAABBBBBBBBBBCCCC  (28 chars)
Output: A14B10C4                      (8 chars)

Step 1 — Hello RLE

class HelloRLE
{
    static void Main()
    {
        Console.WriteLine("Hello RLE");
    }
}

Step 2 — RLE class stub

public class RLE
{
    public string str = "";
    public void rle(string s)
    {
        str = "A14B10C4";
        Console.WriteLine(s + " transforms to " + str);
    }
}
class HelloRLE
{
    static void Main()
    {
        RLE r = new RLE();
        r.rle("AAAAAAAAAAAAAABBBBBBBBBBCCCC");
        Console.WriteLine(r.str);
    }
}

Step 3 — Iterate over characters

public void rle(string s)
{
    char[] masChar = s.ToCharArray();
    for (int i = 0; i < masChar.Length - 1; i++)
        Console.WriteLine(i + ":" + masChar[i]);
}

Step 4 — Count repeating characters

public void rle(string s)
{
    int count = 1;
    char[] masChar = s.ToCharArray();
    for (int i = 0; i < masChar.Length - 1; i++)
    {
        if (masChar[i] == masChar[i + 1])
            count++;
        else
        {
            if (count == 1)
                str += masChar[i];
            else
            {
                str += masChar[i] + count.ToString();
                count = 1;
            }
        }
    }
    if (count == 1)
        str += masChar[masChar.Length - 1];
    else
        str += masChar[masChar.Length - 1] + count.ToString();
}

Part II — Decompression (Advanced)

public string rle_dec(string s)
{
    string result = "";
    int i = 0;
    while (i < s.Length)
    {
        char ch = s[i++];
        string numStr = "";
        while (i < s.Length && char.IsDigit(s[i]))
            numStr += s[i++];
        int count = numStr == "" ? 1 : int.Parse(numStr);
        result += new string(ch, count);
    }
    return result;
}
// rle_dec("A14B10C4") => "AAAAAAAAAAAAAABBBBBBBBBBCCCC"

Live Demo

Enter a string and run the C# RLE algorithm on the server.

Code-behind (C#)

// Lab 5 - RLE
protected void btnEncode_Click(object sender, EventArgs e)
{
    string input = txtInput.Text;
    var sb = new StringBuilder();
    int i = 0;
    while (i < input.Length)
    {
        char c = input[i]; int count = 1;
        while (i + count < input.Length && input[i + count] == c) count++;
        sb.Append(count > 1 ? c.ToString() + count : c.ToString());
        i += count;
    }
    string output = sb.ToString();
}

protected void btnDecode_Click(object sender, EventArgs e)
{
    string input = txtInput.Text;
    var sb = new StringBuilder();
    int i = 0;
    while (i < input.Length)
    {
        char c = input[i]; i++;
        string numStr = "";
        while (i < input.Length && char.IsDigit(input[i])) { numStr += input[i]; i++; }
        int count = numStr.Length > 0 ? int.Parse(numStr) : 1;
        sb.Append(new string(c, count));
    }
    string output = sb.ToString();
}

Conclusion

RLE is effective for data with long runs of repeating bytes such as raster images. Its weakness is a low compression ratio when there are few or short repetitions.