SICP 読み (48) 2.3.4 例: Huffman 符号化木

scheme SICP

紙の上のマンガを書く事が多い今日この頃。問題 2.70 以降は机上ベースの問題になっている模様。

問題 2.70

2.69 の実装だと以下なカンジ。呑ませるリストは

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

で

(make-code-tree
 '(leaf "NA" 13)
 (make-code-tree
 '(leaf "YIP" 9)
 (make-code-tree
  '(leaf "SHA" 3)
  (make-code-tree
   (make-code-tree '(leaf "GET" 2) '(leaf "JOB" 2))
   (make-code-tree '(leaf "A" 2)
                   (make-code-tree (leaf "WAH" 1) (leaf "BOOM" 1)))))))

か。必要なビット数は 6 bits になりますか。で、問題の歌詞を符号化したら以下のようなカンジでしょうか。

5 4 5
3 1 1 1 1 1 1 1 1
5 4 5
3 1 1 1 1 1 1 1 1
6 2 2 2 2 2 2 2 2 2
3 6

合計したらいくつになるんだろうか。
問題の文章にある

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

という文章は意味を図りかねております。上記の値の合計とは違うのかな。

追記

あ。文字列だと symbol な判定が eq? では無理なのかな??
であれば上記は間違いではないのか。解としては

gosh> (+ 5 4 5
3 1 1 1 1 1 1 1 1
5 4 5
3 1 1 1 1 1 1 1 1
6 2 2 2 2 2 2 2 2 2
3 6)
83
gosh>

と出ました。微妙感満点ですがこのままスルー。

問題 2.71

問題にある相対頻度だと、cons リストのような木ができる。(末端は '() ではないですが)
n が 5 の場合は 4 bits で n が 10 の場合は 9 bits となるので、n な木で必要なビット数は n - 1 bits
という事で良いのだろうか。あ、これは最低頻度の記号を符号化するのに必要なビット数ですね。最高頻度のソレについては、全てのケースで 1
bits で良い形になっているように見える。

問題 2.72

紙の上にてステップ数を確認してみたんですが、大体 2倍程度でしょうか。確実に 2 倍よりは多いのですが ...
問題 2.71 のケースで検討しているという事は、釣り合いのとれた二分木ではないので、という事なんだと思うのですが、よく考えてみるとステップ数の増加の程度は、二分木の状態とは関係ないのかなぁ。

別途、答え合わせしてみます。