Представление деревьев Хаффмана

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

Листья дерева представляются в виде списка, состоящего из символа leaf (лист), символа, содержащегося в листе, и веса:

(define (make-leaf symbol weight) (list leaf symbol weight))

(define (leaf? object)

(eq? (car object) leaf))

(define (symbol-leaf x) (cadr x))

(define (weight-leaf x) (caddr x))

Дерево в общем случае будет списком из левой ветви, правой ветви, множества символов и веса. Множество символов будет просто их списком, а не каким-то более сложным представлением. Когда мы порождаем дерево слиянием двух вершин, мы получаем вес дерева как сумму весов этих вершин, а множество символов как объединение множеств их символов. Поскольку наши множества представлены в виде списка, мы можем породить объединение при помощи процедуры append, определенной нами в разделе 2.2.1:

(define (make-code-tree left right)

(list left

right

(append (symbols left) (symbols right)) (+ (weight left) (weight right))))

Если мы порождаем дерево таким образом, то у нас будут следующие селекторы:

(define (left-branch tree) (car tree)) (define (right-branch tree) (cadr tree)) (define (symbols tree)

(if (leaf? tree)

(list (symbol-leaf tree)) (caddr tree)))

(define (weight tree)

(if (leaf? tree)

(weight-leaf tree) (cadddr tree)))

Процедуры symbols и weight должны вести себя несколько по-разному в зависимости от того, вызваны они для листа или для дерева общего вида. Это простые примеры обобщенных процедур (generic procedures) (процедур, которые способны работать более, чем с одним типом данных), о которых мы будем говорить намного более подробно в разделах 2.4 и 2.5.

Процедура декодирования

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

(define (decode bits tree)

(define (decode-l bits current-branch) (if (null? bits) ()

(let ((next-branch

(choose-branch (car bits) current-branch))) (if (leaf? next-branch)

(cons (symbol-leaf next-branch)

(decode-l (cdr bits) tree)) (decode-l (cdr bits) next-branch))))) (decode-l bits tree))

(define (choose-branch bit branch)

(cond ((= bit 0) (left-branch branch)) ((= bit l) (right-branch branch))

(else (error "плохой бит -- CHOOSE-BRANCH" bit))))

Процедура decode-l принимает два аргумента: список остающихся битов и текущую позицию в дереве. Она двигается «вниз» по дереву, выбирая левую или правую ветвь в зависимости от того, ноль или единица следующий бит в списке (этот выбор делается в процедуре choose-branch). Когда она достигает листа, она возвращает символ из него как очередной символ сообщения, присоединяя его посредством cons к результату декодирования остатка сообщения, начиная от корня дерева. Обратите внимание на проверку ошибок в конце choose-branch, которая заставляет программу протестовать, если во входных данных обнаруживается что-либо помимо единиц и нулей.

Множества взвешенных элементов

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

Мы представим множество листьев и деревьев как список элементов, упорядоченный по весу в возрастающем порядке. Следующая процедура adjoinset для построения множеств подобна той, которая описана в упражнении 2.61; однако элементы сравниваются по своим весам, и никогда не бывает так, что добавляемый элемент уже содержится в множестве.

(define (adjoin-set x set) (cond ((null? set) (list x))

((< (weight x) (weight (car set))) (cons x set)) (else (cons (car set)

(adjoin-set x (cdr set))))))

Следующая процедура принимает список пар вида символ-частота, например ((A 4) (B 2) (C 1) (D 1)), и порождает исходное упорядоченное множество листьев, готовое к слиянию по алгоритму Хаффмана:

(define (make-leaf-set pairs) (if (null? pairs)

()

(let ((pair (car pairs)))

(adjoin-set (make-leaf (car pair)

(cadr pair)) (make-leaf-set (cdr pairs))))))

Упражнение 2.67.

Пусть нам даны дерево кодирования и пример сообщения:

(define sample-tree

(make-code-tree (make-leaf A 4) (make-code-tree (make-leaf B 2)

(make-code-tree (make-leaf D 1)

(make-leaf C 1)))))

(define sample-message (0 110010101110))

Раскодируйте сообщение при помощи процедуры decode.

Упражнение 2.68.

Процедура encode получает в качестве аргументов сообщение и дерево, и порождает список битов, который представляет закодированное сообщение.

(define (encode message tree) (if (null? message)

()

(append (encode-symbol (car message) tree) (encode (cdr message) tree))))

Encode-symbol - процедура, которую Вы должны написать, возвращает список битов, который кодирует данный символ в соответствии с заданным деревом. Вы должны спроектировать encode-symbol так, чтобы она сообщала об ошибке, если символ вообще не содержится в дереве. Проверьте свою процедуру, закодировав тот результат, который Вы получили в упражнении 2.67, с деревом-примером и проверив, совпадает ли то, что получаете Вы, с исходным сообщением.

Упражнение 2.69.

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

(define (generate-huffman-tree pairs)

(successive-merge (make-leaf-set pairs)))

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