2020年11月07日

令和2年度 技術士第一次試験問題 情報工学部門 V−2

V−2

次の文字列をハフマン符号化することを考える。
  eenymeenyminymoe
ハフマン符号化の過程で、作成される可能性があるハフマン木 (辺上の0と1は省略してある) として、最も不適切なものはどれか。

令和2年度 技術士第一次試験問題 情報工学部門 V−2





正解

B


解説

ハフマン符号は最も出現数の高い文字から順に
0 10 110 1110  ・・・ と符号化し、最も出現率の低い文字の最終ビットは1、次に出現率の低い文字の最終ビットを0として符号化する。

e: 5個
n: 3個
y: 3個
m: 3個
i: 1個
o: 1個

ハフマン木は、以下の手順で作成する。
(1) すべての記号の出現率 (出現数) を求める。
(2) 出現率 (出現数) の小さいもの同士で葉と節を作り、その節の2つの葉の出現率の和を求めて、新たな葉とする。
(3) (2)を繰り返す。

問題では、
(1) iとoで節を作る。
(2) (1)と、nかyかmとで節を作る。
(3) (2)で使わなかったnかyかmのうち、2つで節を作る。
この過程の (3) で、mとeの2つの葉が同じ節から作らることはなく、Bが不適切である。

posted by ファーストマクロ at 08:02| Comment(0) | R02技術士一次試験(情報工学)
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

認証コード: [必須入力]


※画像の中の文字を半角で入力してください。