кодирование Хаффмана

Question

Я пытаюсь реализовать алгоритм Хаффмана для сжатия, который требует записи битов переменной длины в файл. Есть ли способ в C ++ для записи данных переменной длины с 1-битной гранулярностью в файл?

Answer 1

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

Вы можете использовать битовый набор , чтобы упростить манипулирование битами, а затем использовать ofstream для записи в файл. Если вы не хотите использовать битовый набор, вы можете использовать побитовые операторы для манипулирования данными перед их сохранением.

Answer 2

Наименьшее количество битов, которые вы можете получить и сохранить, составляет 8 = 1 байт. Вы можете получить доступ к битам в байтах, используя битовые операторы ^ & |.

Вы можете установить n-й бит на 1, используя:

my_byte = my_byte | (1 << n);

где n от 0 до 7.

Вы можете установить n-й бит на 0, используя:

my_byte = my_byte & ((~1) << n);

Вы можете переключать n-й бит, используя:

my_byte = my_byte ^ (1 << n);

Подробнее здесь .

Answer 3

Вся необходимая информация о битовом тиддлинге находится здесь:
Как установить, очистить и переключить один бит?

Но самый маленький объект, который вы можете поместить в файл, - это байт.
Я использовал бы dynamic_bitset и каждый раз, когда размер становился больше 8, извлекал нижние 8 бит в символ и записывал это в файл, а затем сдвигал оставшиеся биты вниз на 8 позиций (повтор).

Answer 4

Ответ

klew, вероятно, тот, который вам нужен, но просто для того, чтобы добавить что-то к тому, что сказал Билл, библиотеки Boost имеют dynamic_bitset , который я нашел полезным в аналогичной ситуации.

Answer 5

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