出典：公益社団法人 日本技術士会「技術士第一次試験 過去問題」
文字列eenymeenyminymoeをハフマン符号化する過程で作成される可能性があるハフマン木として、最も不適切なものを選ぶ問題。文字の出現頻度から、ハフマン木の生成手順に従わない木を見分ける。
出現頻度を数え、ハフマン法の手順(頻度の小さい2つを併合)で作られる木かどうかを判断する問題。
① ハフマン木は「その時点で頻度が最小の2つ」を必ず併合して作る
② 頻度: e=5、n=y=m=3、i=o=1。i+o=2 → 2+(3の1つ)=5 → 残りは3,3,5,5なので次は必ず3+3=6 → 5+5=10 → 6+10。根の片側は「頻度3の文字2つ」の組になる
③ ③は y(3) と (n,(i,o))(5) を併合していて、3同士を先に併合していない → ③
文字列の16文字のうち、出現頻度は、e=5、n=3、y=3、m=3、i=1、o=1。ハフマン法では、頻度の小さい2つを順に併合する。まず、i(1)とo(1)を併合して2。次に、2と、頻度3のいずれか(n、y、mのどれか)を併合して5。残りは、3、3、5(e)、5となり、最小の3と3を併合して6。次に、5(e)と5(併合済みの節)を併合して10。最後に6と10を併合する。したがって、根の一方の子は、頻度3の2文字を葉に持つ節(6)で、もう一方の子は、e(5)と、頻度3の1文字と(i,o)の節(5)を併合した節(10)となる。③は、根の子が、(y,(n,(i,o)))と(m,e)となっており、頻度3と3を併合していないため、生成される可能性がなく、最も不適切である。
ハフマン木は、頻度が最小の2節を順に併合して作る。頻度が同じ文字が複数ある場合は、併合の選び方に自由度があり、複数の木ができうるが、必ず、その時点の最小2つを併合している。
キーワード: ハフマン符号、ハフマン木、可変長符号、データ圧縮、出現頻度、情報工学部門