Кодирование по методу Хаффмана последовательного слияния функция


Из SICP:

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

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

Сделаем-лист-набор в порядке, определенном выше, которая преобразует список пар в упорядоченный набор листьев. Последовательного слияния процедуры должны писать, используя Make-кода-дерево последовательно объединить маленький вес элементы набора пока нет только один элемент слева, который является нужные Хаффмана дерево. (Эта процедура немного хитрая, но не очень сложно. Если вы окажетесь проектирование сложной процедурой, затем вы почти наверняка делаете что-то не так. Вы можете взять значительное преимущество в том, что мы используем упорядоченный набор представление.)

Я написал следующее решение:

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

(define (successive-merge leaf-set)
  (define (iter result leaf-subset)
    (if (null? leaf-subset) 
        result 
        (let ((first-leaf (car leaf-subset)))
          (iter (make-code-tree first-leaf result) (cdr leaf-subset)))))
  (iter (make-code-tree (car leaf-set) (cadr leaf-set)) (cddr leaf-set)))

Это хороший ответ? Его можно улучшить?



985
3
задан 23 апреля 2011 в 02:04 Источник Поделиться
Комментарии
1 ответ

Это было время, так как я сделал любую схему сюсюкать/, но я сделаю одну точку и одного стиля алгоритмической точки.

Стиль точки: это, как правило, более удобочитаемым, если вы определяете структуру проекции функции с осмысленными именами, а не использовать автомобиль, Удуи т. д.

Алгоритмической точки: самый простой способ сделать это, чтобы включить некоторые приоритетные структура очереди из стандартной библиотеки. После этого вы просто удалите два минимум элементов из очереди, создать их сочетании Хаффмана дерево, и вставьте их в очередь. Вы закончили, когда очередь содержит только один элемент.

3
ответ дан 16 октября 2011 в 11:10 Источник Поделиться