問題2-71〜72

Huffman-treeを構成している記号が任意の数の場合、そこから生成される符号の大きさにどのような分布が見られるかを調べます。(問題2-71)

(define 5-symbols
  '((a 1) (b 2) (c 4) (d 8) (e 16)))

(encode '(a) (generate-huffman-tree 5-symbols))
;=>(0 0 0 0)
(encode '(b) (generate-huffman-tree 5-symbols))
;=>(0 0 0 1)
(encode '(c) (generate-huffman-tree 5-symbols))
;=>(0 0 1)
(encode '(d) (generate-huffman-tree 5-symbols))
;=>(0 1)
(encode '(e) (generate-huffman-tree 5-symbols))
;=>(1)

(define 10-symbols
  '((a 1) (b 2) (c 4) (d 8) (e 16) (f 32) (g 64) (h 128) (i 256) (j 512)))

(encode '(a) (generate-huffman-tree 10-symbols))
;=>(0 0 0 0 0 0 0 0 0)
(encode '(b) (generate-huffman-tree 10-symbols))
;=>(0 0 0 0 0 0 0 0 1)
(encode '(c) (generate-huffman-tree 10-symbols))
;=>(0 0 0 0 0 0 0 1)
(encode '(d) (generate-huffman-tree 10-symbols))
;=>(0 0 0 0 0 0 1)
(encode '(e) (generate-huffman-tree 10-symbols))
;=>(0 0 0 0 0 1)
(encode '(f) (generate-huffman-tree 10-symbols))
;=>(0 0 0 0 1)
(encode '(g) (generate-huffman-tree 10-symbols))
;=>(0 0 0 1)
(encode '(h) (generate-huffman-tree 10-symbols))
;=>(0 0 1)
(encode '(i) (generate-huffman-tree 10-symbols))
;=>(0 1)
(encode '(j) (generate-huffman-tree 10-symbols))
;=>(1)

というわけで、最大頻度の記号は1ビットで表現できますが、最小頻度の記号はn-1ビット必要になってしまいます。
次の問題2-72についてですが、記号の相対頻度が高いほど、Huffman-treeの根に近い部分に存在しているため、探索ステップが少なくなります。最も頻度が高い場合は、1ステップで見つけられます。逆に相対頻度が低い場合は、Huffman-treeの最も深い部分に位置しているため、それだけステップ数が多くなってしまいます。最低頻度の記号の場合、上記の結果からも推察することができますが、n-1のステップが必要となります。
そのため、最高頻度のみを集めた記号列を符号化する場合、文字数に比例したステップの増加になりますが、最低頻度のみを集めた場合は、((n-1)*文字数)という増加傾向が見られるのではないかと思われます。