String compression implementation in C#

Question

I wrote a method that reduces a string like aabcccccaaa to a2b1c5a3

My implementation:

string Compress(string str)
{
    StringBuilder builder = new StringBuilder();
    using(TextReader reader = new StringReader(str))
    {
        while(reader.Peek() != - 1){
            char c = (char)reader.Read();
            int n = 1;
            while(reader.Peek() == c) {
                reader.Read();
                n++;
            }
            builder.AppendFormat("{0}{1}",c,n);
        }
    }
    return builder.ToString();
}

What do you think about this, is there a better way to do this?

Answer 1

You can use a regular expression to match a range of repeated characters and replace it with the character and the count:

public static string Compress(string str) {
  return Regex.Replace(str, @"(.)\1*", m => m.Groups[1].Value + m.Value.Length);
}

If that is better or not is up for debate, but it is at least a lot shorter.

You can also make it simpler using a regular loop and access the characters by index instead of using a StringReader. That makes it easier to compare the characters next to each other:

public static string Compress(string str) {
  StringBuilder builder = new StringBuilder();
  for (int i = 1, cnt = 1; i <= str.Length; i++, cnt++) {
    if (i == str.Length || str[i] != str[i - 1]) {
      builder.Append(str[i - 1]).Append(cnt);
      cnt = 0;
    }
  }
  return builder.ToString();
}

Answer 2

That's a perfectly cromulent implementation. I would just suggest making the style more consistent, with regards to spacing and braces, and maybe using Append instead of AppendFormat:

var builder = new StringBuilder();
using (var reader = new StringReader(str))
{
    while (reader.Peek() != -1)
    {
        char c = (char)reader.Read();
        int n = 1;
        while (reader.Peek() == c)
        {
            reader.Read();
            n++;
        }

        builder.Append(c).Append(n);
    }
}

return builder.ToString();

StringReader might be overkill for the situation; I find it to be of most use for its ReadLine method, which we're not using here. You might want to consider something like this:

var compressed = new StringBuilder();
int start = 0;
while (start < input.Length)
{
    char c = input[start];
    int end = start + 1;
    while (end < input.Length && input[end] == c)
    {
        end++;
    }

    compressed.Append(c).Append(end - start);
    start = end;
}

return compressed.ToString();

Answer 3

You need to consider the type of String that you wish to compress. If you are expecting multiple repeating characters then your system will work. However, if you wish to compress text, then this system will actually increase the size as few words have multiple repeating characters.

If you can guarantee that your string will be low-ASCII (no Unicode, no box-chars) then you can use the high-bit to signal your code to treat that character as a loop index.

if (c > 127) then n = c-127;

Also, you should be storing your repeat index as a value 'A' not a string char "65".

There are GNUish libraries available for RLE encoding, and it might be easier for you to use one of those.