Адаптивное декодирование Хаффмана

Question

В настоящее время я изучаю алгоритмы сжатия и наткнулся на Адаптивного Хаффмана. В отличие от «обычного» Хаффмана, в этом мы не знаем частоту каждого символа априори . Я наткнулся на упражнение, которое просто не могу понять.

Учитывая алфавит A = {1,2,3,4,5,6,7,8} и предполагая, что использовался адаптивный кодер Хаффмана, определите сообщение, соответствующее потоку битов 0110010000011010

Я не понимаю, нужно ли мне строить дерево Хаффмана или есть другой способ обхода без построения дерева, потому что я пытался назначить двоичные коды каждому символу алфавита: 1 для 000, 2 для 001, 3 для 010, 4 для 011, ... (на основе 2 ^ e + r = 8, с e = 3 и r = 0), но не совпадает с правильным awser.

Спасибо за ваше время

Answer 1

Не существует окончательной версии адаптивного Хаффмана, вот некоторые предположения, которые я сделал, чтобы придумать одно возможное решение:

• Кодер для каждого символа адаптивен
• Дерево построено в полете, вы начинаете с пустого дерева, которое содержит только escape-символ
• Символ Escape всегда имеет вес 0
• Левая ветвь - кодовый бит 0, правая ветвь - 1

Сначала в заглушке дерева нет ветвей, поэтому для декодирования escape-символа стоит 0 битов.

Далее получен буквенный код 011 => 4 . Добавлены два новых узла: родительский узел (вес 1) и символ 4 (код 0, вес 1). Экранирующий символ имеет код 1 и вес 0.

Далее код 0 декодируется => 4 , символ 4 имеет вес 2.

Далее код 0 декодируется => 4 , символ 4 имеет вес 3.

Далее код 1 декодируется => escape. Получен буквенный код 000 => 1 . Добавлены два новых узла: родительский узел (вес 1) и символ 1 (код 10, вес 1). Экранирующий символ имеет код 11 и вес 0.

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