Хранение и реконструкция дерева Хаффмана

Question

Хранение и реконструкция дерева Хаффмана

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

возьмите дерево ниже:

---------------garbage------
-------------/-------\------
------------A-------garbage-
--------------------/-----\-
-------------------B-------C-

Одной из идей может быть сохранение символа на каждом уровне, а затем использование этой информации для восстановления дерева.
В этом случае:
A1B2C2.
Итак, как я могу сначала получить уровни и связать каждый уровень с персонажем.

1

c++huffman-code tree

Решение

Другие решения

спецификация zlib объясняет, что для хранения дерева Хаффмана нужны только длины битов каждого символа. Например. если построить дерево для A = 101, B = 111, C = 110, D = 01, он просто посчитает длины битов и восстановит дерево по длинам так, чтобы ключевые слова были последовательными -> A = 101, B = 110, С = 111, D = 01. (или что когда-либо производит следующий код)

задавать bl_count[2]=1, bl_count[3]=3 и итерации:

code = 0;   // From z-lib specification, RFC 1951
bl_count[0] = 0;
for (bits = 1; bits <= MAX_BITS; bits++) {
code = (code + bl_count[bits-1]) << 1;
next_code[bits] = code;
}

Максимальная длина символа будет <16 для хранения этих длин требуется максимум 4 бита на символ: 3,3,3,2 == 0011 0011 0011 0010; однако, zlib / deflate лучше — это длина пробега кодирует эти символы используют управляющий символ, такой как 16 == серия из 3, 17: последовательность из 4 и т. д. для дальнейшего сжатия потока длин символов. Также RLE принимает случай нулевой длины, то есть пропущенных символов.

2

Источник

Accepted Answer

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

Если ваши коды Хаффмана канонические, вам нужно хранить только битовые длины для каждого символа, так как это вся информация, необходимая для генерации канонического кодирования. Это относительно небольшое количество бит на символ, поэтому оно должно быть достаточно компактным. Вы также можете дополнительно сжать эту информацию (см. ответ от Аки Суйхконен).

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

Алгоритм генерации канонических кодов довольно прост:

Возьмите все символы, для которых вы хотите сгенерировать коды, отсортированные сначала по длине кода (сначала самое короткое), а затем по самому символу.
Начните с кода нулевой длины.
Если для следующего символа требуется больше битов, чем в настоящее время в коде, добавляйте нули справа (наименее значимые биты) вашего кода до тех пор, пока он не станет нужной длины.
Свяжите код с текущим символом и увеличьте код.
Вернитесь к (3), пока не сгенерируете все символы.

Возьми строку «банан». Очевидно, что используются 3 символа: «b», «a» и «n» со счетами 1, 3 и 2 соответственно.

Так что дерево может выглядеть так:

*
/ \
* а
/ \
б н

Наивно, что могли бы дать коды:

а = 1
б = 00
n = 01

Однако, если вместо этого вы просто используете длину в битах в качестве входных данных для генерации канонического кода, вы получите следующее:

а = 0
б = 10
n = 11

Это другой код, но, очевидно, он будет выдавать сжатый вывод одинаковой длины. Более того, вам нужно только хранить длины кода, чтобы воспроизвести код.

Так что вам нужно только сохранить последовательность:

0 ... 1 2 0 ... 2 0 ...

Где «…» представляет легко сжимаемое повторение, и все значения будут довольно малы (вероятно, только 4-битные каждый — и обратите внимание, что символы не сохраняются вообще). Это представление будет очень компактным.

Если вы действительно должны хранить само дерево, один из методов — пройти по дереву и сохранить один бит, чтобы указать, является ли узел внутренним или конечным, а затем для конечных узлов, хранящих код символа. Это довольно компактно для деревьев, которые не содержат каждый символ, и не так уж плохо даже для довольно полных деревьев. Наихудшим размером для этого будет общий размер всех ваших символов плюс столько отдельных бит, сколько у вас может быть узлов. Для стандартного 8-битного потока байтов это будет 320 байтов (256 байтов для кодов, 511 бит для самой древовидной структуры).

Метод должен начинаться с корневого узла и для каждого узла:

Если узел является родительским, выведите 0, а затем выведите левых и правых потомков.
Если узел является листом, выведите 1, а затем выведите символ

Чтобы восстановить, выполните аналогичную рекурсивную процедуру, но, очевидно, читая данные и выбирая, создавать ли рекурсивно дочерние элементы или читать по символу, в зависимости от ситуации.

Для приведенного выше примера поток битов для дерева будет выглядеть примерно так:

0, 0, 1, «b», 1, «n», 1, «a»

Это 5 битов для дерева, плюс 3 байта для символов, округляя до 4 байтов памяти. Однако он будет быстро расти по мере того, как вы будете добавлять больше символов, в то время как сохранение длин кода не будет.

4