Изменения

Перейти к: навигация, поиск
м
Нет описания правки
|}
Оценим используемое количество памяти. Так как в нашем дереве <tex> n </tex> листьев, то в нем <tex> 2 \cdot n - 2 </tex> ребер (это легко показать из алгоритма Хаффмана, в нем <tex> n - 1 </tex> итерация и на каждой в дерево добавляется по 2 ребра), а символов в нашей записи будет <tex> 2 \cdot n - 1 </tex>, так как на каждое ребро приходится по символу плюс последний, терминальный, <tex> U </tex>.
=== Передача информации для восстановления листьев ===
Сопоставим каждому символу алфавита равномерный код фиксированной <tex>c'</tex> длины <tex> \lceil log_{2} \log _2 \rceil n</tex> - его порядковый номер в алфавите, записанный в двоичной системе счисления. Тогда, если выписать подряд коды <tex>c'</tex> для всех символов в том порядке, в котором обход в глубину посещает соответствующие им листы, несложно восстановить, какому символу какой код <tex>c</tex> соответствует.
=== Используемая память ===
В этом решении нам также придется передавать размер алфавита (32 бита). Итого, задача решена с использованием <tex>n \lceil log_{2} \log_2 \rceil n + 2n - 1+ 32 = n \lceil \log_2 \rceil n + 2n + 31 </tex> бит.
== Ссылки ==
7
правок

Навигация