이 문제는 글자 n개를 위한 허프만 나무의 빈도가 1, 2, 4, ... , 2^n-1일 때

n = 5, n = 10일 때 나무를 스케치하고

가장 많이 나오는 글자와 가장 덜 나오는 글자를 인코딩하는데

필요한 비트를 구하는 문제입니다.

정말 복잡하네요.^^;;;

파워포인트를 이용하여 나무를 스케치하였습니다.

(조금 이상하게 나왔지만 다른 프로그램을 모르기에...OTL...)

n = 5

n = 10

빈도가 2의 지수로 늘어나기에 저처럼 옆가지를 하나씩 친 나무가 됩니다.

그렇기에 가장 많이 나오는 글자는 비트가 하나만 있으면 됩니다.

그리고 가장 덜 나오는 글자는 (n-1) 비트가 있으면 됩니다.

즉, 가장 많이 나오는 글자 : 1bit, 가장 덜 나오는 글자 : (n-1) bit

참조

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

; 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 16) (list 'B 8) (list 'C 4) (list 'D 2) (list 'E 1)))
(define pairs2 (list (list 'A 512) (list 'B 256) (list 'C 128) (list 'D 64) (list 'E 32) (list 'F 16) (list 'G 8) (list 'H 4) (list 'I 2) (list 'J 1)))
(generate-huffman-tree pairs1)
(generate-huffman-tree pairs2)

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

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