令和２年度 技術士第一次試験問題【専門科目】
Ⅲ－２
次の文字列をハフマン符号化することを考える。
ｅｅｎｙｍｅｅｎｙｍｉｎｙｍｏｅ
ハフマン符号化の過程で、作成される可能性があるハフマン木 (辺上の0と1は省略してある) として、最も不適切なものはどれか。
正解
③
解説
ハフマン符号は最も出現数の高い文字から順に
0 10 110 1110 ・・・ と符号化し、最も出現率の低い文字の最終ビットは1、次に出現率の低い文字の最終ビットを0として符号化する。
ｅ: 5個
ｎ: 3個
ｙ: 3個
ｍ: 3個
ｉ: 1個
ｏ: 1個
ハフマン木は、以下の手順で作成する。
(1) すべての記号の出現率 (出現数) を求める。
(2) 出現率 (出現数) の小さいもの同士で葉と節を作り、その節の２つの葉の出現率の和を求めて、新たな葉とする。
(3) (2)を繰り返す。
問題では、
(1) ｉとｏで節を作る。
(2) (1)と、ｎかｙかｍとで節を作る。
(3) (2)で使わなかったｎかｙかｍのうち、２つで節を作る。
この過程の (3) で、ｍとｅの2つの葉が同じ節から作らることはなく、③が不適切である。
| Ⅲ－１ | 目次 | Ⅲ－３ |