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. Я использовал этот код в качестве основы для сжатия в одном из моих рабочих проектов. Не знаете, какая часть .NET Framework доступна в SDK Xbox 360, поэтому не уверен, насколько хорошо это сработает для вас.

Answer 3

Проблема с этим алгоритмом RLE заключается в том, что это слишком просто. Он префикс каждый байт, сколько раз это повторяется, но это означает, что в длинных диапазонах неповторяющихся байтов каждый одиночный байт имеет префикс «1». По данным без повторений это будет double размер файла.

Этого можно избежать, используя вместо этого код типа Rode; «Код» (также называемый «токен») будет байтом, который может иметь два значения; либо он указывает, сколько раз повторяется один следующий байт, или он указывает, сколько последующих не повторяющихся байтов следует скопировать, как они есть. Разница между этими двумя кодами производится путем включения наивысшего бита, что означает, что для этого значения имеется еще 7 бит, то есть количество копий или повторений на такой код может быть до 127.

Это означает, что даже в наихудшие сценарии, конечный размер может быть только на 1/127 больше размера исходного файла.

Хорошее объяснение всей концепции, а также полный рабочий (и, на самом деле, сильно оптимизированы) C# код, можно найти здесь:

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

Обратите внимание, что иногда, данные будут в конечном итоге больше, чем оригинал в любом случае, просто потому, что в нем не хватает повторяющихся байтов для работы RLE. Хороший способ справиться с такими ошибками сжатия - это добавить заголовок к вашим окончательным данным. Если вы просто добавляете дополнительный байт в начале, который находится на 0 для несжатых данных и 1 для сжатых данных RLE, тогда, когда RLE не дает меньший результат, вы просто сохраняете его несжатым, с 0 впереди и ваши окончательные данные будет на один байт больше оригинала. Затем система с другой стороны может прочитать этот стартовый байт и использовать это, чтобы определить, должны ли несжатые или просто скопировать следующие данные.