Каков базовый метод хранения дерева Хаффмана вместе с закодированным потоком битов в виде файла?

#file #huffman-code

#файл #хаффман-код

Вопрос:

Как я могу сохранить битовый поток в кодировке Хаффмана в виде двоичного файла?

Ответ №1:

Для сохранения кодировки вам понадобятся три вещи:

  1. Некоторый способ восстановления дерева кодирования, сопоставляющий каждый символ с битовым шаблоном.
  2. Фактическое кодирование потока.
  3. Какой-нибудь способ определения конца закодированных данных.

Существует множество способов решения каждой из этих проблем. Вы могли бы явно сохранить шаблоны битов для каждого символа в таблице или просто использовать одну и ту же таблицу кодирования для всех потоков, которые вы сжимаете. Что касается того, как определить конец потока, одним из вариантов может быть использование символа псевдо-EOF для завершения этого потока. Для этого при создании дерева кодирования Хаффмана добавьте к нему новый символ с кратностью один, который будет служить сигналом, обозначающим конец потока. При записи результата вы пишете этот символ в конце, чтобы можно было определить, где заканчивается поток, даже если в нем не используется количество битов, которое идеально вписывается в байт.

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