基礎理論
4記号A,B,C,Dの確率がそれぞれ1/2, 1/4, 1/8, 1/8のとき、ハフマン符号の平均符号長として正しいものはどれか。
ア.1.50ビット
イ.1.65ビット
ウ.1.75ビット正解
エ.2.00ビット
解説
ハフマン符号は「確率の高い記号ほど短い符号を割り当てる」欲張り戦略。木を下から組み立てて、確率の低いものから順に合体させる——圧縮の王道アルゴリズム。
なぜ ウ が正解か
ウが正解。ハフマン木を構築：確率順にC=D=1/8、B=1/4、A=1/2。①C(1/8)とD(1/8)を合体→CD(1/4)、符号長3。②CD(1/4)とB(1/4)を合体→BCD(1/2)、符号長2(B)・3(C,D)。③BCD(1/2)とA(1/2)を合体→根(1)。符号割り当て：A=0（1ビット）、B=10（2ビット）、C=110（3ビット）、D=111（3ビット）。平均符号長=1/2×1+1/4×2+1/8×3+1/8×3=0.5+0.5+0.375+0.375=1.75ビット✓。これはエントロピー(-1/2×log₂(1/2)-1/4×log₂(1/4)-1/8×log₂(1/8)-1/8×log₂(1/8)=0.5+0.5+0.375+0.375=1.75ビット)と一致する理想的なケース。
出典: AI生成問題（学習用）