出典：公益社団法人 日本技術士会「技術士第一次試験 過去問題」
情報源記号A、B、C、D、Eがそれぞれ0.12、0.3、0.05、0.45、0.08の確率で発生する無記憶5元情報源に対する2元ハフマン符号として、最も適切なものを選ぶ問題。
与えられた確率のハフマン符号を構成し、符号語の長さが一致する選択肢を選ぶ問題。
① ハフマン符号: 確率の小さい2つを順に合わせていく。確率が大きいほど符号は短い。どの符号も他の符号の頭の部分になってはいけない
② C(0.05)+E(0.08)=0.13 → A(0.12)+0.13=0.25 → B(0.3)+0.25=0.55 → D(0.45)+0.55。符号の長さはD=1、B=2、A=3、C=E=4
③ この長さに合い、頭の重なりもないのは①(②はD=0がB=00の頭になっている)
ハフマン符号は、確率の小さい2つを順に併合して木を作る。確率の小さい順に、C(0.05)とE(0.08)を併合して0.13。次にA(0.12)と0.13を併合して0.25。次にB(0.3)と0.25を併合して0.55。最後にD(0.45)と0.55を併合して1.0となる。符号語長は、D=1、B=2、A=3、C=4、E=4である。選択肢①は、A→100(3ビット)、B→11(2ビット)、C→1010(4ビット)、D→0(1ビット)、E→1011(4ビット)で、符号語長がこれに一致し、どの符号語も他の符号語の接頭語になっていない(語頭符号)。したがって①が正しい。
ハフマン符号は、出現確率の小さい記号を順に併合して作る最適な語頭符号で、確率の大きい記号ほど短い符号語となる。平均符号長=Σ確率×符号語長 を最小にする。
キーワード: ハフマン符号、情報源符号化、平均符号長、無記憶情報源、データ圧縮、情報工学部門