Сохранение дерева Хаффмана компактно в C++

Question

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

001A1C01E01B1D 

У меня проблема с сохранением этой строки для побитового файла. Я знаю, что C++ может выводить только файл по одному байту за один раз, поэтому у меня проблема с сохранением этой строки в байтах. Можно ли преобразовать первые три бита в символ без добавления прошивки к байту? Если он поместится в байты для кодов обхода, мое дерево (и коды) будет полностью перепутано. Если бы я должен был рубить это по одному бабу за раз, то что произойдет, если дерево не будет точно кратным 8? Что произойдет, если бит-длина сжатого файла не будет точно кратной 8?

Надеюсь, я был достаточно ясен.

Answer 1

Стандартное решение этой проблемы - прокладка. Существует много возможных схем заполнения. Схемы заполнения заполняют до четного количества байтов (т. Е. Кратно 8 битам). Кроме того, они кодируют либо длину сообщения в битах, либо количество битов заполнения (из которых длина сообщения в битах может быть определена путем вычитания). Последнее решение, очевидно, дает несколько более эффективные прокладки.

Проще говоря, вы можете добавить число «неиспользуемых» битов в последнем байте в качестве дополнительного байтового значения.

Один уровень вверх, начните с предположения, что количество заполняющих бит соответствует 3 битам. Определите последние 3 бита закодированного файла для кодирования количества битов заполнения. Теперь, если сообщение использует не более 5 бит последнего байта, отступы могут хорошо вписываться в один и тот же байт. Если необходимо добавить байт, чтобы содержать отступы, максимальный зазор равен 5 + 2 = 7 (5 из неиспользуемых старших бит дополнительного байта, а 2 - максимально возможное свободное пространство в последнем байте, в противном случае 3 -битное значение прокладки было бы подходящим там). Поскольку 0-7 представляется в 3 битах, это работает (он не работает для 2 бит, так как максимальный зазор больше и диапазон отображаемых значений меньше).

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

Answer 2

Просто обработайте последовательность n байтов в виде последовательности 8n бит. Используйте операторы >> или <<, | и & для сбора байтов из последовательности битовых кодов переменной длины.

Конец потока важно для правильной работы. Вам нужен код конца потока, чтобы декодер знал, что нужно остановить и не попытаться декодировать окончательные биты заполнения, которые завершают последний байт.