С# сжать массив байтов

Я не очень хорошо разбираюсь в алгоритмах сжатия. Я ищу простой алгоритм сжатия (или фрагмент кода), который может уменьшить размер байта [,,] или байта []. Я не могу использовать 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();
    }

}

Я также нашел реализацию LZW на основе java, строк и целых чисел. Я преобразовал его в С#, и результаты выглядят хорошо (код размещен ниже). Однако я не уверен, как это работает и как заставить его работать с байтами вместо строк и целых чисел.

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;
    }
}

person zfedoran    schedule 17.07.2010    source источник
comment
Я не могу использовать System.IO.Compression - почему?   -  person Mitch Wheat    schedule 17.07.2010
comment
чтобы немного расширить то, что сказал Митч, есть и другие библиотеки (например, SharpZipLib) поэтому понимание того, почему вы не можете использовать существующие вещи в рамках, поможет выяснить, какие другие варианты могут работать или нет.   -  person James Manning    schedule 17.07.2010
comment
Ну, его нет на моей платформе (xbox 360).   -  person zfedoran    schedule 17.07.2010
comment
Добавлен тег xbox360, потому что он несколько актуален (по крайней мере, он проясняет вопрос, это домашнее задание?)   -  person Brendan Long    schedule 17.07.2010


Ответы (3)


Посмотрите здесь. Я использовал этот код в качестве основы для сжатия в одном из моих рабочих проектов. Не уверен, какая часть .NET Framework доступна в Xbox 360 SDK, поэтому не уверен, насколько хорошо это будет работать для вас.

person GrahamMoore    schedule 17.07.2010

Посмотрите на коды Хаффмана, это довольно простой алгоритм. По сути, используйте меньше битов для шаблонов, которые появляются чаще, и ведите таблицу того, как они закодированы. И вы должны учитывать в своих кодовых словах, что в них нет разделителей, помогающих вам декодировать.

person gtrak    schedule 17.07.2010

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

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

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

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

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

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

person Nyerguds    schedule 10.01.2018