이 문제는 앞에서 만든 프로시저를 가지고 노래 가사를 인코딩 하는 문제입니다.

잘 나오는군요.^^

이 가사 전부를 인코딩 하기위해서는 총 84bit가 필요합니다.

하지만 8낱말로 이루어진 글집합을 길이가 정해진 코드로 인코딩한다면

한 낱말을 표현하는데 3비르가 필요합니다. (2³ = 8)

낱말이 총 36개이므로 36 * 3 = 108비트가 필요합니다.

허프만 알고리즘이 훨씬 짧네요.^^

참조

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

(define true (= 0 0))
(define false (= 0 1))
; section 2.3.3
(define (element-of-set? x set)
  (cond ((null? set) false)
        ((equal? x (car set)) true)
        (else (element-of-set? x (cdr set)))))

; 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))))))
; exercise 2.68
(define (encode message tree)
  (if (null? message)
      '()
      (append (encode-symbol (car message) tree)
              (encode (cdr message) tree))))
(define (encode-symbol sy tree)
  (define (recv current-branch)
    (cond ((leaf? current-branch) null)
          ((element-of-set? sy (symbols (left-branch current-branch)))
           (cons 0 (recv (left-branch current-branch))))
          (else (cons 1 (recv (right-branch current-branch))))))
  (if (not (element-of-set? sy (symbols tree)))
      (error "bad message -- A CHARACTER NOT IN MESSAGE" sy)
      (recv tree)))

; exercise 2.69
(define (generate-huffman-tree pairs)
  (successive-merge (make-leaf-set pairs)))
(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))

; answer
(define ans-list
  (list (list 'A 2) (list 'NA 16) (list 'BOOM 1) (list 'SHA 3) (list 'GET 2) (list 'YIP 9) (list 'JOB 2) (list 'WAH 1)))
(define ans-tree
  (generate-huffman-tree ans-list))

; execute
ans-list
ans-tree
(newline)
(encode '(GET A JOB) ans-tree)
(encode '(SHA NA NA NA NA NA NA NA NA) ans-tree)
(encode '(GET A JOB) ans-tree)
(encode '(SHA NA NA NA NA NA NA NA NA) ans-tree)
(encode '(WAH YIP YIP YIP YIP YIP YIP YIP YIP YIP) ans-tree)
(encode '(SHA BOOM) ans-tree)

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

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