Декодирование алгоритма/реализация с использованием дерева Хаффмана

Question

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

a: 0 
b: 100 
c: 101 
d: 11 

0 0 100 100 11 101 

Так это будет декодировать: aabbdc

Что декодирования алгоритм я мог бы использовать, что строит дерево Хаффмана, а затем использует его для декодирования сообщения? Образец кода будет также высоко оценен!

Вот что я имел в виду:

• создать таблицу поиска, которая отображает каждый символ его биты
• создать корневой узел
• построить дерево, читать в каждом бите из кодированных
  • если 0, создайте левого ребенка. если 1, создать правильный ребенка
  • если пространство будет достигнуто, указывают лист каким-то образом (нуль левый и правый указатели)
    • не используют биты мы дочитали до этого места и увидеть, что это таблица поиска
    • вставить символ в этом листе

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

Answer 1

На входе нет/не должно быть пробелов. Вы должны просто получить что-то вроде 0010010011101.

Чтобы создать дерево, для каждого символа начинайте с корня, а для каждого бита - влево, если это 0 или пойдите направо, если это 1 (создание узлов там, где это необходимо). Когда вы достигли конца какого-либо символа, установите значение узла, к которому мы привязаны, к символу.

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

Пример:

a = 0 - просто создать левую ребенка на корню.

. 
/
a 

b = 100 - идите направо (для 1), затем налево (для 0), потом снова налево (для 0).

. 
/\ 
a . 
/
    . 
/
b 

c = 101 - идите направо, потом налево, потом направо.

. 
/\ 
a . 
/
    . 
/\ 
b c 

d = 11 - перейти направо, а затем вправо.

. 
/\ 
a . 
/\ 
    . d 
/\ 
b c 

При обработке входного 00100 ...

Начало в корне.

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

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

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