C＃压缩字节数组

Question

我对压缩算法了解不多。我正在寻找一种简单的压缩算法（或代码片段），它可以减小字节[,,]或字节[]的大小。我无法使用System.IO.Compression。此外，数据有很多重复。

我试着实现RLE算法（下面贴出来供您检查）。但是，它会产生1.2到1.8倍的数组。

public static class RLE 
{ 
    public static byte[] Encode(byte[] source) 
    { 
     List<byte> dest = new List<byte>(); 
     byte runLength; 

     for (int i = 0; i < source.Length; i++) 
     { 
      runLength = 1; 
      while (runLength < byte.MaxValue 
       && i + 1 < source.Length 
       && source[i] == source[i + 1]) 
      { 
       runLength++; 
       i++; 
      } 
      dest.Add(runLength); 
      dest.Add(source[i]); 
     } 

     return dest.ToArray(); 
    } 

    public static byte[] Decode(byte[] source) 
    { 
     List<byte> dest = new List<byte>(); 
     byte runLength; 

     for (int i = 1; i < source.Length; i+=2) 
     { 
      runLength = source[i - 1]; 

      while (runLength > 0) 
      { 
       dest.Add(source[i]); 
       runLength--; 
      } 
     } 
     return dest.ToArray(); 
    } 

} 

我还发现了一个基于java，string和integer的LZW实现。我已将其转换为C＃，结果看起来不错（代码如下）。但是，我不确定它是如何工作的，也不知道如何使它与字节而不是字符串和整数一起工作。

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<string, int> dictionary = new Dictionary<string, int>(); 
     for (int i = 0; i < dictSize; i++) 
      dictionary.Add("" + (char)i, i); 

     string w = ""; 
     List<int> result = new List<int>(); 

     for (int i = 0; i < 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<int, string> dictionary = new Dictionary<int, string>(); 
     for (int i = 0; i < dictSize; i++) 
      dictionary.Add(i, "" + (char)i); 

     string w = "" + (char)compressed[0]; 
     string result = w; 
     for (int i = 1; i < 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; 
    } 
} 

Answer 1

调查霍夫曼代码，这是一个非常简单的算法。基本上，对于更频繁出现的模式，使用更少的位，并且保留一个表格来表示它的编码方式。而且您必须在您的代码字中注明没有分隔符来帮助您解码。

Answer 2

看一看here。我使用此代码作为压缩我的一个工作项目的基础。不确定在Xbox 360 SDK中有多少.NET Framework是可访问的，因此不确定这对您有多好。

Answer 3

RLE算法的问题在于它太简单了。它在每个字节前加以及重复多少次，但这确实意味着在非重复字节的长范围内，每个单字节前缀为“1”。关于数据没有任何重复，这将双的文件大小。

这可以通过使用Code-type RLE来避免; 'Code'（也称为'Token'）将是一个可以有两个含义的字节;要么表示单个后面的字节重复了多少次，要么表示有多少非重复字节应该按原样复制。这两个代码之间的区别是通过启用最高位来实现的，这意味着该值仍然有7位可用，这意味着每个这样的代码的复制或重复的数量可以高达127.

这意味着即使在在最坏的情况下，最终尺寸只能比原始文件尺寸大1/127。

整个概念的一个很好的解释，再加上完整的工作（而且，事实上，大量优化）C＃代码，可以在这里找到：

http://www.shikadi.net/moddingwiki/RLE_Compression

注意，有时，这些数据将结束原因是大大小于，只是因为没有足够的重复字节让RLE工作。处理这种压缩失败的一个好方法是在最终数据中添加一个头部。如果您只是在开始处添加一个额外的字节，其值为0表示未压缩的数据，而另一个表示RLE压缩数据的值，则当RLE未能提供较小的结果时，您只需将其保存为未压缩的数据，并将0放在前面，并将最终数据将比原来的大一个字节。然后在另一侧的系统可以读取该起始字节，并使用它来确定下列数据是否应该解压缩或者只是复制。