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

Question

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

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

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

Спасибо

Answer 1

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

EDIT

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

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

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

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