SICPを読む(81) 問題2.70 - 2.72 ハフマン符号化木(4)
ビット数計算やら、ステップ数計算やら。
問題 2.70
8つのワードがあるから、2^3で、3ビット必要。
固定長符号で考えると歌詞は39ワードあるので、39words*3bit = 117bit必要となる。
可変長な符号な場合、88bitに圧縮された。約25%の節約となった。単調な繰り返しが多い符号化にはかなり有用である事がわかる。ベタ塗りの画像符号化なら、偏りが大きいので相当効果アリ。
問題 2.71
ちょっと自信無し
5記号で3ビット必要。
最高頻度に0だけ割り当てるなら、1ビット。最低頻度に3当てる。
後は地道に計算・・・中間をどう割り当てればいいんだ・・・。
(+ 25 16 9 4 1) ; (* 55 3) 165 25 16 14 (+ (* 25 1) (* 16 2) (* 14 3)) ; 99
こんな感じ?
10の計算はむじぃな・・・。
手動で計算すると死にそうなので、コンピューターの力を借りる。
(define words-tree (generate-huffman-tree '((a 1) (b 4) (c 9) (d 16) (e 25) (f 36) (g 49) (h 64) (i 81) (j 100)))) (encode '(a) words-tree) ; (1 1 0 1 0 0 0) (encode '(b) words-tree) ; (1 1 0 1 0 0 1) (encode '(c) words-tree) ; (1 1 0 1 0 1) (encode '(d) words-tree) ; (1 1 0 1 1) (encode '(e) words-tree) ; (1 1 0 0) (encode '(f) words-tree) ; (0 1 0) (encode '(h) words-tree) ; (1 1 1) (encode '(g) words-tree) ; (0 1 1) (encode '(i) words-tree) ; (0 0) (encode '(j) words-tree) ; (1 0) (* (+ 100 81 64 49 36 25 16 9 4 1) 4) ; 1540 (+ (* (+ 81 100) 2) (* (+ 36 49 64) 3) (* 25 4) (* 16 5) (* 9 6) (* (+ 1 4) 7)) ; 1078
固定長な場合、1540,可変長だと1078。
疑問
全て1にしたら?
(define words-tree (generate-huffman-tree '((a 1) (b 1) (c 1) (d 1) (e 1) (f 1) (g 1) (h 1) (i 1) (j 1)))) (encode '(a) words-tree) ; (1 0 1) (encode '(b) words-tree) ; (1 0 0) (encode '(c) words-tree) ; (0 1 1) ; 略 (encode '(i) words-tree) ; (1 1 0 1) (encode '(j) words-tree) ; (1 1 0 0)
おぉ、固定長よりもビット数が少ない!!
ハフマンすげぇ。これ以上突っ込むと数学がいっぱい飛び出しそうなのでヤメ。
問題 2.72
単純に考えると、最悪のケースで入力*木なのでnの2乗。
難しいって書いてあるからこれ以上のことはパス!
頭の悪い奴というのは、問題の意味がわからないのだ!!
ハフマン符号化木から学んだこと
ハフマン符号化木から学んだことをまとめておく。
- 複数のデータ型を持つツリーの扱いについて学んだ。
- ツリーの検索履歴が有用である事を学んだ。
- ツリーのデータ検索について学んだ。
- 畳み込みながらソートを覚えた。
畳み込みながら何かを加工するというテクニックは今後色々役に立つと思う。
ハフマン符号化木は大満足の章でした。
