Tech Qu: Write a function to do RLE (Run Length Encoding)

  • Given a string, compress using run-length encoding. Example:
    Input: aaabbac
    Output: a3b2ac

First Pass – simplistic solution

Code Snippet
  1. /// <summary>
  2.  /// Assuming no digits in string.
  3.  /// </summary>
  4.  /// <param name="s"></param>
  5.  /// <returns></returns>
  6.  public static string RLEEncode1(string s)
  7.  {
  8.    var sb = new StringBuilder();
  9.    int count = 1;
  10.    char current = s[0];
  11.    for (int i = 1; i < s.Length; i++)
  12.    {
  13.      if (current == s[i])
  14.      {
  15.        count++;
  16.      }
  17.      else
  18.      {
  19.        if (count > 1)
  20.          sb.AppendFormat("{1}{0}", count, current);
  21.        else
  22.          sb.Append(current);
  23.        count = 1;
  24.        current = s[i];
  25.      }
  26.    }
  27.    if (count > 1)
  28.      sb.AppendFormat("{1}{0}", count, current);
  29.    else
  30.      sb.Append(current);  
  31.    return sb.ToString();
  32.  }

A better solution is to assume that there are no characters > 127 in the string and using the range 128-255 as counter indicators. This solution is shown below.

 

Code Snippet
  1. public static string RLEEncode2(string s)
  2.     {
  3.       var sb = new StringBuilder();
  4.       int count = 1;
  5.       char current = s[0];
  6.       for (int i = 1; i < s.Length; i++)
  7.       {
  8.         if (current == s[i])
  9.         {
  10.           count++;
  11.           if(count > 127)
  12.           {
  13.               
  14.               sb.Append(current);
  15.               sb.Append((char)(count + 127));
  16.               count = 1;
  17.           }          
  18.         }
  19.         else
  20.         {
  21.           if (count > 1)
  22.           {
  23.             
  24.             sb.Append(current);
  25.             sb.Append((char)(count + 127));
  26.           }
  27.           else
  28.             sb.Append(current);
  29.           count = 1;
  30.           current = s[i];
  31.         }
  32.       }
  33.       if (count > 1)
  34.       {
  35.         {
  36.           
  37.           sb.Append(current);
  38.           sb.Append((char)(count+127));
  39.         }          
  40.       }
  41.       else
  42.         sb.Append(current);  
  43.       return sb.ToString();
  44.     }

Inspecting the string, we see the result:

[0]    97 'a'    char
[1]    130 '‚'    char
[2]    98 'b'    char
[3]    129 ''    char
[4]    97 'a'    char
[5]    99 'c'    char

Comments

Popular posts from this blog

Simple WP7 Mango App for Background Tasks, Toast, and Tiles: Code Explanation

Yet once more into the breech (of altered programming logic)

How to convert SVG data to a Png Image file Using InkScape