2.3.4. Пример: деревья кодирования по Хаффману
Упражнение 2.69

Процедура successive-merge

Следующая процедура берет в качестве аргумента список пар вида символ-частота (где ни один символ не встречается более, чем в одной паре) и порождает дерево кодирования по Хаффману в соответствии с алгоритмом Хаффмана.

(define (generate-huffman-tree pairs)
  (successive-merge (make-leaf-set pairs)))

Приведенная выше процедура make-leaf-set преобразует список пар в упорядоченное множество пар. Вам нужно написать процедуру successive-merge, которая при помощи make-codetree сливает наиболее легкие элементы множества, пока не останется только один элемент, который и представляет собой требуемое дерево Хаффмана. (Эта процедура устроена немного хитро, но она не такая уж сложная. Если Вы видите, что строите сложную процедуру, значит, почти наверняка Вы делаете что-то не то. Можно извлечь немалое преимущество из того, что мы используем упорядоченное представление для множеств.)



Комментарии отсутствуют.

Необходима авторизация

Вы должны авторизоваться для создания комментария.

Вход