Действия по сжатию файла с использованием кода Хаффмана

Question

Я знаю, что есть много вопросов, связанных с кодом Хаффмана, включая еще один от меня, но мне интересно, как лучше всего кодировать текстовый файл. Декомпрессия кажется тривиальной; пересекая дерево, двигаясь влево в 0 и вправо в 1, печатая символ.

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

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

Спасибо

Answer 1

Ну, если вы собираетесь кодировать файл на основе символов, я не вижу проблемы, просто сохраните хэш-таблицу символов, затем создайте дерево и запишите его в начале файла, используя любое соглашение, которое вы хотите, Hten применить новый алфавит к тексту. Взгляните на подход, использованный в DEFLATE, который используется для сжатия изображений PNG.

РЕДАКТИРОВАТЬ

Не совсем понятно, в чем проблема.

Искать в дереве персонажа каждый раз, когда он встречается, и проследить шаги?

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

Итак, вы уже разработали алгоритм построения дерева, и проблема в том, как назначить двоичные значения узлам? Или где хранить эти значения? Само дерево представляет двоичные значения естественным образом, вы можете отслеживать их во время построения дерева, просто следите за "путем" элемента в операции вставки и сохраните это значение внутри узла, или создайте хеш-таблицу, если вы этого не сделаете хочу изменить сущность узла.