問題2.70 – SICP(計算機プログラムの構造と解釈)その82

問題2.70

(define rock-code '((A 2) (BOOM 1) (GET 2) (JOB 2) (NA 16) (SHA 3) (YIP 9) (WAH 1)))
rock-code
gosh> ((A 2) (BOOM 1) (GET 2) (JOB 2) (NA 16) (SHA 3) (YIP 9) (WAH 1))

(define rock-huffman-tree (generate-huffman-tree rock-code))
(display rock-huffman-tree)
gosh> ((leaf NA 16) ((leaf YIP 9) (((leaf A 2) ((leaf WAH 1) (leaf BOOM 1) (WAH BOOM) 2) (A WAH BOOM) 4) ((leaf SHA 3) ((leaf JOB 2) (leaf GET 2) (JOB GET) 4) (SHA JOB GET) 7) (A WAH BOOM SHA JOB GET) 11) (YIP A WAH BOOM SHA JOB GET) 20) (NA YIP A WAH BOOM SHA JOB GET) 36)#<undef>

(define rock-song '(GET A JOB
                        SHA NA NA NA NA NA NA NA NA
                        GET A JOB
                        SHA NA NA NA NA NA NA NA NA
                        WAH YIP YIP YIP YIP YIP YIP YIP YIP YIP
                        SHA BOOM))

(define rock-song-bit (encode rock-song rock-huffman-tree))
rock-song-bit
gosh> (1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 0 1 1)

(length rock-song-bit)
gosh> 84

符号化には 84bit 必要となる。

(length rock-song)
gosh> 36

8記号アルファベットの固定長符号で符号化する場合は、1文字当たり 3bit が必要なので 36(歌の長さ)* 3bit で合計 108bit 必要となる。

計算機プログラムの構造と解釈
ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542
«
»