이 문제는 허프만 알고리즘에 따라 tree를 만드는 프로시저입니다.

잘 되는군요.^^

이 문제를 읽어보면 이런 글이 있습니다.

'차례 매긴 집합 표현 방식을 쓴다는 사실에서 큰 도움을 얻을 수 있다.'

저 문장을 무시하고 저 나름대로 tree를 해석하고 만들려니 정말 힘들었습니다.

그렇게 한 시간 가량을 보내다가 책을 다시 한 번 살펴보았습니다.

213~214쪽에 적혀진 tree 만드는 글을 읽고서 그 뜻을 알 수 있었습니다.

그 글에 적혀진대로 프로시저를 만드니 정말 간단하게 답이 나왔습니다.

괜히 한 시간을 날렸습니다.OTL....

그리고 한 가지 문제점이 있습니다.

이 프로시저는 (cdr list)가 null인지 확인합니다.

왜냐하면 원소가 하나 남을 때까지 해야하기 때문입니다.

그렇기에 return으로 (car list)를 해야합니다.

하지만 이 프로시저를 만들 때 별 생각없이 list를 return하였습니다.

전부터 (cdr list)가 아닌 list가 null인지 확인하였기 때문입니다.

그런 습관이 쌓여서 저런 실수를 한 것입니다.

리턴을 무엇으로 해야하는지 천천히 생각해보고 만들어야겠습니다.

참조

해럴드 애빌슨, 김재우 역, <컴퓨터 프로그램의 구조와 해석>, 인사이트, 2007, pp. 219

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

; section 2.3.4
(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))
(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)))
(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))))))
(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))))))

; answer
(define (successive-merge orderlist)
  (define (iter list)
    (cond ((null? (cdr list)) (car list))
          (else (iter (adjoin-set
                       (make-code-tree (car list) (cadr list))
                       (cddr list))))))
  (iter orderlist))

; execute
(define pairs1 (list (list 'A 4) (list 'B 2) (list 'C 1) (list 'D 1)))
(make-leaf-set pairs1)
(generate-huffman-tree pairs1)

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.