C # - кодирование Хаффмана для большого файла занимает слишком много времени - PullRequest
Новая
       9

C # - кодирование Хаффмана для большого файла занимает слишком много времени

0 голосов
/ 15 ноября 2018

Я пытаюсь реализовать кодирование Хаффмана в C #.У меня проблема с кодированием больших файлов, так как это занимает слишком много времени.Например, для кодирования двоичного файла размером 11 МБ в режиме отладки требуется 10 секунд.И я даже не удосужился дождаться, пока моя программа завершит работу с файлом размером 27 МБ.

Вот проблемный цикл: 

            BitArray bits = new BitArray(8);
            byte[] byteToWrite = new byte[1];
            byte bitsSet = 0;

            while ((bytesRead = inputStream.Read(buffer, 0, 4096)) > 0) // Read input in chunks
            {
                for (int i = 0; i < bytesRead; i++)
                {
                    for (int j = 0; j < nodesBitStream[buffer[i]].Count; j++)
                    {
                        if (bitsSet != 8)
                        {
                            bits[bitsSet] = nodesBitStream[buffer[i]][j];
                            bitsSet++;
                        }
                        else
                        {
                            bits.CopyTo(byteToWrite, 0);
                            outputStream.Write(byteToWrite, 0, byteToWrite.Length);
                            bits = new BitArray(8);
                            bitsSet = 0;

                            bits[bitsSet] = nodesBitStream[buffer[i]][j];
                            bitsSet++;
                        }
                    }
                }
            }

nodesBitStream - это Dictionary<byte, List<bool>>.List<bool> - это представление пути от корня дерева Хаффмана до конечного узла, содержащего определенный символ, представленный как byte.

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

Ответы [ 2 ]

0 голосов
/ 15 ноября 2018

Я действительно не знаю, как работает алгоритм, но, глядя на ваш код, можно выделить две вещи:

  1. Кажется, вы используете словарь для индексации с помощьюбайт.Может быть, простой List<bool>[] быстрее, используя buffer[i] для индексации в нем.Цена памяти, которую вы бы заплатили, довольно низкая.Используя массив, вы обмениваетесь поисками со смещениями, которые быстрее.Вы делаете там несколько поисков.

  2. Почему вы создаете bits на каждой итерации?В зависимости от того, сколько итераций вы выполняете, это может в конечном итоге оказать давление на GC.Кажется, в этом нет необходимости, вы, по сути, перезаписываете каждый бит и выплевываете его каждые 8 ​​бит, поэтому просто перезапишите его, не обновляйте его;использовать один и тот же экземпляр снова и снова.

0 голосов
/ 15 ноября 2018

Работа по крупицам - это много дополнительной работы. Кроме того, в то время как Dictionary<byte, TVal> является приличным, простой массив еще быстрее.

Коды Хаффмана также могут быть представлены в виде пары целых чисел, одно для длины (в битах), а другое содержит биты. В этом представлении вы можете обработать символ за пару быстрых операций, например (не проверено): 

BinaryWriter w = new BinaryWriter(outStream);
uint buffer = 0;
int bufbits = 0;
for (int i = 0; i < symbols.Length; i++)
{
    int s = symbols[i];
    buffer <<= lengths[s];  // make room for the bits
    bufbits += lengths[s];  // buffer got longer
    buffer |= values[s];    // put in the bits corresponding to the symbol

    while (bufbits >= 8)    // as long as there is at least a byte in the buffer
    {
        bufbits -= 8;       // forget it's there
        w.Write((byte)(buffer >> bufbits)); // and save it
    }
}
if (bufbits != 0)
    w.Write((byte)(buffer << (8 - bufbits)));

Или какой-то другой вариант, например, вы можете заполнить байты наоборот или сохранить байты в массиве и делать большие записи и т. Д.

Этот код требует, чтобы длина кода была ограничена максимум 25 битами, обычно другие требования еще ниже, чтобы ограничить этот предел. Огромная длина кода не требуется для получения хорошей степени сжатия.

...