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

}

Я также нашел реализацию LZW на основе Java, строки и целых чисел.Я преобразовал его в 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

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

Answer 2

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

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

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

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

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

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

Answer 3

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