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

18 February, 2008 (21:50) | Решения упражнений

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

1+2 = 3 = 4 – 1,

3+4 = 7 = 8 – 1,

2n-1 + 2n = 2n+1-1.

Таким образом дерево Хаффмана для n=5 будет выглядеть следующим образом (слева частоты обозначены простыми числами, а справа через степени двойки для наглядности):

2711.png

Для n=10 дерево будет таким (вновь слева частоты обозначены простыми числами, а справа через степени двойки):

2712.png

Самый часто встречающийся символ имеет частоту 2n-1 и находится сразу налево от корня, то есть кодируется одним битом 0.

Самый редко встречающийся символ имеет частоту 1=20 и находится на самом длинном пути в дереве, состоящем из n-1 единицы, то есть имеет код 11…1 (число битов в коде равно n-1).

Write a comment