Как сделать реализацию памяти Huffman Agorithm?

Question

У меня есть алгоритм кода Хаффмана, который сжимает символы в последовательности битов произвольной длины, которая меньше размера по умолчанию char (8 бит на большинстве современных платформ)

Если код Хаффмана сжимает 8-битный символ в 3 бита, как мне представить это 3-битное значение в памяти?Чтобы продолжить, как мне объединить несколько сжатых символов в сжатое представление?

Например, рассмотрим l, который равен "00000" (5x8 бит, поскольку 0 также является символом).Как мне представить l с 00000 (5 бит) вместо последовательности символов?

Реализация AC или C ++ предпочтительна.

Answer 1

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

В C это относительно простая функция, состоящая из сдвига влево(<<) и побитовое ИЛИ (|).Вот функция, с примером, чтобы сделать ее работоспособной.Чтобы увидеть его с более подробными комментариями, пожалуйста, обратитесь к этому GitHub gist .

#include <stdlib.h>
#include <stdio.h>

#define BYTE_SIZE 8

size_t compress_code(const int *code, const size_t code_length, unsigned char **compressed)
{
    if (code == NULL || code_length == 0 || compressed == NULL) {
        return 0;
    }
    size_t compressed_length = (code_length + BYTE_SIZE - 1) / BYTE_SIZE;
    *compressed = calloc(compressed_length, sizeof(char));
    for (size_t char_counter = 0, i = 0; char_counter < compressed_length && i < code_length; ++i) {
        if (i > 0 && (i % BYTE_SIZE) == 0) {
            ++char_counter;
        }
        // Shift the last bit to be set left by one
        (*compressed)[char_counter] <<= 1;
        // Put the next bit onto the end of the unsigned char
        (*compressed)[char_counter] |= (code[i] & 1);
    }
    // Pad the remaining space with 0s on the right-hand-side
    (*compressed)[compressed_length - 1] <<= compressed_length * BYTE_SIZE - code_length;
    return compressed_length;
}

int main(void)
{
    const int code[] = { 0, 1, 0, 0, 0, 0, 0, 1,   // 65: A
                         0, 1, 0, 0, 0, 0, 1, 0 }; // 66: B
    const size_t code_length = 16;
    unsigned char *compressed = NULL;
    size_t compressed_length = compress_code(code, code_length, &compressed);
    for (size_t i = 0; i < compressed_length; ++i) {
        printf("%c\n", compressed[i]);
    }
    return 0;
}

Затем вы можете просто записать символы в массиве в файл или даже скопировать память массиванепосредственно в файл, чтобы записать сжатый вывод.

Чтение сжатых символов в биты, что позволит вам проходить по дереву Хаффмана для декодирования, выполняется с правыми сдвигами (>>) и проверкой самого правогобит с побитовым И (&).

Answer 2

Теперь, когда этот вопрос вновь открыт ...

Чтобы создать переменную, которая содержит переменное число бит, мы просто используем младшие биты одного unsigned int для хранения битов, ииспользуйте другой unsigned int, чтобы запомнить, сколько битов мы сохранили.

При записи файла, сжатого Хаффманом, мы ждем, пока у нас будет сохранено как минимум 8 бит.Затем мы записываем char, используя верхние 8 битов, и вычитаем 8 из сохраненного количества бит.из 8 и записать символы.

В C ++ полезно инкапсулировать вывод в некоторый класс BitOutputStream, например:

class BitOutputStream
{
    std::ostream m_out;
    unsigned m_bitsPending;
    unsigned m_numPending;

    public:
    BitOutputStream(const char *fileName)
        :m_out(... /* you can do this part */)
    {
        m_bitsPending = 0;
        m_numPending = 0;
    }

    // write out the lower <count> bits of <bits>
    void write(unsigned bits, unsigned count)
    {
       if (count > 16)
       {
           //do it in two steps to prevent overflow
           write(bits>>16, count-16);
           count=16;
       }
       //make space for new bits
       m_numPending += count;
       m_bitsPending <<= count;

       //store new bits
       m_bitsPending |= (bits & ((1<<count)-1));

       //write out any complete bytes
       while(m_numPending >= 8)
       {
           m_numPending-=8;
           m_out.put((char)(m_bitsPending >> m_numPending));
       }
    }

    //write out any remaining bits
    void flush()
    {
        if (m_numPending > 0)
        {
            m_out.put((char)(m_bitsPending << (8-m_numPending)));
        }
        m_bitsPending = m_numPending = 0;
        m_out.flush();
    }
}