SICP 問題 2.70（記号は、別に文字１コじゃなくてもいいんだぜ。）

問題2.70

次の８記号のアルファベットと相対頻度は、1950年代ロックの歌の叙情詩を効率よく符号化するよう設計された。（「アルファベット」の「記号」は必ずしも個々の文字ではないことに注意）

A	2
BOOM	1
GET	2
JOB	2
NA	16
SHA	3
YIP	9
WAH	1

（問題 2.69の）generate-huffman-tree を使って対応する Huffman 木を作成し、（問題 2.68の）encode を使って次の通信文を符号化せよ。



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

符号化に何ビット必要か。８記号アルファベットの固定長符号を使うとこの歌を符号化するのに必要な最小ビット数はいくらか。

解答

まずは generate-huffman-tree に食わせるデータを作成しよう。



'( (A 2) (BOOM 1) (GET 2) (JOB 2) (NA 16) (SHA 3) (YIP 9) (WAH 1))

では generate-huffman-tree に食わせてみる。あとで使うので評価結果を変数 tree-2.70 に束縛。



gosh> (define tree-2.70 (generate-huffman-tree '((A 2) (BOOM 1) (GET 2) (JOB 2) (NA 16) (SHA 3) (YIP 9) (WAH 1))))

tree-2.70

gosh> tree-2.70

((leaf NA 16) ((leaf YIP 9) (((leaf A 2) ((leaf WAH 1) (leaf BOOM 1) #0=(WAH BOOM) 2) (A . #0#) 4) ((leaf SHA 3) ((leaf JOB 2) (leaf GET 2) #1=(JOB GET) 4) #2=(SHA . #1#) 7) #3=(A WAH BOOM . #2#) 11) #4=(YIP . #3#) 20) (NA . #4#) 36)

gosh>

次に、encode を使って符号化してみる。



gosh> (encode '(Get a job) tree-2.70)


    ERROR: list required, but got #
    Stack Trace:

_______________________________________

  0  (encode (cdr message) tree)

        At line 6 of "(stdin)"

  1  (encode (cdr message) tree)

        At line 6 of "(stdin)"

gosh>

ありゃ？あ、わかった。Scheme（R5RS）って確かシンボルの大文字小文字は区別しないんじゃなかったっけ？と思って調べてみたらshiroさんのこんな記事発見した。やっぱりね。
つーわけで、全部大文字にしてみよう。



gosh> (encode '(GET A JOB) tree-2.70)

(1 1 1 1 1 1 1 0 0 1 1 1 1 0)

gosh>

できた。じゃ、全部符号化してみるか。



gosh> (encode '(GET A JOB) tree-2.70)

(1 1 1 1 1 1 1 0 0 1 1 1 1 0)

gosh> (encode '(SHA NA NA NA NA NA NA NA NA) tree-2.70)

(1 1 1 0 0 0 0 0 0 0 0 0)

gosh> (encode '(GET A JOB) tree-2.70)

(1 1 1 1 1 1 1 0 0 1 1 1 1 0)

gosh> (encode '(SHA NA NA NA NA NA NA NA NA) tree-2.70)

(1 1 1 0 0 0 0 0 0 0 0 0)

gosh> (encode' (WAH YIP YIP YIP YIP YIP YIP YIP YIP YIP) tree-2.70)

(1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0)

gosh> (encode '(SHA BOOM) tree-2.70)

(1 1 1 0 1 1 0 1 1)

gosh>

つーわけで、全ビットを合計すると、



gosh> (length (append '(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)))

84

gosh>

８４ビット。
固定長を使った場合、８種類のシンボルだからサンプルとして摘要すると、
こんな感じになって１記号につき3ビット必要になる。

A	000
BOOM	001
GET	010
JOB	011
NA	100
SHA	101
YIP	110
WAH	111

出現するメッセージの総シンボル数は、



gosh> (length (append '(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)))

36

gosh>

なので、



36シンボル × 3ビット = 108ビット

になると。