Serendip

Web Studio

問題2.71

(define (expt-pair pairs)
  (let ((n (length pairs)))
       (define (iter pairs)
         (let ((i (- n (length pairs))))
              (if (null? pairs)
                  '()
                  (cons (list (car pairs) (expt 2 i))
                        (iter (cdr pairs))))))
       (iter pairs)))

(define set5 '(A B C D E))
(define set10 '(A B C D E F G H I J))

(expt-pair set5)
gosh> ((A 1) (B 2) (C 4) (D 8) (E 16))
(expt-pair set10)
gosh> ((A 1) (B 2) (C 4) (D 8) (E 16) (F 32) (G 64) (H 128) (I 256) (J 512))

(define set5-huffman-tree (generate-huffman-tree (expt-pair set5)))
; (((((leaf A 1) (leaf B 2) (A B) 3) (leaf C 4) (A B C) 7) (leaf D 8) (A B C D) 15) (leaf E 16) (A B C D E) 31)
(define set10-huffman-tree (generate-huffman-tree (expt-pair set10)))
; ((((((((((leaf A 1) (leaf B 2) (A B) 3) (leaf C 4) (A B C) 7) (leaf D 8) (A B C D) 15) (leaf E 16) (A B C D E) 31) (leaf F 32) (A B C D E F) 63) (leaf G 64) (A B C D E F G) 127) (leaf H 128) (A B C D E F G H) 255) (leaf I 256) (A B C D E F G H I) 511) (leaf J 512) (A B C D E F G H I J) 1023)

(encode '(E) set5-huffman-tree)
gosh> (1)
(encode '(J) set10-huffman-tree)
gosh> (1)
(encode '(A) set5-huffman-tree)
gosh> (0 0 0 0)
(encode '(A) set10-huffman-tree)
gosh> (0 0 0 0 0 0 0 0 0)

n = 5 の場合、最高頻度の記号の符号化には 4bit 、最低頻度の記号の符号化には 1bit が必要となる。
n = 10 の場合、最高頻度の記号の符号化には 9bit 、最低頻度の記号の符号化には 1bit が必要となる。

したがって n 記号のHuffman木の最高頻度の記号の符号化には (n - 1) bit、最低頻度の記号の符号化には 1bit が必要となる。

問題2.72

最低頻度の記号の符号化の場合

O(1)

最高頻度の記号の符号化の場合

O(n^2)

計算機プログラムの構造と解釈

posted with amazlet at 08.11.07

ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542

Amazon.co.jp で詳細を見る