理系学生日記

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

忍者TOOLS

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

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ビットが必要になるはず。