理系学生日記

おまえはいつまで学生気分なのか

問題2-71 (2.3.4 Example: Huffman Encoding Trees)

SICP

n個のシンボルがあって、それぞれの出現頻度が1,2,4,\cdots,2^{n-1}のときの符号木はどうなるかって話で、n=5のときはこんなになる。

n=10はメンドいので省略しました！


一番出現頻度が大きいシンボルに何ビット必要かは、他のシンボルの出現頻度の和が
\sum_{i=1}^{n-2}2^{i-1}=2^{n-1}-1<2^{n-1}
なので、1ビットですむ。
一番出現頻度が小さいシンボルは木の高さと同じビット数が必要だから、符号木の形を考えるとn-1ビットが必要になるはず。