получить пары из дерева Хаффмана

Я пытаюсь написать процедуру листьев Хаффмана; процедура возвращает список пар из созданного дерева Хаффмана. Пример того, как это работает

  (huffman-leaves sample-tree) 
   ->((A . 8) (C . 5) (B . 1) (D . 1))

То, что я придумал, но заблокировало сценаристов...

(define (huffman-leaves tree)
  (define (huffman-get-pairs current-branch pairs)
     (if (or (null? tree) (null? current-branch))
         pairs
         (let ((next-branch
                (get-branch (car current-branch) current-branch)))
           (not (member? next-branch pairs)
                (if (leaf? next-branch)
                    (cons (append  pairs next-branch)
                          (display pairs)
                          (huffman-get-pairs (cadr current-branch) pairs))
                    (huffman-get-pairs next-branch pairs))))))
  (huffman-get-pairs tree '()))

  (member? item 'list) #if item in list return #t else #false

Я знаю, что делаю что-то не так, но не вижу этого. Как я могу остановить поиск в дереве Хаффмана в схеме? Любой совет, что я должен делать по-другому?


list tree scheme huffman-code
person user2079185    schedule 12.03.2013    source источник
comment
Трудно ответить на такой вопрос, не зная вашего определения данных для дерева Хаффмана. То есть комментарий вида: ;; Дерево Хаффмана является одним из: - (list 'Leaf Char Frequency) или: - (list 'Node HuffmanTree HuffmanTree). (Я уверен, что этот пример определения данных не тот, который вам нужен; он просто предназначен для иллюстрации стиля.   -  person pnkfelix    schedule 12.03.2013

Ответы (1)


arrow_upward
3
arrow_downward

Я рекомендую:

  1. Напишите определение данных для дерева Хаффмана.

  2. Создайте пример входных деревьев Хаффмана, закодированных в соответствии с вашим определением данных из шага 1, и ожидаемые результаты (в данном случае списки листьев).

  3. Следуйте рецепту дизайна, чтобы создать базовый шаблон для функции huffman-leaves.

  4. Заполните ... в своем шаблоне в соответствии с примерами, которые вы построили на шаге 2.

  5. Переведите свои примеры из шага 2. в тесты и протестируйте свой код из шага 4.

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

Если вы предпочитаете настоящий код, вот одно из направлений, в котором вы можете пойти, чтобы сделать очень общее решение для вашей проблемы:

;; make-visitor : (X -> Y) (X -> [Listof X]) (Y [Listof Z] -> Z) -> Z
;; Very generic descend+map+recombine routine
;; (note X, Y, Z are implicitly universally quantified above).
(define (make-visitor transform children combine)
  (lambda (x)
    (let rec ((x x)) ;; rec : X -> Z
      (combine (transform x)
               (map rec (children x))))))

;; ... the hard bit is coming up with the appropriate lambda
;; expressions for `transform`, `children`, and `combine` above.

(define leaves
  (make-visitor (lambda (x) ...)
                (lambda (x) ...)
                (lambda (y zs) ...)))

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

person pnkfelix    schedule 12.03.2013