Решение упражнения 2.67 из SICP

15 February, 2008 (20:54) | Решения упражнений

Дерево кодирования из примера изображено на рисунке ниже:

2671.png

При декодировании последовательности

0 1 1 0 0 1 0 1 0 1 1 1 0

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

Сначала, пройдем по левой ветке (0) и попадем в лист А:

0 1 1 0 0 1 0 1 0 1 1 1 0  

A

Теперь, двигаясь направо (1), опять направо (1) и налево (0), получим D:

0 1 1 0 0 1 0 1 0 1 1 1 0  

A D

Дальше действуем аналогично (шаги показаны ниже, результат на каждом шаге выделен жирным шрифтом):

0 1 1 0 0 1 0 1 0 1 1 1 0  

A D A
0 1 1 0 0 1 0 1 0 1 1 1 0  

A D A B
0 1 1 0 0 1 0 1 0 1 1 1 0  

A D A B B
0 1 1 0 0 1 0 1 0 1 1 1 0  

A D A B B C
0 1 1 0 0 1 0 1 0 1 1 1 0  

A D A B B C A

И действительно:

> (decode sample-message sample-tree)  

(A D A B B C A)

Write a comment