Получение битового потока из целых чисел и вывод его в файл

Рейтинг: 1Ответов: 1Опубликовано: 09.04.2015

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

Результатом кодирования Хаффмана является массив пар символ-код, где код — целое число произвольной битовой длины. Для достижения сжатия из кодов следует получать битовый поток, который записывается в закодированный файл.

В приведённом ответе makeAndSlice() создаёт битовый поток BitsStream из data[] и отсекает по 8 старших значимых битов в OutputByte по мере накопления их в потоке (while (BitsStreamCount >= ByteBits)). Чтобы получить лаконичный ответ, массивом data[] подменяется последовательность кодовых значений символов исходного файла.

Например, пускай data[] = {110, 1110, 11110, 1110, 110, 11110, 1110, 1}, где все числа записаны в двоичном представлении, тогда makeAndSlice() создаёт битовый поток 11011101111011101101111011101 и разделяет его на следующий список байтов: {11011101, 11101110, 11011110, 11101000}.

c# битовые-операции huffman
Источник: Stack Overflow на русском

Ответы

▲ 1

Ну, а в чём проблема? Всё делается легко, нужно лишь решить, как вы хотите кодировать «поток битов».

Например (для конвенции little endian):

int* data; // данные
size_t num_ints; // сколько их

size_t curr_int; // текущее слово, инициализируется нулём
size_t curr_bit; // текущий бит в слове, инициализируется нулём
#define BITS_IN_CHAR 8

int next_bit()
{
    if (curr_int >= num_ints)
        return -1; // конец потока

    int result = data[curr_int] & (1 << curr_bit);
    curr_bit++;
    if (curr_bit > sizeof(int) * BITS_IN_CHAR)
    {
        curr_bit = 0;
        curr_int++;
    }
    return result ? 1 : 0;
}