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

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

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

В качестве иллюстрации рассмотрим случай, когда относительные частоты символов таковы, как в предыдущем упражнении. В этом случае для того, чтобы закодировать наиболее часто встречающийся символ, мы найдем его сразу же в множестве из одного элемента за константное число шагов, а затем сделаем один шаг по дереву вниз. То есть порядок роста числа шагов равен Θ(1).

Для кодирования наиболее редкого символа нам придется спуститься на всю глубину дерева, то есть произвести поиск в n-1 множестве. В этих множествах будет находиться последовательно n-1, n-2, …, 1 элементов. Поскольку множества представляются неупорядоченными списками, поиск элемента в множестве требует порядка Θ(k) шагов, где k – число элементов множества. Таким образом будет выполнено порядка n поисков, каждый из которых потребует порядка n шагов. А значит порядок роста числа шагов для кодирования самого редкого элемента будет Θ(n2).

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

Для того, чтобы закодировать самый частый символ нам нужно константное число шагов, для кодирования второго по частоте – число шагов порядка n, для третьего – порядка 2n, для четвертого – порядка 3n и т.д. При этом их частоты убывают от 2n-1 до 1. Тогда в среднем число шагов будет равно n*(1/2 + 2/4 + 3/8 + 4/16 + 5/32 + … ). Вообще говоря, ряд конечный, но его можно ограничить сверху соответствующим сходящимся бесконечным рядом с общим членом вида k/2k. Сумма этого сходящегося ряда равна 2. Таким образом мы можем сделать вывод, что в среднем для кодирования одного символа текста требуется Θ(n) шагов. В среднем в данном случае – это не просто какая-то оценка. Это означает, что для кодирования всего сообщения потребуется порядка Θ(L*n) шагов, где L -длина сообщения в символах.

Comments

Comment from gorilych
Date: July 27, 2009, 5:24 pm

в определении encode-symbol можно
1) отбросить сообщение об ошибке
2) сделать безусловный переход направо после первой проверки


(define (encode-symbol symbol tree)
(if (leaf? tree)
null
(if (element-of-set? symbol (symbols (left-branch tree)))
(cons 0 (encode-symbol symbol (left-branch tree))))
(cons 1 (encode-symbol symbol (right-branch tree))))))

Это значительно уменьшит количество шагов.
Проверку на наличие символа в дереве можно сделать в другом месте один раз поискав (element-of-set? symbol (symbols tree).
А после этого можно быть уверенным – если символа нет слева – то он справа.

Comment from Rokker Ruslan
Date: March 6, 2014, 8:01 am

gorilych вы неправильно решили упражнение, прочитайте еще раз

Write a comment