title: C# compress a byte array
body: <p>I do not know much about compression algorithms. I am looking for a simple compression algorithm (or code snippet) which can reduce the size of a byte[,,] or byte[]. I cannot make use of System.IO.Compression. Also, the data has lots of repetition.</p>
  
  <p>I tried implementing the RLE algorithm (posted below for your inspection). However, it produces array's 1.2 to 1.8 times larger. </p>
  
  <pre><code>public static class RLE
  {
      public static byte[] Encode(byte[] source)
      {
          List&lt;byte&gt; dest = new List&lt;byte&gt;();
          byte runLength;
  
          for (int i = 0; i &lt; source.Length; i++)
          {
              runLength = 1;
              while (runLength &lt; byte.MaxValue 
                  &amp;&amp; i + 1 &lt; source.Length 
                  &amp;&amp; source[i] == source[i + 1])
              {
                  runLength++;
                  i++;
              }
              dest.Add(runLength);
              dest.Add(source[i]);
          }
  
          return dest.ToArray();
      }
  
      public static byte[] Decode(byte[] source)
      {
          List&lt;byte&gt; dest = new List&lt;byte&gt;();
          byte runLength; 
  
          for (int i = 1; i &lt; source.Length; i+=2)
          {
              runLength = source[i - 1];
  
              while (runLength &gt; 0)
              {
                  dest.Add(source[i]);
                  runLength--;
              }
          }
          return dest.ToArray();
      }
  
  }
  </code></pre>
  
  <p>I have also found a java, string and integer based, LZW implementation. I have converted it to C# and the results look good (code posted below). However, I am not sure how it works nor how to make it work with bytes instead of strings and integers.   </p>
  
  <pre><code>public class LZW
  {
      /* Compress a string to a list of output symbols. */
      public static int[] compress(string uncompressed)
      {
          // Build the dictionary.
          int dictSize = 256;
          Dictionary&lt;string, int&gt; dictionary = new Dictionary&lt;string, int&gt;();
          for (int i = 0; i &lt; dictSize; i++)
              dictionary.Add("" + (char)i, i);
  
          string w = "";
          List&lt;int&gt; result = new List&lt;int&gt;();
  
          for (int i = 0; i &lt; uncompressed.Length; i++)
          {
              char c = uncompressed[i];
              string wc = w + c;
              if (dictionary.ContainsKey(wc))
                  w = wc;
              else
              {
                  result.Add(dictionary[w]);
                  // Add wc to the dictionary.
                  dictionary.Add(wc, dictSize++);
                  w = "" + c;
              }
          }
  
          // Output the code for w.
          if (w != "")
              result.Add(dictionary[w]);
          return result.ToArray();
      }
  
      /* Decompress a list of output ks to a string. */
      public static string decompress(int[] compressed)
      {
          int dictSize = 256;
          Dictionary&lt;int, string&gt; dictionary = new Dictionary&lt;int, string&gt;();
          for (int i = 0; i &lt; dictSize; i++)
              dictionary.Add(i, "" + (char)i);
  
          string w = "" + (char)compressed[0];
          string result = w;
          for (int i = 1; i &lt; compressed.Length; i++)
          {
              int k = compressed[i];
              string entry = "";
              if (dictionary.ContainsKey(k))
                  entry = dictionary[k];
              else if (k == dictSize)
                  entry = w + w[0];
  
              result += entry;
  
              // Add w+entry[0] to the dictionary.
              dictionary.Add(dictSize++, w + entry[0]);
  
              w = entry;
          }
  
          return result;
      }
  }
  </code></pre>